# 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 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. Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems'Routing and layout; G.2.1 [Discrete Mathematics]: Combinatorics' Combinatorial algorithms; G.2.2 [Discrete Mathematics]: Graph Theory'Network problems graph algorithms, trees. © 2009 ACM.

### Full Text

### Duke Authors

### Cited Authors

- Andreev, K; Garrod, C; Golovin, D; Maggs, B; Meyerson, A

### Published Date

- December 1, 2009

### Published In

### Volume / Issue

- 6 / 1

### Electronic International Standard Serial Number (EISSN)

- 1549-6333

### International Standard Serial Number (ISSN)

- 1549-6325

### Digital Object Identifier (DOI)

- 10.1145/1644015.1644031

### Citation Source

- Scopus