{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:37:13Z","timestamp":1750307833698,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,8]]},"abstract":"\n We present the first constant-factor approximation algorithms for the following problem. Given a metric space (\n V<\/jats:italic>\n ,\n c<\/jats:italic>\n ), a finite set\n D<\/jats:italic>\n \u2286\n V<\/jats:italic>\n of terminals\/customers with demands\n d<\/jats:italic>\n :\n D<\/jats:italic>\n \u2192 R\n +<\/jats:sub>\n , a facility opening cost\n f<\/jats:italic>\n \u2208 R\n +<\/jats:sub>\n and a capacity\n u<\/jats:italic>\n \u2208R\n +<\/jats:sub>\n , find a partition\n D<\/jats:italic>\n =\n D<\/jats:italic>\n 1<\/jats:sub>\n \u228d\u2026\u228d\n \n D\n k<\/jats:sub>\n <\/jats:italic>\n and Steiner trees\n \n T\n i<\/jats:sub>\n <\/jats:italic>\n for\n \n D\n i<\/jats:sub>\n <\/jats:italic>\n (\n i<\/jats:italic>\n = 1, \u2026,\n k<\/jats:italic>\n ) with\n c<\/jats:italic>\n (\n E<\/jats:italic>\n (\n \n T\n i<\/jats:sub>\n <\/jats:italic>\n )) +\n d<\/jats:italic>\n (\n \n D\n i<\/jats:sub>\n <\/jats:italic>\n ) \u2264\n u<\/jats:italic>\n for\n i<\/jats:italic>\n = 1,\u2026,\n k<\/jats:italic>\n such that \u03a3\n \n i<\/jats:italic>\n <\/jats:sub>\n = 1\n \n k<\/jats:italic>\n <\/jats:sup>\n c<\/jats:italic>\n (\n E<\/jats:italic>\n (\n T<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n )) +\n kf<\/jats:italic>\n 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 (\n D<\/jats:italic>\n ,\n c<\/jats:italic>\n ).\n <\/jats:p>","DOI":"10.1145\/1383369.1383381","type":"journal-article","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T11:56:36Z","timestamp":1219838196000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Approximation algorithms for a facility location problem with service capacities"],"prefix":"10.1145","volume":"4","author":[{"given":"Jens","family":"Ma\u00dfberg","sequence":"first","affiliation":[{"name":"University of Bonn, Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[{"name":"University of Bonn, Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8,22]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1109\/TCAD.2002.807888"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/290179.290180"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/1123008.1123032"},{"unstructured":"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. 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.","key":"e_1_2_1_4_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1109\/SFCS.1991.185402"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1016\/j.orl.2003.11.010"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1137\/0132071"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1137\/0132072"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.5555\/996070.1009896"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1137\/0130013"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1109\/SFCS.1982.61"},{"volume-title":"Complexity of Computer Computations","author":"Karp R. M.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"Korte B.","year":"2008","edition":"4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1007\/11538462_14"},{"volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM","author":"Robins G.","key":"e_1_2_1_15_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1002\/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G"},{"doi-asserted-by":"crossref","unstructured":"Toth P. and D. Vigo e. 2002. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. SIAM Philadelphia PA. Toth P. and D. Vigo e. 2002. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. SIAM Philadelphia PA.","key":"e_1_2_1_17_1","DOI":"10.1137\/1.9780898718515"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383381","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1383369.1383381","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:59Z","timestamp":1750255079000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383381"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1383369.1383381"],"URL":"https:\/\/doi.org\/10.1145\/1383369.1383381","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2005-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}