-
作者：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...
-
作者：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...
-
作者：Johnstone, Patrick R.; Moulin, Pierre
作者单位：Rutgers University System; Rutgers University New Brunswick; University of Illinois System; University of Illinois Urbana-Champaign
摘要：The purpose of this manuscript is to derive new convergence results for several subgradient methods applied to minimizing nonsmooth convex functions with Holderian growth. The growth condition is satisfied in many applications and includes functions with quadratic growth and weakly sharp minima as special cases. To this end there are three main contributions. First, for a constant and sufficiently small stepsize, we show that the subgradient method achieves linear convergence up to a certain r...
-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco
作者单位：Johns Hopkins University; University of Padua
摘要：We consider Gomory and Johnson's infinite group model with a single row. Valid inequalities for this model are expressed by valid functions and it has been recently shown that any valid function is dominated by some nonnegative valid function, modulo the affine hull of the model. Within the set of nonnegative valid functions, extreme functions are the ones that cannot be expressed as convex combinations of two distinct valid functions. In this paper we construct an extreme function pi:R ->[0,1...
-
作者：Klatte, Diethard; Kummer, Bernd
作者单位：University of Zurich; Humboldt University of Berlin
-
作者：Ahmadi, Amir Ali; Zhang, Jeffrey
作者单位：Princeton University
摘要：We prove that unlessP=NP there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known Frank-Wolfe type theorems imply that exactly one of two cases can occur: either the optimal value is attained on every instance, or it is strongly NP-...
-
作者：D'Ambrosio, Claudia; Liberti, Leo; Poirion, Pierre-Louis; Vu, Ky
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; RIKEN; FPT University
摘要：Random projections map a set of points in a high dimensional space to a lower dimensional one while approximately preserving all pairwise Euclidean distances. Although random projections are usually applied to numerical data, we show in this paper that they can be successfully applied to quadratic programming formulations over a set of linear inequality constraints. Instead of solving the higher-dimensional original problem, we solve the projected problem more efficiently. This yields a feasib...
-
作者：Graf, Lukas; Harks, Tobias; Sering, Leon
作者单位：Technical University of Berlin
摘要：We study dynamic network flows and introduce a notion of instantaneous dynamic equilibrium (IDE) requiring that for any positive inflow into an edge, this edge must lie on a currently shortest path towards the respective sink. We measure current shortest path length by current waiting times in queues plus physical travel times. As our main results, we show: existence and constructive computation of IDE flows for multi-source single-sink networks assuming constant network inflow rates, finite t...
-
作者：Menickelly, Matt; Wild, Stefan M.
作者单位：United States Department of Energy (DOE); Argonne National Laboratory
摘要：We develop an algorithm for minimax problems that arise in robust optimization in the absence of objective function derivatives. The algorithm utilizes an extension of methods for inexact outer approximation in sampling a potentially infinite-cardinality uncertainty set. Clarke stationarity of the algorithm output is established alongside desirable features of the model-based trust-region subproblems encountered. We demonstrate the practical benefits of the algorithm on a new class of test pro...
