Can I read Sherali-Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained Facility Location on EtoBox?

Sherali-Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained Facility Location by Kolliopoulos, Stavros G.; Moysoglou, Yannis is a scholarly article available to read on EtoBox.

What is Sherali-Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained Facility Location about?

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 of \cite{LiS13, AnBS13}. 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 th

Author

Kolliopoulos, Stavros G.; Moysoglou, Yannis

Published

2013

Language

EN