License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.297
URN: urn:nbn:de:0030-drops-47046
URL: http://drops.dagstuhl.de/opus/volltexte/2014/4704/
Go to the corresponding LIPIcs Volume Portal


Kolliopoulos, Stavros G. ; Moysoglou, Yannis

Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location

pdf-format:
21.pdf (0.5 MB)


Abstract

Metric facility location is a well-studied problem for which linear programming methods have been used with great success in deriving approximation algorithms. The capacity-constrained generalizations, such as capacitated facility location (CFL) and lower-bounded facility location (LBFL), have proved notorious as far as LP-based approximation is concerned: while there are local-search-based constant-factor approximations, there is no known linear relaxation with constant integrality gap. According to Williamson and Shmoys devising a relaxation-based approximation for CFL is among the top 10 open problems in approximation algorithms. This paper advances significantly the state-of-the-art on the effectiveness of linear programming for capacity-constrained facility location through a host of impossibility results for both CFL and LBFL. We show that the relaxations obtained from the natural LP at Omega(n) levels of the Sherali-Adams hierarchy have an unbounded gap, partially answering an open question from the literature. Here, n denotes the number of facilities in the instance. Building on the ideas for this result, we prove that the standard CFL relaxation enriched with the generalized flow-cover valid inequalities has also an unbounded gap. This disproves a long-standing conjecture of Levi et al. We finally introduce the family of proper relaxations which generalizes to its logical extreme the classic star relaxation and captures general configuration-style LPs. We characterize the behavior of proper relaxations for CFL and LBFL through a sharp threshold phenomenon.

BibTeX - Entry

@InProceedings{kolliopoulos_et_al:LIPIcs:2014:4704,
  author =	{Stavros G. Kolliopoulos and Yannis Moysoglou},
  title =	{{Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{297--312},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4704},
  URN =		{urn:nbn:de:0030-drops-47046},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.297},
  annote =	{Keywords: Approximation Algorithms, Linear Programming, Facility Location}
}

Keywords: Approximation Algorithms, Linear Programming, Facility Location
Seminar: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 02.09.2014


DROPS-Home | Fulltext Search | Imprint Published by LZI