LP-Based Algorithms for Capacitated Facility Location
This research presents LP-Based Algorithms for the Capacitated Facility Location problem, aiming to choose facilities to open and assign clients to these facilities efficiently. It discusses solving the problem using metric costs, client and facility sets, capacities, and opening costs. The research also covers a successful specialized case regarding uncapacitated facility location problems and different approximation algorithms used in such scenarios, combining linear program rounding and primal-dual algorithms to achieve various approximation ratios.
- LP-Based Algorithms
- Capacitated Facility Location
- Approximation Algorithms
- Linear Programming
- Primal-Dual
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
LP-Based Algorithms for Capacitated Facility Location Hyung-Chan An July 29, 2013 Joint work with Mohit Singh and Ola Svensson
Capacitated facility location problem Given a metric cost c on D: set of clients F: set of facilities 2 12 3 10
Capacitated facility location problem Given a metric cost c on D: set of clients F: set of facilities Ui: capacity of i F oi: opening cost of i F 3 5 2 1 3 20
Capacitated facility location problem Given a metric cost c on D: set of clients F: set of facilities Ui: capacity of i F oi: opening cost of i F 3 5 2 1 3 20 Want: Choose S F to open
Capacitated facility location problem Given a metric cost c on D: set of clients F: set of facilities Ui: capacity of i F oi: opening cost of i F 3 5 2 1 3 20 Want: Choose S F to open Assign every client to an open facility f : D S Capacities satisfied
Capacitated facility location problem Given a metric cost c on D: set of clients F: set of facilities Ui: capacity of i F oi: opening cost of i F 2 2 5 2 5 3 2 20 Want: Choose S F to open Assign every client to an open facility f : D S Capacities satisfied Minimize i S oi + j D cj,f(j) = (20 + 5) + (2 + 2 + 2 + 5 + 2 + 3)
Successful special case Uncapacitated facility location problem Ui= i NP-hard to approximate better than 1.463 [Guha & Khuller 1999] [Sviridenko] 1.488-approximation algorithm [Li 2011]
Successful special case Uncapacitated facility location problem Ui= i NP-hard to approximate better than 1.463 [Guha & Khuller 1999] [Sviridenko] 1.488-approximation algorithm [Li 2011] Combining a linear program(LP)-rounding algorithm with a primal-dual algorithm LP-rounding 3.16-approximation [Shmoys, Tardos, Aardal 1997], LP-rounding & greedy 2.41- approximation [Guha & Khuller 1999], LP-rounding 1.74-approximation [Chudak & Shmoys 1999], primal-dual 3-approximation [Jain & Vazirani 2001], combining 1.73-approximation [Charikar & Guha 1999], primal-dual 1.61-approximation [Jain, Mahdian, Markakis, Saberi, Vazirani 2003], LP-rounding 1.59- approximation [Sviridenko 2002], primal-dual 1.52-approximation [Mahdian, Ye, Zhang 2006], combining 1.5-approximation algorithm [Byrka & Aardal 2010]
The Question Can we use these LP-based techniques to solve the capacitated facility location problem?
The Question Can we use these LP-based techniques to solve the capacitated facility location problem? All known approximation algorithms based on local search [Bansal, Garg, Gupta 2012], [Pal, Tardos, Wexler 2001], [Korupolu, Plaxton, Rajaraman 2000] 5-approximation
The Question Can we use these LP-based techniques to solve the capacitated facility location problem? Rich toolkit of algorithmic techniques
The Question Can we use these LP-based techniques to solve the capacitated facility location problem? Rich toolkit of algorithmic techniques Per-instance performance guarantee Application to related problems One of the ten Open Problems selected by the textbook of Williamson and Shmoys
The Question Can we use these LP-based techniques to solve the capacitated facility location problem? Why is this hard? Standard LP relaxation fails to bound the optimum within a reasonable factor Relaxed problems: uncapacitated problem, capacities can be violated [Abrams, Meyerson, Munagala, Plotkin 2002], facilities can be opened multiple times [Shmoys, Tardos, Aardal 1997], [Jain, Vazirani 2001], opening costs are uniform [Levi, Shmoys, Swamy 2012]
The Question Can we use these LP-based techniques to solve the capacitated facility location problem? Why is this hard? Standard LP relaxation fails to bound the optimum within a reasonable factor No LP relaxation known that is algorithmically amenable
Main result Theorem There is a good LP: its optimum is within a constant factor of the true optimum. In particular, there is a poly-time algorithm that finds a solution whose cost is within a constant factor of the LP optimum.
Our relaxation Standard LP rewritten i F i F, j D xij=1 if j is assigned to i, 0 if not Consider a multicommodity flow network: arc (j, i) of capacity xij j D is a source of commodity j with demand 1 i F is a sink of commodity-oblivious capacity yi Ui commodity-specific capacity yi 1 3 y=1 yi=1 if open, 0 if not 2 y=0 3 y=1 All shown arcs are of capacity 1; others 0.
Our relaxation Standard LP rewritten i F i F, j D xij=1 if j is assigned to i, 0 if not Consider a multicommodity flow network: arc (j, i) of capacity xij j D is a source of commodity j with demand 1 i F is a sink of commodity-oblivious capacity yi Ui commodity-specific capacity yi 1 Minimize i F oiyi + i F, j D cijxij subject to the flow network defined by (x, y) is feasible xij, yi {0, 1} 3 y=1 yi=1 if open, 0 if not 2 y=0 3 y=1 All shown arcs are of capacity 1; others 0.
Our relaxation Standard LP rewritten i F i F, j D xij=1 if j is assigned to i, 0 if not Consider a multicommodity flow network: arc (j, i) of capacity xij j D is a source of commodity j with demand 1 i F is a sink of commodity-oblivious capacity yi Ui commodity-specific capacity yi 1 Minimize i F oiyi + i F, j D cijxij subject to the flow network defined by (x, y) is feasible xij, yi [0, 1] 3 y=1 yi=1 if open, 0 if not 2 y=0 3 y=1 All shown arcs are of capacity 1; others 0.
Our relaxation 3 Consider arbitrary partial assignment g : D F Suppose that clients are assigned according to g (x, y) should still give a feasible solution for the remaining clients: i.e., the flow network should still be feasible when only the remaining clients have demand of 1 commodity-oblivious capacity of i is yi (Ui -|g-1(i)|) In similar spirit as knapsack-cover inequalities [Wolsey 1975] [Carr, Fleischer, Leung, Phillips 2000] 2 3 x 32 y=1 x 21 y=0 3 y=1 LP constraint: the flow network defined by (g, x, y) is feasible for allg Is this really a relaxation? All shown arcs are of capacity 1; others 0.
Our relaxation 3 Is this really a relaxation? No. The only facility adjacent from remaining clients has 1 0 = 0 commodity-oblivious capacity 2 3 Introduce backward edges corresponding to g Now flows can be routed along alternating paths 3 y=1 2 y=0 x 30 y=1 All shown arcs are of capacity 1; others 0.
Our relaxation Minimize subject to i F oiyi + i F, j D cijxij MFN(g, x, y) is feasible partial assignment g where MFN(g, x, y) is a multicommodity flow network with arc (j, i) of capacity xij, arc (i, j) of capacity 1 if g assigns j to i, j D is a source of commodity j with demand 1 if not assigned by g, i F is a sink of commodity-oblivious capacity yi (Ui -|g-1(i)|) and commodity-specific capacity yi 1.
Our relaxation Minimize subject to i F oiyi + i F, j D cijxij MFN(g, x, y) is feasible partial assignment g Automatically embraces Standard LP when g is the empty partial function Knapsack-cover inequalities Can be separated with respect to any given g Algorithm uses feasibility of MFN(g, x, y) for a single g Invoke standard techniques [Carr, Fleischer, Leung, Phillips 2000], [Levi, Lodi, Sviridenko 2007]
LP-rounding algorithm I {i F | y*i > }, S {i F | y*i }; open I Can afford it Choose a partial assignment g : D I For each client j assigned by g, assign j in the same way Remaining clients are to be assigned to S Lemma We can choose a partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where all flow is drained at S.
LP-rounding algorithm Remaining clients are to be assigned to S MFN(g, x*, y*) remains feasible even when restricted to S MFN( , x*, y*) is feasible when restricted to remaining clients i.e., it is feasible for the standard LP Commodity-oblivious capacity of i S is yi Ui Ui / 2 Capacity constraints are not tight Can use Abrams et al. s algorithm based on the standard LP Finds 18-approx soln where capacities are violated by 2 Lemma We can choose a partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where all flow is drained at S.
LP-rounding algorithm Can use Abrams et al. s algorithm based on the standard LP Finds 18-approx soln where capacities are violated by 2 A 288-approximation algorithm Obvious improvements, but perhaps not leading to 5 Determination of integrality gap remains open Lemma We can choose a fractional partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where at least half of each commodity s flow is drained at S.
LP-rounding algorithm Lemma We can choose a partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where all flow is drained at S.
LP-rounding algorithm 2 1 1 2 2 y=1 1 Simplifying assumption For each client j, all its incident edges in the support have equal costs 1/3 1/3 1/3 1 y=1 y=1 1/2 y=1/2 1/2 1/2 y=1/2 1/2 Support of x* := { (i, j) | x*ij > 0 } x-values shown on edges Lemma We can choose a partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where all flow is drained at S.
LP-rounding algorithm 2 1 1 2 2 Simplifying assumption For each client j, all its incident edges in the support have equal costs Support of x* := { (i, j) | x*ij > 0 } Lemma We can choose a partial assignment g s.t. g is cheap MFN(g, x*, y*) has a feasible flow where all flow is drained at S.
LP-rounding algorithm 2 1 1 2 2 I {i F | y*i > }, S {i F | y*i }; open I Find a maximum bipartite matching g on the support of x* j D is matched at most once i I is matched up to Ui times i S is not matched I S
LP-rounding algorithm 2 1 1 2 2 I {i F | y*i > }, S {i F | y*i }; open I Find a maximum bipartite matching g on the support of x* j D is matched at most once i I is matched up to Ui times i S is not matched I S
LP-rounding algorithm 2 1 1 2 2 I {i F | y*i > }, S {i F | y*i }; open I Find a maximum bipartite matching g on the support of x* j D is matched at most once i I is matched up to Ui times i S is not matched Now we observe MFN(g, x*, y*) There exists no path from a remaining client to a facility in Ithat is undermatched I S 2 1 1 2 2 I S
LP-rounding algorithm 2 1 1 2 2 I {i F | y*i > }, S {i F | y*i }; open I Find a maximum bipartite matching g on the support of x* j D is matched at most once i I is matched up to Ui times i S is not matched Now we observe MFN(g, x*, y*) There exists no path from a remaining client to a facility in Ithat is undermatched Fully matched facility has zero capacity All flow drained at S I S x x x 21 10 10 2 2 I S
Main result Theorem There is a good LP: its optimum is within a constant factor of the true optimum. In particular, there is a poly-time algorithm that finds a solution whose cost is within a constant factor of the LP optimum.
The Question Can we use LP-based techniques to solve the capacitated facility location problem? Yes! Can we use other LP-based techniques with our new relaxation? Can we apply these results to related problems? Can we improve our integrality gap bounds?
