Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present new approximation algorithms for it. This problem is a generalization of the classical facility location problem where each facility can serve at most u units of demand and each client must be served by exactly one facility. This problem is motivated by its applications in many practical problems including supply chain problems of indivisible goods (Verter in Foundations of location analysis, chapter 2. International series in operations research and management science. Springer, Berlin, 2011) and the assignment problem in the content distribution networks (Bateni and Hajiaghayi in Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, pp 805–814, 2009). While there are several approximation algorithms for the soft capacitated version of this problem (in which one can open multiple copies of each facility) or the splittable version (in which the demand of each client can be divided to be served by multiple open facilities), there are very few results for the UCFLP. It is known that it is NP-hard to approximate this problem within any factor without violating the capacities. So we consider bicriteria \((\alpha ,\beta )\)-approximations where the algorithm returns a solution whose cost is within factor \(\alpha \) of the optimum and violates the capacity constraints within factor \(\beta \). Shmoys et al. (Proceedings of the twenty-ninth annual ACM symposium on theory of computing, pp 265–274, 1997) were the first to consider this problem and gave a (9, 4)-approximation. Later results imply (O(1), 2)-approximations, however, no constant factor approximation is known with capacity violation of less than 2. We present a framework for designing bicriteria approximation algorithms for this problem and show two new approximation algorithms with factors (9, 3 / 2) and (29.315, 4 / 3). These are the first algorithms with constant approximation in which the violation of capacities is below 2. The heart of our algorithm is a reduction from the UCFLP to a restricted version of the problem. One feature of this reduction is that any \((O(1),1+{\epsilon })\)-approximation for the restricted version implies an \((O(1),1+{\epsilon })\)-approximation for the UCFLP and we believe our techniques might be useful towards finding such approximations or perhaps \((f({\epsilon }),1+{\epsilon })\)-approximation for the UCFLP for some function f. In addition, we present a quasi-polynomial time \((1+\epsilon ,1+\epsilon )\)-approximation for the (uniform) UCFLP in Euclidean metrics, for any constant \({\epsilon }>0\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. We should point out that the definitions of L and S are with respect to a given parameter \({\epsilon }\). Since throughout the following sections, this parameter is the same for all statements, in the interest of brevity, we use this notation instead of \(L({\epsilon })\) and \(S({\epsilon })\).

References

  1. Aggarwal, A., Anand, L., Bansal, M., Garg, N., Gupta, N., Gupta, S., Jain, S.: A 3-approximation for facility location with uniform capacities. In: Integer Programming and Combinatorial Optimization, vol 6080 of Lecture Notes in Computer Science, pp. 149–162. Springer, Berlin (2010)

  2. Alzoubi, H.A., Lee, S., Rabinovich, M., Spatscheck, O., der Merwe, J.: Anycast CDNS revisited. In: WWW ’08: Proceeding of the 17th International Conference on World Wide Web, pp. 277–286. ACM, New York, NY (2008)

  3. Arora, S.: Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 2–12. IEEE Computer Society, Washington, DC (1996)

  4. Arora, S.: Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pp. 554–563. IEEE Computer Society, Washington, DC (1997)

  5. Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: Proceedings of the Thirteeth Annual ACM Symposium on Theory of Computing, STOC ’98, pp. 106–113. ACM, New York, NY (1998)

  6. Arya, V., Garg, N., K., Rohit, M., Adam, M., Kamesh, P., Vinayaka: Local search heuristic for k-median and facility location problems. In: STOC ’01: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 21–29. ACM, New York, NY (2001)

  7. Bansal, M., Garg, N., Gupta, N.: A 5-approximation for capacitated facility location. In: 20th European Symposium on Algorithms, pp. 133–144 (2012)

  8. Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: STOC ’98: Proceedings of the Thirteeth Annual ACM symposium on Theory of computing, pp. 161–168. ACM, New York, NY (1998)

  9. Bateni, M.H., Hajiaghayi, M.T.: Assignment problem in content distribution networks: unsplittable hard-capacitated facility location. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 805–814 (2009)

  10. Behsaz, B.: Approximation Algorithms for Clustering Problems. PhD thesis, University of Alberta, Department of Computing Science (2012)

  11. Byrka, J.: An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. In: APPROX ’07/RANDOM ’07: Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 29–43. Springer, Berlin (2007)

  12. Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, pp. 378–388. IEEE Computer Society, Washington, DC (1999)

  13. Chudak, F.: Improved approximation algorithms for uncapacitated facility location. In: Integer Programming and Combinatorial Optimization, volume 1412 of Lecture Notes in Computer Science, pp. 180–194. Springer, Berlin (1998)

  14. Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for a capacitated facility location problem. In: SODA ’99: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 875–876. Society for Industrial and Applied Mathematics, Philadelphia, PA (1999)

  15. Chudak, F.A., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. In: Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 99–113. Springer, London (1999)

  16. de la Vega, W., Lueker, G.S.: Bin packing can be solved within \(1+\epsilon \) in linear time. Combinatorica 1(4), 349–355 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  17. Drezner, Zvi, Hamacher, Horst W.: Facility Location: Applications and Theory. Springer, Berlin (2004)

    MATH  Google Scholar 

  18. Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: STOC ’03: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 448–455. ACM, New York, NY (2003)

  19. Garey, Michael R., Johnson, David S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York, NY (1979)

    MATH  Google Scholar 

  20. Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. In: SODA ’98: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 649–657. Society for Industrial and Applied Mathematics, Philadelphia, PA (1998)

  21. Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: STOC ’02: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, pp. 731–740. ACM, New York, NY (2002)

  22. Jain, K., Vazirani, V.V.: Primal-dual approximation algorithms for metric facility location and k-median problems. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, pp. 2–13. IEEE Computer Society, Washington, DC (1999)

  23. Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: IEEE Symposium on Foundations of Computer Science, pp. 312–320 (1982)

  24. Kolliopoulos, S.G., Rao, S.: A nearly linear-time approximation scheme for the Euclidean kappa-median problem. In: Proceedings of the 7th Annual European Symposium on Algorithms, ESA ’99, pp. 378–389. Springer, London (1999)

  25. Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete algorithms, SODA ’98, pp. 1–10. Society for Industrial and Applied Mathematics , Philadelphia, PA (1998)

  26. Levi, R., Shmoys, D., Swamy, C.: LP-based Approximation Algorithms for Capacitated Facility Location. In: Bienstock, D., Nemhauser, G. (eds.) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 3064, pp. 21–27. Springer, Berlin (2004)

  27. Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. In: Proceedings of the 38th International Conference on Automata, Languages and Programming, Vol. Part II, ICALP’11, pp. 77–88. Springer, Berlin (2011)

  28. Lin, J.-H., Vitter, J.S.: e-approximations with minimum packing constraint violation (extended abstract). In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’92, pp. 771–782. ACM, New York, NY (1992)

  29. Love, Robert F., Morris, James G., Wesolowsky, George O.: Facilities Location: Models and Methods. North-Holland, Amsterdam (1988)

    MATH  Google Scholar 

  30. Mahdian, M., Pál, M.: Universal facility location. In: Di Battista, G., Zwick, U. (eds.) Algorithms—ESA 2003. Lecture Notes in Computer Science, vol. 2832, pp. 409–421. Springer, Berlin (2003)

  31. Mahdian, M., Ye, Y., Zhang, J.: A 2-approximation algorithm for the soft-capacitated facility location problem. In: RANDOM-APPROX, pp. 129–140 (2003)

  32. Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: APPROX, pp. 229–242 (2002)

  33. Pál, M., Tardos, É., Wexler, T: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS ’01, pp. 329–338. IEEE Computer Society, Washington, DC (2001)

  34. Shmoys, D.B., Tardos, E.: An approximation algorithm for the generalized assignment problem. Math. Progr. 62(3), 461–474 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  35. Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 265–274 (1997)

  36. Verter, V.: Foundations of location analysis, chapter 2. International Series in Operations Research and Management Science. Springer, Berlin (2011)

  37. Zhang, J., Chen, B., Ye, Y.: A Multi-exchange local search algorithm for the capacitated facility location problem. In: Integer Programming and Combinatorial Optimization, pp. 1–4. Springer, Berlin (2004)

Download references

Author information

Authors and Affiliations

  1. Department of Computing Science, University of Alberta, Edmonton, Alberta, T6G 2E8, Canada

    Babak Behsaz & Mohammad R. Salavatipour

  2. Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA, 94043, USA

    Zoya Svitkina

Authors
  1. Babak Behsaz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohammad R. Salavatipour
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zoya Svitkina
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohammad R. Salavatipour.

Additional information

A preliminary version of this paper has appeared in the Proceedings of 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), Pages 237–248, 2012.

Babak Behsaz: Supported in part by Alberta Innovates Graduate Student Scholarship.

Mohammad R. Salavatipour: Supported by NSERC and an Alberta Ingenuity New Faculty Award.

Zoya Svitkina: Supported in part by Alberta Ingenuity.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Behsaz, B., Salavatipour, M.R. & Svitkina, Z. New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem. Algorithmica 75, 53–83 (2016). https://doi.org/10.1007/s00453-015-0012-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-015-0012-z

Keywords

Search

Navigation