Title | ||
---|---|---|
Greedy approximation for source location problem with vertex-connectivity requirements in undirected graphs |
Abstract | ||
---|---|---|
Let G = (V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v ∈ V has a demand d(v) ∈ Z+, and a cost c(v) ∈ R+, where Z+ and R+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices minimizing Σv∈S c(v) such that there are at least d(v) pairwise vertex-disjoint paths from S to v for each vertex v ∈ V - S. It is known that the problem is not approximable within a ratio of O(ln Σv∈V d(v)), unless NP has an O(Nlog log N)-time deterministic algorithm. Also, it is known that even if every vertex has a uniform cost and d* = 4 holds, then the problem is NP-hard, where d* = max{d(v) | v ∈ V}. In this paper, we consider the problem in the case where every vertex has a uniform cost. We propose a simple greedy algorithm for delivering a max{d* + 1, 2d* - 6}-approximate solution to the problem in O(min{d*, √|V|}d*|V|2) time. Especially, in the case of d* ≤ 4, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to d* ≤ 4. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-77120-3_5 | ISAAC |
Keywords | Field | DocType |
set v,greedy approximation,vertex-connectivity requirement,approximation ratio,undirected graph,nonnegative real,source location problem,vertex v,simple greedy algorithm,graph g,nonnegative integer,uniform cost,set e,greedy algorithm | Integer,Discrete mathematics,Binary logarithm,Graph,Greedy approximation,Combinatorics,Vertex (geometry),Neighbourhood (graph theory),Greedy algorithm,Deterministic algorithm,Mathematics | Conference |
Volume | ISSN | ISBN |
4835 | 0302-9743 | 3-540-77118-2 |
Citations | PageRank | References |
1 | 0.36 | 10 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Toshimasa Ishii | 1 | 110 | 17.03 |