-
作者：Li, Xiaodong; Li, Yang; Ling, Shuyang; Strohmer, Thomas; Wei, Ke
作者单位：University of California System; University of California Davis; University of California System; University of California Davis; Fudan University
摘要：Given a set of data, one central goal is to group them into clusters based on some notion of similarity between the individual objects. One of the most popular and widely-used approaches is k-means despite the computational hardness to find its global minimum. We study and compare the properties of different convex relaxations by relating them to corresponding proximity conditions, an idea originally introduced by Kumar and Kannan. Using conic duality theory, we present an improved proximity c...
-
作者：Carmon, Yair; Duchi, John C.; Hinder, Oliver; Sidford, Aaron
作者单位：Stanford University; Stanford University; Stanford University
摘要：We prove lower bounds on the complexity of finding similar to-stationary points (points x such that similar to. f (x)similar to = similar to) of smooth, high-dimensional, and potentially non-convex functions f. We consider oracle-based complexity measures, where an algorithm is given access to the value and all derivatives of f at a query point x. We show that for any (potentially randomized) algorithm A, there exists a function f with Lipschitz pth order derivatives such that A requires at le...
-
作者：Koehne, Anna; Traub, Vera; Vygen, Jens
作者单位：University of Bonn; University of Bonn
摘要：We show that the classical LP relaxation of the asymmetric traveling salesman path problem (ATSPP) has constant integrality ratio. If.ATSP and.ATSPP denote the integrality ratios for the asymmetric TSP and its path version, then.ATSPP = 4.ATSP - 3. We prove an even better bound for node-weighted instances: if the integrality ratio for ATSP on node-weighted instances is.NWATSP, then the integrality ratio for ATSPP on node-weighted instances is at most 2.NW ATSP - 1. Moreover, we show that for A...
-
作者：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...
