A Constant Factor Approximation for the Single Sink Edge Installation Problem ∗

A Constant Factor Approximation for the Single Sink Edge Installation Problem ∗
复制标题

单水槽边缘安装问题的常数因子近似*

DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Kamesh Munagala
Kamesh Munagala
中科院分区：
--
文献类型：
--
作者：
Sudipto Guha;Adam Meyerson;Kamesh Munagala

文献摘要

被引文献

相似文献

我们提出了单汇批量购买网络设计问题的第一个恒定近似，其中我们必须通过购买每单位长度不同成本和容量的管道来设计网络，以将一组源的需求路由到单个汇。底层网络中的距离形成一个度量。此结果改进了之前的 O(log |R|) 界限，其中 R 是源集。我们还对相关的接入网络设计问题提出了更好的常数近似。我们的算法是随机和组合的。作为我们算法中的子程序，我们使用设施位置的一个有趣的变体，其开放设施需要服务的需求量的下限。我们将此变体称为负载平衡设施位置，并为其提供常数因子近似值，同时通过常数因子放宽下限。 *本文结合了两篇会议论文 [12, 13] 的工作，这些论文分别发表在 2000 年第 41 届 IEEE 计算机科学基础研讨会和 2001 年第 33 届 ACM 计算理论研讨会上。 †宾夕法尼亚大学计算机与信息科学系。电子邮件：sudipto@cis.upenn.edu。研究由美国国家科学基金会职业奖和斯隆基金会奖学金支持。 ‡加利福尼亚大学计算机科学系，洛杉矶 CA 90095-1596。电子邮件：awm@cs.ucla.edu §杜克大学计算机科学系，Durham NC 27708。电子邮件：kamesh@cs.duke.edu。研究由 NSF 通过职业奖和拨款 CNS-0540347 支持。
We present the first constant approximation to the single sink buy-at-bulk network design problem, where we have to design a network by buying pipes of different costs and capacities per unit length to route demands at a set of sources to a single sink. The distances in the underlying network form a metric. This result improves the previous bound of O(log |R|), where R is the set of sources. We also present a better constant approximation to the related Access Network Design problem. Our algorithms are randomized and combinatorial. As a subroutine in our algorithm, we use an interesting variant of facility location with lower bounds on the amount of demand an open facility needs to serve. We call this variant load balanced facility location, and present a constant factor approximation for it, while relaxing the lower bounds by a constant factor. ∗This paper combines the work in two conference papers [12, 13], which appeared in the 41st IEEE Symposium on the Foundations of Computer Science, 2000 and the 33rd ACM Symposium on Theory of Computing, 2001 respectively. †Department of Computer and Information Sciences, University of Pennsylvania. Email: sudipto@cis.upenn.edu. Research supported by an NSF CAREER award and a Sloan Foundation Fellowship. ‡Department of Computer Science, University of California, Los Angeles CA 90095-1596. Email: awm@cs.ucla.edu §Department of Computer Science, Duke University, Durham NC 27708. Email: kamesh@cs.duke.edu. Research supported by NSF via a CAREER award and grant CNS-0540347.