Simultaneous source location
Authors:
Open Access
- 28 December 2009
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 6 (1) , 1-17
Abstract
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.Keywords
Funding Information
- National Science Foundation (CCR-0085982CCR-0122581CNF-0435382)
This publication has 16 references indexed in Scilit:
- Minimum Transversals in Posi-modular SystemsLecture Notes in Computer Science, 2006
- An algorithm for source location in directed graphsOperations Research Letters, 2005
- Local Search Heuristics for k-Median and Facility Location ProblemsSIAM Journal on Computing, 2004
- Locating Sources to Meet Flow Demands in Undirected NetworksJournal of Algorithms, 2002
- Minimum cost source location problem with vertex-connectivity requirements in digraphsInformation Processing Letters, 2001
- Generalized submodular cover problems and applicationsTheoretical Computer Science, 2001
- A partial k-arboretum of graphs with bounded treewidthTheoretical Computer Science, 1998
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986
- An analysis of the greedy algorithm for the submodular set covering problemCombinatorica, 1982
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956