-
作者：Bienstock, Daniel; Chen, Chen; Munoz, Gonzalo
作者单位：Columbia University; University System of Ohio; Ohio State University; Universidad de O'Higgins
摘要：This paper introduces cutting planes that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set S boolean AND P, where S is a closed set, and P is a polyhedron. Given an oracle that provides the distance from a point to S, we construct a pure cutting plane algorithm which is shown to converge if the initial relaxation is a polyhedron. These cuts are generated from convex forbidd...
-
作者：Hosseini, Reshad; Sra, Suvrit
作者单位：University of Tehran; Institute for Research in Fundamental Sciences IPM; Massachusetts Institute of Technology (MIT)
摘要：We consider maximum likelihood estimation for Gaussian Mixture Models (Gmm s). This task is almost invariably solved (in theory and practice) via the Expectation Maximization (EM) algorithm. EM owes its success to various factors, of which is its ability to fulfill positive definiteness constraints in closed form is of key importance. We propose an alternative to EM grounded in the Riemannian geometry of positive definite matrices, using which we cast Gmm parameter estimation as a Riemannian o...
-
作者：Naegele, Martin; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Minimum cut problems are among the most classical problems in Combinatorial Optimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global mininmum cuts, minimum s-t cuts, and minimum odd cuts in undirected graphs. We study a problem class that can be seen to generalize the above variants, namely finding congruency-constrained minimum cuts, i.e., we consider cuts whose number of vertices is congruent to r modulo m, for some integers...
-
作者：Chekuri, Chandra; Quanrud, Kent; Torres, Manuel R.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Purdue University System; Purdue University; University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider approximation algorithms for packing integer programs (PIPs) of the form max[ (c, x) Ax < b, x E {0, 1r} where A, h and c are nonnegative. We let W = mini, / kJ denote the width of A which is at least 1. Previous work by Bansal et al. (Theory Comput 8(24):533-565, 2012) obtained an Q /11,,) approximation ratio A6 where A() is the maximum number of nonzeroes in any column of A (in other words the 4 -column sparsity of A). They raised the question of obtaining approximation ratios ba...
-
作者：Berndt, Sebastian; Jansen, Klaus; Klein, Kim-Manuel
作者单位：University of Kiel; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of ...
-
作者：Paat, Joseph; Weismantel, Robert; Weltge, Stefan
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Technical University of Munich
摘要：A classic result of Cook et al. (Math. Program. 34:251-264, 1986) bounds the distances between optimal solutions of mixed-integer linear programs and optimal solutions of the corresponding linear relaxations. Their bound is given in terms of the number of variables and a parameter Delta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt}...
-
作者：Kurpisz, Adam; Leppanen, Samuli; Mastrolilli, Monaldo
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Universita della Svizzera Italiana
摘要：We introduce a method for proving Sum-of-Squares (SoS)/Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of well-behaved univariate polynomial inequalities. We illustrate the technique on two problems, one unconstrained and the other with constraints. More precisely, we give a short elementary proof of Grigoriev/Laurent lower bound for...
-
作者：Linhares, Andre; Olver, Neil; Swamy, Chaitanya; Zenklusen, Rico
作者单位：University of Waterloo; University of London; London School Economics & Political Science; Centrum Wiskunde & Informatica (CWI); Vrije Universiteit Amsterdam; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited violations of the constraints of the other matroids. In addition to the classical steps of iterative relaxation approaches, we iterativelyrefineinvolved matroid constraints. This leads to more restrictive constraint systems whose structure can be exploited to prove the existence of constraints that c...
-
作者：Philpott, A. B.; Wahid, F.; Bonnans, J. F.
作者单位：University of Auckland; Inria
摘要：Mixed integer dynamic approximation scheme (MIDAS) is a new sampling-based algorithm for solving finite-horizon stochastic dynamic programs with monotonic Bellman functions. MIDAS approximates these value functions using step functions, leading to stage problems that are mixed integer programs. We provide a general description ofMIDAS, and prove its almost-sure convergence to a 2T e-optimal policy for problems with T stages when the Bellman functions are known to be monotonic, and the sampling...
-
作者：Luke, D. Russell; Teboulle, Marc; Thao, Nguyen H.
作者单位：University of Gottingen; Tel Aviv University; Delft University of Technology; Can Tho University
摘要：We present necessary conditions for monotonicity of fixed point iterations of mappings that may violate the usual nonexpansive property. Notions of linear-type monotonicity of fixed point sequences-weaker than Fejer monotonicity-are shown to imply metric subregularity. This, together with the almost averaging property recently introduced by Luke et al. (Math Oper Res, 2018. 10.1287/moor.2017.0898), guarantees linear convergence of the sequence to a fixed point. We specialize these results to t...
