Approximation Algorithms for Minimum-Load k-Facility Location

Authors Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad R. Salavatipour, Chaitanya Swamy



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.17.pdf
  • Filesize: 0.62 MB
  • 17 pages

Document Identifiers

Author Details

Sara Ahmadian
Babak Behsaz
Zachary Friggstad
Amin Jorati
Mohammad R. Salavatipour
Chaitanya Swamy

Cite AsGet BibTex

Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad R. Salavatipour, and Chaitanya Swamy. Approximation Algorithms for Minimum-Load k-Facility Location. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 17-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.17

Abstract

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 (MLkFL) 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' of k facilities, and assign each client j to a facility f(j) in F' so as to minimize maximum, over all facilities in F', of the sum of distances of clients j assigned to F' to F'. We call this sum the load of facility f. This problem was studied under the name of min-max star cover in [6, 2], who (among other results) gave bicriteria approximation algorithms for MLkFL for when F = C. MLkFL is rather poorly understood, and only an O(k)-approximation is currently known for MLkFL, even for line metrics. Our main result is the first polynomial time approximation scheme (PTAS) for MLkFL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that MLkFL is strongly NP-hard on line metrics. We also devise a quasi-PTAS for MLkFL on tree metrics. MLkFL turns out to be surprisingly challenging even on line metrics, and resilient to attack by the 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 MLkFL. 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 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.
Keywords
  • approximation algorithms
  • min-max star cover
  • facility location
  • line metrics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. H.-C. An, A. Bhaskara, C. Chekuri, S. Gupta, V. Madan, and O. Svensson. Centrality of trees for capacitated k-center. In Proceedings of APPROX, 2014. Google Scholar
  2. E.M. Arkin, R. Hassin, and A. Levin. Approximations for minimum and min-max vehicle routing problems. Journal of Algorithms, 59(1):1-18, 2006. Google Scholar
  3. V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3):544-562, 2004. Google Scholar
  4. M. Charikar, S. Guha, É. Tardos, and D. B. Shmoys. A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1):129-149, 2002. Google Scholar
  5. M. Cygan, M. T. Hajiaghayi, and S. Khuller. Lp rounding for k-centers with non-uniform hard capacities. Arxiv preprint arXiv:1208.3054, 2012. Google Scholar
  6. G. Even, N. Garg, J. Könemann, R. Ravi, and A. Sinha. Covering graphs using trees and stars. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 24-35, 2003. Google Scholar
  7. D. Hochbaum and D. Shmoys. A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM Journal on Computing, 17:539-551, 1988. Google Scholar
  8. K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani. Greedy facility location algorithms analyzed using dual-fitting with factor-revealing lp. Journal of the ACM, 50(6):795-824, 2003. Google Scholar
  9. K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM, 48(2):274-296, 2001. Google Scholar
  10. A. Jorati. Approximation algorithms for min-max vehicle routing problems. Master’s thesis, University of Alberta, Department of Computing Science, 2013. Google Scholar
  11. M. R. Khani and M. R. Salavatipour. Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. In APPROX, 2011. Google Scholar
  12. S. Li and O. Svensson. Approximating k-median via pseudo-approximation. In Symposium on Theory of Computing (STOC), 2013. Google Scholar
  13. P. Mirchandani and R. Francis, editors. Discrete location theory. Jown Wiley and Sons, 1990. Google Scholar
  14. H. Nagamochi and K. Okada. Approximating the minmax rooted-tree cover in a tree. Information Processing Letters, 104(5):173-178, 2007. Google Scholar
  15. R. Ravi. Workshop on Flexible Network Design, 2012. URL: http://fnd2012.mimuw.edu.pl/qa/index.php?qa=4&qa_1=approximating-star-cover-problems.
  16. D. B. Shmoys. The design and analysis of approximation algorithms: facility location as a case study. In S. Hosten, J. Lee, and R. Thomas, editors, Trends in Optimization, AMS Proceedings of Symposia in Applied Mathematics 61, pages 85-97. 2004. Google Scholar
  17. D. B. Shmoys and E. Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62(3):461-474, 1993. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail