-
作者：Cifuentes, Diego; Harris, Corey; Sturmfels, Bernd
作者单位：Massachusetts Institute of Technology (MIT); University of Oslo; University of California System; University of California Berkeley
摘要：Consider the problem of minimizing a quadratic objective subject to quadratic equations. We study the semialgebraic region of objective functions for which this problem is solved by its semidefinite relaxation. For the Euclidean distance problem, this is a bundle of spectrahedral shadows surrounding the given variety. We characterize the algebraic boundary of this region and we derive a formula for its degree.
-
作者：Leme, Renato Paes; Wong, Sam Chiu-wai
作者单位：Alphabet Inc.; Google Incorporated; University of California System; University of California Berkeley
摘要：We present the first polynomial time algorithm for computing Walrasian equilibrium in an economy with indivisible goods and general buyer valuations having only access to an aggregate demand oracle, i.e., an oracle that given prices on all goods, returns the aggregated demand over the entire population of buyers. For the important special case of gross substitute valuations, our algorithm queries the aggregate demand oracle O(n(3)) times and takes O(n(3)) time, where n is the number of goods a...
-
作者：Zheng, Yang; Fantuzzi, Giovanni; Papachristodoulou, Antonis; Goulart, Paul; Wynn, Andrew
作者单位：University of Oxford; Imperial College London
摘要：We employ chordal decomposition to reformulate a large and sparse semidefinite program (SDP), either in primal or dual standard form, into an equivalent SDP with smaller positive semidefinite (PSD) constraints. In contrast to previous approaches, the decomposed SDP is suitable for the application of first-order operator-splitting methods, enabling the development of efficient and scalable algorithms. In particular, we apply the alternating direction method of multipliers (ADMM) to solve decomp...
-
作者：Di Summa, Marco
作者单位：University of Padua
摘要：The infinite relaxations in integer programming were introduced by Gomory and Johnson to provide a general framework for the theory of cutting planes: the so-called valid functions, and in particular the minimal and extreme functions, can be seen as automatic rules for the generation of cuts. However, while many extreme functions are piecewise linear and therefore easy to describe, the set of extreme functions turns out to have a very complicated mathematical structure, as several extreme func...
-
作者：Iutzeler, Franck; Malick, Jerome; de Oliveira, Welington
作者单位：Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Universite PSL; MINES ParisTech
摘要：In this paper, we consider nonsmooth convex optimization problems with additive structure featuring independent oracles (black-boxes) working in parallel. Existing methods for solving these distributed problems in a general form are synchronous, in the sense that they wait for the responses of all the oracles before performing a new iteration. In this paper, we propose level bundle methods handling asynchronous oracles. These methods require original upper-bounds (using upper-models or scarce ...
-
作者：Gleixner, Ambros; Steffy, Daniel E.
作者单位：Zuse Institute Berlin; Oakland University
摘要：Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations is considered through a bit-complexity analysis. Yet in practice, implementations typically use limited-precision arithme...
-
作者：Fiorini, Samuel; Joret, Gwenael; Schaudt, Oliver
作者单位：Universite Libre de Bruxelles; Universite Libre de Bruxelles; University of Cologne
摘要：We study the problem of deleting a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. This problem is often calledcluster vertex deletionin the literature and admits a straightforward 3-approximation algorithm since it is a special case of the vertex cover problem on a 3-uniform hypergraph. Recently, You, Wang, and Cao described an efficient 5/2-approximation algorithm for the unweighted version of the p...
-
作者：de Klerk, Etienne; Kuhn, Daniel; Postek, Krzysztof
作者单位：Tilburg University; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam
摘要：In distributionally robust optimization the probability distribution of the uncertain problem parameters is itself uncertain, and a fictitious adversary, e.g., nature, chooses the worst distribution from within a knownambiguity set. A common shortcoming of most existing distributionally robust optimization models is that their ambiguity sets contain pathological discrete distributions that give nature too much freedom to inflict damage. We thus introduce a new class of ambiguity sets that cont...
-
作者：Verdugo, Victor; Verschae, Jose; Wiese, Andreas
作者单位：University of London; London School Economics & Political Science; Universidad de O'Higgins; Universidad de Chile; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：The sum of squares (SoS) hierarchy gives an automatized technique to create a family of increasingly tight convex relaxations for binary programs. There are several problems for which a constant number of rounds of this hierarchy give integrality gaps matching the best known approximation algorithms. For many other problems, however, ad-hoc techniques give better approximation ratios than SoS in the worst case, as shown by corresponding lower bound instances. Notably, in many cases these insta...
-
作者：Dash, Sanjeeb; Gunluk, Oktay; Moran R, Diego A.
作者单位：International Business Machines (IBM); IBM USA; Universidad Adolfo Ibanez
摘要：Given P. Rn, a mixed-integer set PI = P n (Zt x Rn-t), and a k-tuple of ndimensional integral vectors (p1,..., pk) where the last n - t entries of each vector is zero, we consider the relaxation of PI obtained by taking the convex hull of points x in P for which pT 1 x,..., pT k x are integral. We then define the k-dimensional lattice closure of PI to be the intersection of all such relaxations obtained from k-tuples of n-dimensional vectors. When P is a rational polyhedron, we show that given...
