Covering Problems in Edge- and Node-Weighted Graphs

被引：0

作者：

Fukunaga, Takuro ^{[1
]}

机构：

[1] Natl Inst Informat, Tokyo, Japan

来源：

ALGORITHM THEORY - SWAT 2014 | 2014年 / 8503卷

关键词：

APPROXIMATION ALGORITHMS; MULTICUT; FLOW;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper discusses the graph covering problem in which a set of edges in an edge-and node-weighted graph is chosen to satisfy some covering constraints while minimizing the sum of the weights. In this problem, because of the large integrality gap of a natural linear programming (LP) relaxation, LP rounding algorithms based on the relaxation yield poor performance. Here we propose a stronger LP relaxation for the graph covering problem. The proposed relaxation is applied to designing primal-dual algorithms for two fundamental graph covering problems: the prize-collecting edge dominating set problem and the multicut problem in trees. Our algorithms are an exact polynomial-time algorithm for the former problem, and a 2-approximation algorithm for the latter problem, respectively. These results match the currently known best results for purely edge-weighted graphs.

引用

页码：217 / 228

页数：12

共 28 条

[1]

Bateni M, 2013, LECT NOTES COMPUT SC, V7965, P81, DOI 10.1007/978-3-642-39206-1_8

[2] Linear time algorithms for generalized edge dominating set problems [J].

Berger, Andre ;

Parekh, Ojas .

ALGORITHMICA, 2008, 50 (02) :244-254

[3] Approximability of the capacitated b-edge dominating set problem [J].

Berger, Andre ;

Fukunaga, Takuro ;

Nagamochi, Hiroshi ;

Parekh, Ojas .

THEORETICAL COMPUTER SCIENCE, 2007, 385 (1-3) :202-213

[4] Linear Time Algorithms for Generalized Edge Dominating Set Problems (vol 50, pg 244, 2008) [J].

Berger, Andre ;

Parekh, Ojas .

ALGORITHMICA, 2012, 62 (1-2) :633-634

[5] Steiner Tree Approximation via Iterative Randomized Rounding [J].

Byrka, Jaroslaw ;

Grandoni, Fabrizio ;

Rothvoss, Thomas ;

Sanita, Laura .

JOURNAL OF THE ACM, 2013, 60 (01)

[6]

Carr R, 2001, J COMB OPTIM, V5, P317, DOI 10.1023/A:1011445210568

[7] On the hardness of approximating MULTICUT and SPARSEST-CUT [J].

Chawla, Shuchi ;

Krauthgamer, Robert ;

Kumar, Ravi ;

Rabani, Yuval ;

Sivakumar, D. .

COMPUTATIONAL COMPLEXITY, 2006, 15 (02) :94-114

[8]

Chekuri Chandra, 2012, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Proceedings 15th International Workshop, APPROX 2012 and 16th International Workshop, RANDOM 2012, P98, DOI 10.1007/978-3-642-32512-0_9

[9] THE COMPLEXITY OF MULTITERMINAL CUTS [J].

DAHLHAUS, E ;

JOHNSON, DS ;

PAPADIMITRIOOU, CH ;

SEYMOUR, PD ;

YANNAKAKIS, M .

SIAM JOURNAL ON COMPUTING, 1994, 23 (04) :864-894

[10] A 2-approximation algorithm for the minimum weight edge dominating set problem [J].

Fujito, T ;

Nagamochi, H .

DISCRETE APPLIED MATHEMATICS, 2002, 118 (03) :199-207

← 1 2 3 →