Carnegie Mellon University
Browse

Simultaneous Source Location

Download (175.29 kB)
journal contribution
posted on 2004-01-01, 00:00 authored by Konstantin Andreev, Charles Garrod, Bruce M Maggs, Adam Meyerson
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(log2n log logn), 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.

History

Date

2004-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC