Source-linked AI summary
LP-Based Algorithms for Capacitated Facility Location
Hyung-Chan An, Mohit Singh, Ola Svensson
TL;DR
Capacitated facility location lacked a strong, algorithmically useful LP relaxation with a constant guarantee, despite constant-factor local-search algorithms. The paper builds a multi-commodity-flow relaxation informed by matching theory and proves a 288-approximation relative to its LP optimum. It resolves a stated open problem while leaving polynomial-time separation unresolved.
Problem
CFL lacked a known strong, algorithmically useful LP relaxation with any constant performance guarantee, despite constant-factor local-search algorithms.
Source: §1 · p. 2Method
The paper formulates a multi-commodity-flow relaxation using matching insights and proves its gap with a polynomial-time LP-rounding algorithm.
Source: §1.1 · pp. 3, 5Results
288-approximation: the algorithm's output cost is at most 288 times the optimal cost of MFN-LP, and the relaxation has a constant integrality gap.
Source: §1.1 · p. 3, §3 · p. 12Takeaways & Limitations
The result resolves Open Problem 5 and opens the possibility of LP-based approaches to CFL and related problems.
Source: §1.1 · p. 5The authors do not know whether the relaxation can be separated in polynomial time.
Source: §1.1 · p. 4
Abstract
from arXiv · showhide
Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general capacitated facility location problem. In fact, all of the known algorithms with good performance guarantees were based on a single technique, local search, and no linear programming relaxation was known to efficiently approximate the problem. In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. We demonstrate that the fundamental theories of multi-commodity flows and matchings provide key insights that lead to the strong relaxation. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding.
1 Introduction
Capacitated facility location had constant-factor local-search algorithms but no known LP relaxation with a constant performance guarantee. The paper presents a constant-gap relaxation and an LP-rounding algorithm using multi-commodity flows and matching theory.
1.1 Our Contributions
- MFN-LP has a constant integrality gap, and polynomial-time rounding returns a CFL solution within a constant factor of the LP optimum, resolving Open Problem 5.Source: §1.1 · p. 3
- Because saturated facilities can block residual assignments, the relaxation allows alternating paths that undo partial assignments through multi-commodity flow.Source: §1.1 · pp. 3–4
- The rounding procedure either rounds a given fractional solution within a constant factor or identifies a violated inequality, without solving the LP to optimality.Source: §1.1 · p. 4
- Polynomial-time separation remains unknown, and the exact integrality gap is open; the current analysis is unlikely to improve on a 5-approximation.Source: §1.1 · pp. 3–4
- The rounding opens facilities with large fractional opening values, then uses partial assignments and multi-commodity flows to route remaining clients.Source: §1.1 · pp. 3, 5
1.2 Further Related Work
- Earlier constant-factor CFL algorithms used local search, with a 5-approximation for general capacities; soft-capacitated variants are also studied.Source: §1.2 · p. 6
2 Multi-commodity Flow Relaxation
MFN-LP requires each valid partial assignment to extend through a multi-commodity flow using assignment and opening variables. Its flow constraints exploit matching structure, support fixed-assignment separation, and strengthen familiar formulations.
2 Multi-commodity Flow Relaxation
- For every valid partial assignment, MFN-LP requires a multi-commodity flow routing each client's unassigned demand using assignment and opening variables.A facility's flow capacity limits total remaining demand and client-specific demand.Source: §2 · pp. 7–8
2.1 Integral Partial Assignments and Separation
- Feasibility for all valid partial assignments is equivalent to feasibility for integral assignments, by integrality of the b-matching polytope.The proof expresses a fractional assignment as a convex combination of integral assignments and combines their feasible flows.Source: §2.1 · pp. 8–9
- For fixed g, an infeasible flow yields a polynomial-time violated valid inequality with coefficients represented using polynomially many bits.The paper notes that polynomial-time separation for the entire MFN-LP is not known, but fixed-g separation suffices for its algorithmic use.Source: §2.1 · p. 9
2.2 MFN-LP is a Relaxation of the Capacitated Facility Location Problem
- MFN-LP is a relaxation: matchings and alternating paths construct feasible flows for integral facility-location solutions.The construction verifies flow capacities and demands; the authors note that the commodity-specific capacity argument uses integral openings.Source: §2.2 · pp. 9–10
2.3 Comparing MFN-LP to Standard LP and Knapsack-Cover Inequalities
- MFN-LP is no weaker than the standard assignment LP, and an example gives the standard LP an unbounded integrality gap as n grows.In the zero-distance example, the standard LP costs 1/(n+1) while the optimum costs 1; the example's knapsack-cover inequalities are implied by the new relaxation.Source: §2.3 · pp. 11–12
3 Approximation Algorithm
The section develops a 288-approximation for capacitated facility location by using capacity-feasible flow exchanges to improve allocations and obtain a semi-integral solution or a violated inequality. It bounds the semi-integral solution’s cost by eight times the LP solution cost, then rounds that solution to an integral one.
3 Approximation Algorithm
- The algorithm returns a solution costing at most 288 times the optimal cost of MFN-LP.The guarantee follows from an 8-factor conversion to a semi-integral solution and a 36-factor rounding to an integral solution.Source: §3 · p. 12, §3.2 · p. 13
3.1 Semi-Integral Solutions: Definition and Rounding
- A semi-integral solution can be rounded in polynomial time to an integral solution costing at most 36 times as much.Facilities are partitioned into fully open and small-opening sets; the residual instance is rounded using the (18, 2)-bicriteria algorithm of Abrams et al..Source: §3.1 · pp. 12–13
3.2 Finding a Semi-Integral Solution or a Violated Inequality
- For a fractional candidate, the algorithm either returns a violated MFN-LP inequality or constructs a semi-integral solution costing at most 8 times the candidate cost.It rounds large opening variables and uses a maximum fractional b-matching to form a partial assignment; if the associated flow network is feasible, a feasible flow can be chosen to send at least half of each client's demand to small-opening facilities.Source: §3.2 · pp. 13–15
3.2.1 Proof of Lemma 3.6: Existence of a Nice Multi-Commodity Flow
- The flow argument establishes that a feasible flow can send at least half of each client's demand to small-opening facilities.The proof considers the clients sending the smallest fraction of demand to those facilities and modifies flow paths to increase that fraction or reduce the number of clients attaining it, yielding a flow with the required bound.Source: §3.2 · p. 15, §3.2.1 · p. 17
- Exchanging an arbitrarily small flow amount between paths preserves demand constraints and can satisfy capacity constraints.The exchange reroutes flow between the same source–sink pairs; the two newly used arcs have sufficient capacity for a sufficiently small change.Source: §3.2.1 · p. 17
- The exchange can make both commodities send more than an α fraction of their demands to S, decreasing |J| or increasing α.The modification also avoids reintroducing nodes js for j ∈ D \ DH, so Claim 3.8 remains applicable.Source: §3.2.1 · p. 18
3.2.2 Proof of Lemma 3.7: Bounding the Cost of the Semi-integral Solution
- The semi-integral solution has cost at most 8c(x⋆, y⋆).The proof bounds facility-opening variables by 4y⋆ and assignment cost to facilities in I by less than twice the fractional assignment cost.Source: §3.2.2 · pp. 18–19
A Formal Proof of Separation Lemma
The separation argument uses multi-commodity-flow feasibility to produce a polynomially representable inequality when the network is infeasible. A polynomial-time separation procedure finds a certificate through an LP solvable with Dijkstra’s algorithm.
A Formal Proof of Separation Lemma
- When MFN(g⋆, x⋆, y⋆) is infeasible, the lemma finds a violated inequality valid for MFN-LP, with coefficient bit length polynomial in |F|, |D|, and log U.U is the maximum facility capacity.Source: A Formal Proof of Separation Lemma · p. 23
- If a fractional g⋆ makes the network infeasible, a polynomial-size convex decomposition into integral b-matchings yields an integral matching that also makes it infeasible.The proof then assumes g⋆ is integral.Source: A Formal Proof of Separation Lemma · p. 23
- The network’s underlying digraph is independent of g, x, and y; these variables determine arc capacities, while client demands depend only on g.The proof denotes arc capacities by ca(g, x, y) and client demands by dj(g).Source: A Formal Proof of Separation Lemma · p. 23
- The separation oracle finds a certificate (z⋆, l⋆) by solving an LP, which is polynomial-time solvable using Dijkstra’s algorithm.The proof chooses an extreme-point solution to that LP.Source: A Formal Proof of Separation Lemma · p. 23
- The certificate yields a linear inequality valid for MFN-LP but violated by (x⋆, y⋆), and its coefficients have polynomial bit length in |F|, |D|, and log U.The proof bounds the coefficients using the extreme-point certificate and the linear capacity and demand functions.Source: A Formal Proof of Separation Lemma · p. 24
B Rounding a Semi-Integral Solution to an Integral Solution
Lemma 3.2 converts a semi-integral solution into an integral solution in polynomial time at cost at most 36 times the original. The rounding handles the residual facilities through a general-demand LP, then uses b-matching to produce an integral assignment without increasing assignment cost.
B Rounding a Semi-Integral Solution to an Integral Solution
- A semi-integral solution can be rounded in polynomial time to an integral solution whose cost is at most 36 times the original.The resulting assignment and facility openings form a feasible capacitated facility location solution.Source: B Rounding a Semi-Integral Solution to… · pp. 24–26
- The residual facilities induce client demands equal to the assignment fractions sent to those facilities, yielding an instance of facility location with general demands.LPdemand is the standard LP relaxation for that general-demand problem.Source: B Rounding a Semi-Integral Solution to… · p. 24
- Applying the general-demand rounding algorithm makes the residual opening variables integral while allowing capacities to double and increasing cost by at most a factor of 18.The proof applies the result to the residual solution with opening variables doubled, yielding a residual cost bound of 36 times its original cost.Source: B Rounding a Semi-Integral Solution to… · pp. 24–25
- A minimum-cost b-matching assigns clients to the opened facilities, and its integral assignment costs no more than the feasible fractional assignment.The matching graph connects clients to opened facilities with edge costs cij.Source: B Rounding a Semi-Integral Solution to… · p. 25, Figure 6 · p. 25