Simultaneous source location

Published

Journal Article

We consider the problem of Simultaneous Source Location -selecting locations for sources in a capacitated graph such that a given set of demands can be satisfied. We give an exact algorithm for trees and show how this can be combined with a result of Räcke to give a solution that exceeds edge capacities by at most O(log2 n log log n), where n is the number of nodes. On graphs of bounded treewidth, we show the problem is still NP-Hard, but we are able to give a PTAS with at most O(1+ε) violation of the capacities, or a (k+1)-approximation with exact capacities, where k is the treewidth and ε can be made arbitrarily small. © Springer-Verlag 2004.

Duke Authors

Cited Authors

  • Andreev, K; Garrod, C; Maggs, B; Meyerson, A

Published Date

  • December 1, 2004

Published In

Volume / Issue

  • 3122 /

Start / End Page

  • 13 - 26

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

Citation Source

  • Scopus