In:
ACM Transactions on Algorithms, Association for Computing Machinery (ACM), Vol. 4, No. 4 ( 2008-08), p. 1-15
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 1 ⊍…⊍ 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 Σ 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 ).
Type of Medium:
Online Resource
ISSN:
1549-6325
,
1549-6333
DOI:
10.1145/1383369.1383381
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2008
detail.hit.zdb_id:
2198259-4
Permalink