Approximation algorithms for a facility location problem with service capacities

ABSTRACT

We present the first constant-factor approximation algorithms for the following problem. Given a metric space (V, c), a finite set D ⊆ V of terminals/customers with demands d : D → R₊, a facility opening cost f ∈ R₊ and a capacity u ∈R₊, find a partition D = D₁⊍…⊍D_k and Steiner trees T_i for D_i (i = 1, …,k) with c(E(T_i)) + d(D_i) ≤ u for i = 1,…,k such that &sum_i = 1^k c(E(T_i)) + 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: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 3: Christoph Bartoschek , Stephan Held , Dieter Rautenbach , Jens Vygen, Efficient generation of short and fast repeater tree topologies, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123032]
• 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: Ding-Zhu Du , Yanjun Zhang , Qing Feng, On better heuristic for euclidean Steiner minimum trees (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.431-439, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185402]
• 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: Stephan Held , Bernhard Korte , Jens Maβberg , Matthias Ringe , Jens Vygen, Clock Scheduling and Clocktree Construction for High Performance ASICS, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.232, November 09-13, 2003 [doi>10.1109/ICCAD.2003.48]
• 10: Hwang, F. 1976. On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math. 30, 104--114.
• 11: Narendra Karmarkar , Richard M. Karp, An efficient approximation scheme for the one-dimensional bin-packing problem, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), p.312-320, November 03-05, 1982
• 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: Gabriel Robins , Alexander Zelikovsky, Improved Steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.770-779, January 09-11, 2000, San Francisco, California, United States
• 16: Simchi-Levi, D. 1994. New worst-case results for the bin-packing problem. Naval Resear. Logistics 41, 579--585.
• 17: Paolo Toth , Daniele Vigo, The vehicle routing problem, Society for Industrial and Applied Mathematics, Philadelphia, PA, 01

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms

Keywords:
Approximation algorithm, VLSI design, facility location, network design