Approximation hardness of min-max tree covers

被引：25

作者：

Xu, Zhou ^{[1
]}

Wen, Qi ^{[2
]}

机构：

[1] Hong Kong Polytech Univ, Dept Logist & Maritime Studies, Hong Kong, Hong Kong, Peoples R China

[2] City Univ Hong Kong, Dept Management Sci, Hong Kong, Hong Kong, Peoples R China

来源：

OPERATIONS RESEARCH LETTERS | 2010年 / 38卷 / 03期

关键词：

Inapproximability bound; Min-max; Vehicle routing; Tree covers; TRAVELING SALESMEN; ALGORITHMS;

D O I：

10.1016/j.orl.2010.02.004

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees. Our technique can also be applied to improve inapproximability bounds for min-max problems that use other covering objectives, such as stars, paths, and tours. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：169 / 173

页数：5

共 10 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2] Approximations for minimum and min-max vehicle routing problems [J].

Arkin, EM ;

Hassin, R ;

Levin, A .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2006, 59 (01) :1-18

[3] A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree [J].

Averbakh, I ;

Berman, O .

DISCRETE APPLIED MATHEMATICS, 1996, 68 (1-2) :17-32

[4] (P-1)/(p+1)-approximate algorithms for p-traveling salesmen problems on a tree with minmax objective [J].

Averbakh, I ;

Berman, O .

DISCRETE APPLIED MATHEMATICS, 1997, 75 (03) :201-216

[5] Routing for relief efforts [J].

Campbell, Ann Melissa ;

Vandenbussche, Dieter ;

Hermann, William .

TRANSPORTATION SCIENCE, 2008, 42 (02) :127-145

[6] Min-max tree covers of graphs [J].

Even, G ;

Garg, N ;

Könemann, J ;

Ravi, R ;

Sinha, A .

OPERATIONS RESEARCH LETTERS, 2004, 32 (04) :309-315

[7] APPROXIMATION ALGORITHMS FOR SOME ROUTING PROBLEMS [J].

FREDERICKSON, GN ;

HECHT, MS ;

KIM, CE .

SIAM JOURNAL ON COMPUTING, 1978, 7 (02) :178-193

[8] Approximating the minmax rooted-subtree cover problem [J].

Nagamochi, H .

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2005, E88A (05) :1335-1338

[9]

Nagamochi H, 2003, LECT NOTES COMPUT SC, V2906, P138

[10] On the approximability of the traveling salesman problem [J].

Papadimitriou, CH ;

Vempala, S .

COMBINATORICA, 2006, 26 (01) :101-120

← 1 →