Approximation Algorithms for Minimum-Load k-Facility Location
| Autor: | Mohammad R. Salavatipour, Zachary Friggstad, Amin Jorati, Sara Ahmadian, Babak Behsaz, Chaitanya Swamy |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
000 Computer science knowledge general works Heuristic (computer science) Computer science Approximation algorithm 0102 computer and information sciences 02 engineering and technology Function (mathematics) Star (graph theory) 01 natural sciences Upper and lower bounds Polynomial-time approximation scheme Facility location problem Mathematics (miscellaneous) 010201 computation theory & mathematics Computer Science 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Integer (computer science) |
| DOI: | 10.4230/lipics.approx-random.2014.17 |
| Popis: | We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimum-load k-facility location (ML k FL) problem, which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k ≥ 0. Assigning client j to a facility f incurs a connection cost d ( f , j ). The goal is to open a set F ⊆ F of k facilities and assign each client j to a facility f ( j )∈ F so as to minimize max f ∈ F ∑ j ∈ C : f ( j )= f d ( f , j ); we call ∑ j ∈ C : f ( j )= f d ( f , j ) the load of facility f . This problem was studied under the name of min-max star cover in References [3, 7], who (among other results) gave bicriteria approximation algorithms for ML k FL for when F = C . ML k FL is rather poorly understood, and only an O ( k )-approximation is currently known for ML k FL, even for line metrics . Our main result is the first polytime approximation scheme (PTAS) for ML k FL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that ML k FL is strongly NP -hard on line metrics. We also devise a quasi-PTAS for ML k FL on tree metrics. ML k FL turns out to be surprisingly challenging even on line metrics and resilient to attack by a variety of techniques that have been successfully applied to facility-location problems. For instance, we show that (a) even a configuration-style LP-relaxation has a bad integrality gap and (b) a multi-swap k -median style local-search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack ML k FL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near-optimal solution possessing some nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding of the problem and argue that a MILP-solution minimizing a certain potential function possesses the desired structure and then use a rounding algorithm for the generalized-assignment problem to “transfer” this structure to the rounded integer solution. Complementing this, we show that these structural properties enable one to find such a structured solution via dynamic programming. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|