2011 | OriginalPaper | Chapter
Approximating Survivable Networks with Minimum Number of Steiner Points
Authors : Lior Kamma, Zeev Nutov
Published in: Approximation and Online Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a graph
H
= (
U
,
E
) and connectivity requirements
r
= {
r
(
u
,
v
):
u
,
v
∈
R
⊆
U
}, we say that
H
satisfies
r
if it contains
r
(
u
,
v
) pairwise internally-disjoint
uv
-paths for all
u
,
v
∈
R
. We consider the
Survivable Network with Minimum Number of Steiner Points
(
SN-MSP
) problem: given a finite set
V
of points in a normed space
$(M, \left\| \cdot \right\|)$
, and connectivity requirements, find a minimum size set
S
⊂
M
−
V
of additional points, such that the unit disc graph induced by
V
∪
S
satisfies the requirements. In the (node-connectivity version of the)
Survivable Network Design Problem
(
SNDP
) we are given a graph
G
= (
V
,
E
) with edge costs and connectivity requirements, and seek a min-cost subgraph
H
of
G
that satisfies the requirements. Let
$k = \mathop{ \max }\limits_{u,v \in V}{r(u,v)}$
denote the maximum connectivity requirement. We will show a natural transformation of an
SN-MSP
instance (
V
,
r
) into an
SNDP
instance (
G
= (
V
,
E
),
c
,
r
), such that an
α
-approximation for the
SNDP
instance implies an
α
·
O
(
k
2
)-approximation algorithm for the
SN-MSP
instance. In particular, for the most interesting case of uniform requirement
r
(
u
,
v
) =
k
for all
u
,
v
∈
V
, we obtain for
SN-MSP
the ratio
O
(
k
2
ln
k
), which solves an open problem from [3].