-
作者：Burer, Samuel; Ye, Yinyu
作者单位：University of Iowa; Stanford University
摘要：We study a class of quadratically constrained quadratic programs (QCQPs), called diagonal QCQPs, which contain no off-diagonal terms x j xk for j = k, and we provide a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact. Our condition complements and refines those already present in the literature and can be checked in polynomial time. We then extend our analysis from diagonal QCQPs to general QCQPs, i.e., ones with no particular structure...
-
作者：Bendotti, Pascale; Fouilhoux, Pierre; Rottner, Cecile
作者单位：Sorbonne Universite; Electricite de France (EDF)
摘要：We consider integer linear programs whose solutions are binary matrices and whose (sub-)symmetry groups are symmetric groups acting on (sub-)columns. Such structured sub-symmetry groups arise in important classes of combinatorial problems, e.g. graph coloring or unit commitment. For a priori known (sub-)symmetries, we propose a framework to build (sub-)symmetry-breaking inequalities for such problems, by introducing one additional variable per considered sub-symmetry group. The derived inequal...
-
作者：O'Connor, Daniel; Vandenberghe, Lieven
作者单位：University of San Francisco; University of California System; University of California Los Angeles
摘要：The primal-dual hybrid gradient (PDHG) algorithm proposed by Esser, Zhang, and Chan, and by Pock, Cremers, Bischof, and Chambolle is known to include as a special case the Douglas-Rachford splitting algorithm for minimizing the sum of two convex functions. We show that, conversely, the PDHG algorithm can be viewed as a special case of the Douglas-Rachford splitting algorithm.
-
作者：Aprile, Manuel; Faenza, Yuri
作者单位：Universite Libre de Bruxelles; Columbia University
摘要：Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the extended formulation also depends on the number of rows of the slack matrix (hence, on the exact description in the original space). We give general sufficient conditions under which those tools can be implemented as to be output-efficient, showin...
-
作者：Gaar, Elisabeth; Rendl, Franz
作者单位：University of Klagenfurt
摘要：The exact subgraph approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation...
-
作者：Nannicini, Giacomo; Sartor, Giorgio; Traversi, Emiliano; Calvo, Roberto Wolfler
作者单位：International Business Machines (IBM); IBM USA; SINTEF; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); University of Cagliari
摘要：We propose a Branch-and-Cut algorithm for the robust influence maximization problem. The influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able to influence the maximum number of other actors. We assume that the social network is given in the form of a graph with node thresholds to indicate the resistance of an actor to influence, and arc weights to represent the strength of the influence between two actors. In the robus...
-
作者：Shindin, Evgeny; Weiss, Gideon
作者单位：International Business Machines (IBM); IBM ISRAEL; University of Haifa
摘要：We consider continuous linear programs over a continuous finite time horizon T, with a constant coefficient matrix, linear right hand side functions and linear cost coefficient functions. Specifically, we search for optimal solutions in the space of measures or of functions of bounded variation. These models generalize the separated continuous linear programming models and their various duals, as formulated in the past by Anderson, by Pullan, and by Weiss. In previous papers we formulated a sy...
-
作者：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...
