-
作者：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...
-
作者：Black, Alexander E.
作者单位：Bowdoin College
摘要：The existence of a pivot rule for the simplex method that guarantees a polynomial run-time is a longstanding, fundamental open problem in the theory of linear programming. The most popular pivot rule for theoretical analysis is the shadow pivot rule, which solves a linear program by projecting the feasible region onto a polygon. It has been shown to perform in expected polynomial time on uniformly random instances and in smoothed analysis. In practice, the pivot rule of choice is the steepest ...
-
作者：Upadhyaya, Manu; Latafat, Puya; Giselsson, Pontus
作者单位：Lund University; IMT School for Advanced Studies Lucca
摘要：We develop a Lyapunov-based analysis of Korpelevich's extragradient method and show that it achieves an o(1/k) last-iterate convergence rate of the constructed Lyapunov function. This Lyapunov function simultaneously upper bounds several standard measures of optimality, which allows our analysis to sharpen existing last-iterate convergence guarantees for these measures. Moreover, the same analysis enables the design of a class of flexible extensions of the extragradient method in which extragr...
-
作者：Li, Yongchun; Xie, Weijun
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective function subject to multiple two-sided linear inequalities intersected with a low-rank and spectral constrained domain. Although solving LSOP is generally NP-hard, its partial convexification (i.e., replacing the domain with its convex hull), termed LSOP-R, is often tractable and yields a high-quality solution. This motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point...
-
作者：Luo, Fengqiao; Dey, Shibshankar; Mehrotra, Sanjay
作者单位：Northwestern University
摘要：We present a finitely convergent cutting-plane algorithm for solving a general mixed-integer convex program given an oracle for solving a general convex program. This method is extended to solve a family of two-stage mixed-integer convex programs using cutting planes, with applications to solving distributionally-robust two-stage stochastic mixed-integer convex programs. Analysis is also given for the case where convex programming oracle provides an is an element of-optimal solution. We combin...
