2026-07-25T06:21:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4704 2024-03-06T10:35:16Z ddc:004 open_access

Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location Kolliopoulos, Stavros G. Moysoglou, Yannis Approximation Algorithms Linear Programming 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stavros G. Kolliopoulos and Yannis Moysoglou 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.297 urn:nbn:de:0030-drops-47046 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.297 eng https://creativecommons.org/licenses/by/3.0/legalcode