skip to main content
research-article

Approximation algorithms for a facility location problem with service capacities

Published: 22 August 2008 Publication History

Abstract

We present the first constant-factor approximation algorithms for the following problem. Given a metric space (V, c), a finite set DV of terminals/customers with demands d : D → R+, a facility opening cost f ∈ R+ and a capacity u ∈R+, find a partition D = D1⊍…⊍Dk and Steiner trees Ti for Di (i = 1, …,k) with c(E(Ti)) + d(Di) ≤ u for i = 1,…,k such that Σi = 1k c(E(Ti)) + kf is minimum. This problem arises in VLSI design. It generalizes the bin-packing problem and the Steiner tree problem. In contrast to other network design and facility location problems, it has the additional feature of upper bounds on the service cost that each facility can handle. Among other results, we obtain a 4.1-approximation in polynomial time, a 4.5-approximation in cubic time, and a 5-approximation as fast as computing a minimum spanning tree on (D, c).

References

[1]
Alpert, C., Kahng, A., Liu, B., Mandoiu, I., and Zelikovsky, A. 2003. Minimum buffered routing with bounded capacitive load for slew rate and reliability control. IEEE Trans. Comput.-Aid. Design Integra. Circuits Syst., 241--253.
[2]
Arora, S. 1998. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. J. ACM 45, 753--778.
[3]
Bartoschek, C., Held, S., Rautenbach, D., and Vygen, J. 2006. Efficient generation of short and fast repeater. In Proceedings of the International Symposium on Physical Design (ISPD'06). ACM Press, New York, NY, 120--127.
[4]
Christofides, N. 1976. Worst-case analysis of a new heuristic for the traveling salesman problem. Tech. rep. CS-93-13, G.S.I.A., Carnegie Mellon University, Pittsburgh, PA.
[5]
Du, D.-Z., Zhang, Y., and Feng, Q. 1991. On better heuristic for Euclidean Steiner minimum trees. In Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science. 431--439.
[6]
Even, G., Garg, N., Könemann, J., Ravi, R., and Sinha, A. 2004. Min-max tree covers of graphs. Oper. Resear. Lett. 32, 4, 309--315.
[7]
Garey, M., and Johnson, D. 1977. The rectilinear Steiner problem is NP-complete. SIAM J. Appl. Math. 32, 826--834.
[8]
Garey, M. R., Graham, R. L., and Johnson, D. S. 1977. The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32, 835--859.
[9]
Held, S., Korte, B., Maßberg, J., Ringe, M., and Vygen, J. 2003. Clock scheduling and clocktree construction for high performance asics. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD'03). IEEE Computer Society, Washington, DC, 232--240.
[10]
Hwang, F. 1976. On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math. 30, 104--114.
[11]
Karmarkar, N., and Karp, R. M. 1982. An efficient approximation scheme for the one-dimensional bin packing problem. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science. 312--320.
[12]
Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. Thatcher Eds., Plenham Press, New York, NY. 85--103.
[13]
Korte, B., and Vygen, J. 2008. Combinatorial Optimization: Theory and Algorithms 4th Ed. Springer, Berlin, Germany.
[14]
Maßberg, J., and Vygen, J. 2005. Approximation algorithms for network design and facility location with service capacities. In Proceedings of 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'05). Springer, 158--169.
[15]
Robins, G., and Zelikovsky, A. 2000. Improved Steiner tree approximation in graphs. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, 770--779.
[16]
Simchi-Levi, D. 1994. New worst-case results for the bin-packing problem. Naval Resear. Logistics 41, 579--585.
[17]
Toth, P., and D. Vigo, e. 2002. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms
ACM Transactions on Algorithms  Volume 4, Issue 4
August 2008
264 pages
ISSN:1549-6325
EISSN:1549-6333
DOI:10.1145/1383369
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 August 2008
Accepted: 01 February 2007
Received: 01 December 2005
Published in TALG Volume 4, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Approximation algorithm
  2. VLSI design
  3. facility location
  4. network design

Qualifiers

  • Research-article
  • Research
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)12
  • Downloads (Last 6 weeks)2
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Approximation algorithms for the airport and railway problemJournal of Combinatorial Optimization10.1007/s10878-024-01237-449:1Online publication date: 4-Dec-2024
  • (2022)Constant-Factor Approximation Algorithms for Parity-Constrained Facility Location and k-CenterAlgorithmica10.1007/s00453-022-01060-585:7(1883-1911)Online publication date: 20-Dec-2022
  • (2018)Global Routing With Timing ConstraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.269796437:2(406-419)Online publication date: 1-Feb-2018
  • (2017)Low-Power Clock Tree Synthesis for 3D-ICsACM Transactions on Design Automation of Electronic Systems10.1145/301961022:3(1-24)Online publication date: 5-Apr-2017
  • (2015)Global Routing with Inherent Static Timing ConstraintsProceedings of the IEEE/ACM International Conference on Computer-Aided Design10.5555/2840819.2840834(102-109)Online publication date: 2-Nov-2015
  • (2015)Global routing with inherent static timing constraints2015 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1109/ICCAD.2015.7372556(102-109)Online publication date: Nov-2015
  • (2012)A Fast and Near-Optimal Clustering Algorithm for Low-Power Clock Tree SynthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2012.220659231:11(1781-1786)Online publication date: 1-Nov-2012
  • (2010)Impact of local interconnects on timing and power in a high performance microprocessorProceedings of the 19th international symposium on Physical design10.1145/1735023.1735060(145-152)Online publication date: 14-Mar-2010
  • (2010)Mathematics of Chip DesignProduction Factor Mathematics10.1007/978-3-642-11248-5_10(179-206)Online publication date: 2010
  • (2009)An algorithm for routing with capacitance/distance constraints for clock distribution in microprocessorsProceedings of the 2009 international symposium on Physical design10.1145/1514932.1514964(141-148)Online publication date: 29-Mar-2009
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media