Simultaneous source location
Konstantin Andreev, Charles Garrod, Daniel Golovin, Bruce MacDowell Maggs, Adam Meyerson · ACM Transactions on Algorithms · 2009
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 simultaneously, with the goal of minimizing the number of locations chosen. For general directed and undirected graphs we give an O (log D )-approximation algorithm, where D is the sum of demands, and prove matching Ω(log D ) hardness results assuming P ≠ NP . For undirected trees, we give an exact algorithm 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 2 n log log n ), where n is the number of nodes. For undirected graphs of bounded treewidth we show that the problem is still NP -hard, but we are able to give a PTAS with at most (1 + ϵ) violation of the capacities for arbitrarily small ϵ, or a ( k +1) approximation with exact capacities, where k is the treewidth.