-
作者：Bennett, Kristin P.; Ferris, Michael C.; Pang, Jong-Shi; Solodov, Mikhail V.; Wright, Stephen J.
作者单位：Rensselaer Polytechnic Institute; University of Wisconsin System; University of Wisconsin Madison; University of Southern California; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
-
作者：Shen, Lingqing; Nam Ho-Nguyen; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University; University of Sydney
摘要：We propose a new framework for solving the convex bilevel optimization problem, where one optimizes a convex objective over the optimal solutions of another convex optimization problem. As a key step of our framework, we form an online convex optimization (OCO) problem in which the objective function remains fixed while the domain changes over time. We note that the structure of our OCO problem is different from the classical OCO problem that has been intensively studied in the literature. We ...
-
作者：Borst, Sander; Dadush, Daniel; Huiberts, Sophie; Tiwari, Samarth
作者单位：Centrum Wiskunde & Informatica (CWI)
摘要：For a binary integer program (IP) max c(T)x, Ax <= b, x is an element of {0, 1}(n), where A is an element of R-mxn and c is an element of R-n have independent Gaussian entries and the right-hand side b is an element of R-m satisfies that its negative coordinates have l(2) norm at most n/10, we prove that the gap between the value of the linear programming relaxation and the IP is upper bounded by poly(m)(log n)(2)/n with probability at least 1 - 2/n(7) - 2(-poly(m)). Our results give a Gaussia...
-
作者：Basu, Amitabh
作者单位：Johns Hopkins University
摘要：In the first part of this paper, we present a unified framework for analyzing the algorithmic complexity of any optimization problem, whether it be continuous or discrete in nature. This helps to formalize notions like input, size and complexity in the context of general mathematical optimization, avoiding context dependent definitions which is one of the sources of difference in the treatment of complexity within continuous and discrete optimization. In the second part of the paper, we employ...
-
作者：Averkov, Gennadiy; Hojny, Christopher; Schymura, Matthias
作者单位：Brandenburg University of Technology Cottbus; Eindhoven University of Technology
摘要：The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is a useful tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on rc(Q)(X), a variant of rc(X) in which the polyhedra P are required to be rational, and we show that rc(X) can be computed in polynomial time if X is 2-dime...
-
作者：Helou, Elias S.; Santos, Sandra A.; Simoes, Lucas E. A.
作者单位：Universidade de Sao Paulo; Universidade Estadual de Campinas
摘要：The solution of bilevel optimization problems with possibly nondifferentiable upper objective functions and with smooth and convex lower-level problems is discussed. A new approximate one-level reformulation for the original problem is introduced. An algorithm based on this reformulation is developed that is proven to converge to a solution of the bilevel problem. Each iteration of the algorithm depends on the solution of a nonsmooth optimization problem and its implementation leverages recent...
-
作者：Aprile, Manuel; Drescher, Matthew; Fiorini, Samuel; Huynh, Tony
作者单位：University of Padua; Universite Libre de Bruxelles; Monash University
摘要：We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines previous approaches, based on the local ratio technique and the management of twins, with a novel construction of a good cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster verte...
