License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.568
URN: urn:nbn:de:0030-drops-49429
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4942/
Kolliopoulos, Stavros G. ;
Moysoglou, Yannis
Extended Formulation Lower Bounds via Hypergraph Coloring?
Abstract
Exploring the power of linear programming for combinatorial optimization
problems has been recently receiving renewed attention after a series of
breakthrough impossibility results. From an algorithmic perspective, the
related questions concern whether there are compact formulations even for problems that are known to admit polynomial-time algorithms.
We propose a framework for proving lower bounds on the size of extended
formulations. We do so by introducing a specific type of extended relaxations that we call product relaxations and is motivated by the study of the Sherali-Adams (SA) hierarchy. Then we show that for every approximate extended formulation of a polytope P, there is a product relaxation that has the same size and is at least as strong. We provide a methodology for proving lower bounds on the size of approximate product relaxations by lower bounding the chromatic number of an underlying hypergraph, whose vertices correspond to gap-inducing vectors.
We extend the definition of product relaxations and our methodology to mixed integer sets. However in this case we are able to show that mixed product relaxations are at least as powerful as a special family of extended formulations. As an application of our method we show an exponential lower bound on the size of approximate mixed product relaxations for the metric capacitated facility location problem Cfl, a problem which seems to be intractable for linear programming as far as constant-gap compact formulations are concerned. Our lower bound implies an unbounded integrality gap for Cfl at Theta({N}) levels of the universal SA hierarchy which is independent of the starting relaxation; we only require that the starting relaxation has size 2^o(N), where N is the number of facilities in the instance. This proof yields the first such tradeoff for an SA procedure that is independent of the initial relaxation.
BibTeX - Entry
@InProceedings{kolliopoulos_et_al:LIPIcs:2015:4942,
author = {Stavros G. Kolliopoulos and Yannis Moysoglou},
title = {{Extended Formulation Lower Bounds via Hypergraph Coloringl}},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages = {568--581},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-78-1},
ISSN = {1868-8969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4942},
URN = {urn:nbn:de:0030-drops-49429},
doi = {10.4230/LIPIcs.STACS.2015.568},
annote = {Keywords: linear programming, extended formulations, inapproximability, facility location}
}
|
Keywords: |
|
linear programming, extended formulations, inapproximability, facility location |
|
Collection: |
|
32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
26.02.2015 |
