Approximating source location and star survivable network problems

Guy Kortsarz, Zeev Nutov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

In Source Location (SL) problems the goal is to select a minimum cost source set S ⊆ V such that the connectivity (or flow) ψ(S, v) from S to any node v is at least the demand dv of v. In many SL problems ψ(S, v) = dv if v ∈ S, so the demand of nodes selected to S is completely satisfied. In a variant suggested recently by Fukunaga [7], every node v selected to S gets a “bonus” pv ≤ dv, and ψ(S, v) = pv + κ(S \ {v}, v) if v ∈ S and ψ(S, v) = κ(S, v) otherwise, where κ(S, v) is the maximum number of internally disjoint (S, v)-paths. While the approximability of many SL problems was seemingly settled to Θ(ln d(V )) in [20], for his variant on undirected graphs Fukunaga achieved ratio O(k ln k), where k = maxvV dv is the maximum demand. We improve this by achieving ratio min{p ln k, k} · O(ln k) for a more general version with node capacities, where p = maxv∈V pv is the maximum bonus. In particular, for the most natural case p = 1 we improve the ratio from O(k ln k) to O(ln2 k). To derive these results, we consider a particular case of the Survivable Network (SN) problem when all edges of positive cost form a star. We obtain ratio O(min{ln n, ln2 k}) for this variant, improving over the best ratio known for the general case O(k3 ln n) of Chuzhoy and Khanna [3]. In addition, we show that directed SL with unit costs is Ω(log n)-hard to approximate even for 0, 1 demands, while SL with uniform demands can be solved in polynomial time. Finally, we obtain a logarithmic ratio for a generalization of SL where we also have edge-costs and flow-cost bounds {bv: v ∈ V }, and require that the minimum cost of a flow of value dv from S to every node v is at most bv.

Original languageEnglish (US)
Title of host publicationGraph-Theoretic Concepts in Computer Science - 41st International Workshop, WG 2015, Revised Papers
EditorsErnst W. Mayr
PublisherSpringer Verlag
Pages203-218
Number of pages16
ISBN (Print)9783662531730
DOIs
StatePublished - 2016
Event41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 - Garching, Germany
Duration: Jun 17 2015Jun 19 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9224 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015
CountryGermany
CityGarching
Period6/17/156/19/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximating source location and star survivable network problems'. Together they form a unique fingerprint.

Cite this