Approximation hardness of min-max tree covers

被引：23

作者：

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

共 50 条

[41] Approximation results for a min-max location-routing problem
Xu, Zhou
Xu, Dongsheng
Zhu, Wenbin
DISCRETE APPLIED MATHEMATICS, 2012, 160 (03) : 306 - 320
[42] Approximation algorithms for some min-max postmen cover problems
Yu, Wei
Liu, Zhaohui
Bao, Xiaoguang
ANNALS OF OPERATIONS RESEARCH, 2021, 300 (01) : 267 - 287
[43] Min-Max Approximation of Transfer Functions With Application to Filter Design
Li, Xianwei
Gao, Huijun
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2015, 63 (01) : 31 - 40
[44] MIN-MAX INDICATOR
VASILEV, SI
SIDELNIKOV, ZI
INSTRUMENTS AND EXPERIMENTAL TECHNIQUES, 1983, 26 (06) : 1325 - 1327
[45] On a min-max theorem
Wu G.R.
Huang W.H.
Shen Z.H.
Applied Mathematics-A Journal of Chinese Universities, 1997, 12 (3) : 293 - 298
[46] APPROXIMATION BY ISOTONE FUNCTIONS - MIN-MAX FORM OF BEST APPROXIMATION - PRELIMINARY REPORT
UBHAYA, VA
NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1974, 21 (02): : A307 - A307
[47] Min-max and min-max regret versions of combinatorial optimization problems: A survey
Aissi, Hassene
Bazgan, Cristina
Vanderpooten, Daniel
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 197 (02) : 427 - 438
[48] Min-max coverage problems on tree-like metrics
Aaron, Eric
Hebert-Johnson, Ursula
Krizanc, Danny
Lokshtanov, Daniel
XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, 2023, 224 : 148 - 156
[49] Min-max event-triggered computation tree logic
Dasgupta, P
Chakrabarti, PP
Deka, JK
SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES, 2002, 27 (2): : 163 - 180
[50] Min-max event-triggered computation tree logic
Dasgupta, Pallab
Chakrabarti, P.P.
Deka, Jatindra Kumar
Sadhana - Academy Proceedings in Engineering Sciences, 2002, 27 (02) : 163 - 180

← 1 2 3 4 5 →