Approximating source location and star survivable network problems

DOI10.1007/978-3-662-53174-7_15MaRDI QIDQ2827812zbMATH OpenOpenAlexFDO

Publication date 21 October 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.4728

Discrete location and assignment (90B80) Programming involving graphs or networks (90C35)

Abstract: In Source Location (SL) problems the goal is to select a mini-mum cost source set

S s u b s e t e q V

such that the connectivity (or flow)

p s i (S, v)

from

S

to any node

v

is at least the demand

d_{v}

of

v

. In many SL problems

p s i (S, v) = d_{v}

if

v i n S

, namely, the demand of nodes selected to

S

is completely satisfied. In a node-connectivity variant suggested recently by Fukunaga, every node

v

gets a "bonus"

p_{v} l e q d_{v}

if it is selected to

S

. Fukunaga showed that for undirected graphs one can achieve ratio

O (k l n k)

for his variant, where

k = m a x_{v i n V} d_{v}

is the maximum demand. We improve this by achieving ratio

m i n p^{*} l n k, k c d o t O (l n (k / q^{*}))

for a more general version with node capacities, where

p^{*} = m a x_{v i n V} p_{v}

is the maximum bonus and

q^{*} = m i n_{v i n V} q_{v}

is the minimum capacity. In particular, for the most natural case

p^{*} = 1

considered by Fukunaga, we improve the ratio from

O (k l n k)

to

O (l n^{2} k)

. We also get ratio

O (k)

for the edge-connectivity version, for which no ratio that depends on

k

only was known before. 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 give ratio

O (m i n l n n, l n^{2} k)

for this variant, improving over the best ratio known for the general case

O (k^{3} l n n)

of Chuzhoy and Khanna.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Approximating source location and star survivable network problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2827812)