首页    期刊浏览 2024年09月18日 星期三
登录注册

文章基本信息

  • 标题:One Tree Suffices: A Simultaneous $O(1)$-Approximation for Single-Sink Buy-at-Bulk
  • 本地全文:下载
  • 作者:Ashish Goel ; Ian Post
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2012
  • 卷号:8
  • 页码:351-368
  • 出版社:University of Chicago
  • 摘要:

    We study the single-sink buy-at-bulk problem with an unknown cost function. We wish to route flow from a set of demand nodes to a root node, where the cost of routing $x$ total flow along an edge is proportional to $f(x)$ for some concave, non-decreasing function $f$ satisfying $f(0)=0$. We present a simple, fast, combinatorial algorithm that takes a set of demands and constructs a single tree $T$ such that for all $f$ the cost $f(T)$ is a 47.45-approximation of the optimal cost for that particular $f$. This is within a factor of 2.33 of the best approximation ratio currently achievable when the tree can be optimized for a specific function. Trees achieving simultaneous $O(1)$-approximations for all concave functions were previously not known to exist regardless of computation time.

  • 关键词:network design; buy-at-bulk; simultaneous optimization
国家哲学社会科学文献中心版权所有