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

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 program-ming 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 Ω(n) levels of the Sherali-Adams hierarchy have an unbounded gap, partially answering an open question of [27, 6]. 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 [1] has also an unbounded gap. This disproves a long-standing conjecture of [24]. 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