A constant factor approximation for the single sink edge installation problem

Journal Article (Journal Article)

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. © 2009 Society for Industrial and Applied Mathematics.

Full Text

Duke Authors

Cited Authors

  • Guha, S; Meyerson, A; Munagala, K

Published Date

  • June 1, 2009

Published In

Volume / Issue

  • 38 / 6

Start / End Page

  • 2426 - 2442

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/050643635

Citation Source

  • Scopus