
CMUCS03162
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS03162
Simultaneous Source Location
Konstantin Andreev*, Charles Garrod,
Bruce Maggs, Adam Meyerson
July 2003
CMUCS03162.ps
CMUCS03162.pdf
Keywords: Approximation algorithms, NPHardness, undirected
capacitated flow graph, treewidth, source location, facility location
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(log n log log n), where n is the number of nodes.
On graphs of bounded treewidth, we show the problem is still
NPHard, 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.
13 pages
*Mathematics Department, Carnegie Mellon University
