-
作者：Doron-Arad, Ilan; Kulik, Ariel; Shachnai, Hadas
作者单位：Technion Israel Institute of Technology; Ben-Gurion University of the Negev
摘要：We study the budgeted versions of the well known matching, matroid independent set, and matroid intersection problems. While all problems admit polynomial-time approximation schemes (PTAS) [Berger et al. (Math. Programming, 2011), Chekuri, Vondr & aacute;k and Zenklusen (SODA 2011)], it has been an intriguing open question whether these problems admit an efficient PTAS (EPTAS). In this paper, we answer this question affirmatively, by presenting an EPTAS for budgeted matching, budgeted matroid ...
-
作者：Ju, Caleb; Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：This paper proposes a novel termination criterion, termed the advantage gap function, for finite state and action Markov decision processes (MDP) and reinforcement learning (RL). By incorporating this advantage gap function into the design of step size rules and deriving a new linear rate of convergence that is independent of the stationary state distribution of the optimal policy, we demonstrate that policy gradient methods can solve MDPs in strongly-polynomial time. To the best of our knowle...
-
作者：Rubbens, Anne; Hendrickx, Julien M.
作者单位：Universite Catholique Louvain
摘要：We consider the problem of obtaining interpolation constraints for function classes, i.e., necessary and sufficient constraints that a set of points, function values and (sub)gradients must satisfy to ensure the existence of a global function of the class considered, consistent with this set. The derivation of such constraints is crucial, e.g., in the performance analysis of optimization methods, since obtaining a priori tight performance guarantees requires using a tight description of functi...
-
作者：Moura, Phablo F. S.; Yaman, Hande; Leus, Roel
作者单位：KU Leuven
摘要：Let k be a positive integer and let G be a graph with n vertices. A connected k-subpartition of G is a collection of k pairwise disjoint sets (a.k.a. classes) of vertices in G such that each set induces a connected subgraph. The connected k-subpartition polytope of G, denoted by P(G,k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} ...
-
作者：Jin, Billy; Klein, Nathan; Williamson, David P.
作者单位：Purdue University System; Purdue University; Boston University; Cornell University
摘要：One of the most famous conjectures in combinatorial optimization is the four-thirds conjecture, which states that the integrality gap of the Subtour LP relaxation of the TSP is equal to 43\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{4}{3}$$\end{document}. For 40 years, the best known upper bound was 1.5, d...
-
作者：Pennanen, Teemu; Perkkioe, Ari-Pekka
作者单位：University of London; King's College London; University of Munich
摘要：This paper studies duality and optimality conditions in general convex stochastic optimization problems introduced by Rockafellar and Wets in (Math Programm Stud 6:170-187, 1976). We derive an explicit dual problem in terms of two dual variables, one of which is the shadow price of information while the other one gives the marginal cost of a perturbation much like in classical Lagrangian duality. Existence of primal solutions and the absence of duality gap are obtained without compactness or b...
-
作者：Ponte, Gabriel; Fampa, Marcia; Lee, Jon
作者单位：Universidade Federal Rural do Rio de Janeiro (UFRRJ); Universidade Federal do Rio de Janeiro; University of Michigan System; University of Michigan
摘要：We develop a branch-and-bound algorithm for the integer D-optimality problem, a central problem in statistical design theory, based on two convex relaxations, employing variable-bound tightening and fast local-search procedures, testing our ideas on various test problems.
-
作者：Ibrahimpur, Sharat; Vegh, Laszlo A.
作者单位：University of Bonn; University of Bonn
摘要：In the Flexible Graph Connectivity (FGC) problem, we are given an undirected multigraph on n vertices with nonnegative edge costs, where each edge is classified as either safe or unsafe. Given integer parameters p and q, the goal in (p, q)-FGC is to purchase a minimum-cost set of edges such that the resulting spanning subgraph remains p-edge-connected after the removal of any set of up to q unsafe edges. Our main contribution is an O(logn) -approximation algorithm based on independent rounding...
-
作者：Liu, Tianxiang; Lourenco, Bruno F.
作者单位：University of Tsukuba; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
摘要：We introduce the notion of Karamata regular operators, which is a notion of regularity that is suitable for obtaining concrete convergence rates for common fixed point problems. This provides a broad framework that includes, but goes beyond, H & ouml;lderian error bounds and H & ouml;lder regular operators. By concrete, we mean that the rates we obtain are explicitly expressed in terms of a function of the iteration number k instead, of say, a function of the iterate xk\documentclass[12pt]{min...
-
作者：Kuhlmann, Stefan; Oertel, Timm; Weismantel, Robert
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Erlangen Nuremberg
摘要：This paper deals with the following question: Suppose that there exist an integer or a non-negative integer solution x to a system Ax = b, where the number of non-zero components of x is n. The target is, for a given natural number k < n, to approximate b with Ay where y is an integer or non-negative integer solution with at most k nonzero components. We establish upper bounds for this question in general. In specific cases, these bounds are tight. If we view the approximation quality as a fun...
