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 条
  • [21] Approximation algorithms for min-max and max-min resource sharing problems, and applications
    Jansen, K
    EFFICIENT APPROXIMATION AND ONLINE ALGORITHMS: RECENT PROGRESS ON CLASSICAL COMBINATORIAL OPTIMIZATION PROBLEMS AND NEW APPLICATIONS, 2006, 3484 : 156 - 202
  • [22] Min-Max Spaces and Complexity Reduction in Min-Max Expansions
    Gaubert, Stephane
    McEneaney, William M.
    APPLIED MATHEMATICS AND OPTIMIZATION, 2012, 65 (03): : 315 - 348
  • [23] Approximation schemes for the min-max starting time problem
    Epstein, L
    Tassa, T
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2003, PROCEEDINGS, 2003, 2747 : 408 - 418
  • [24] Complexity of the min-max and min-max regret assignment problems
    Aissi, H
    Bazgan, C
    Vanderpooten, D
    OPERATIONS RESEARCH LETTERS, 2005, 33 (06) : 634 - 640
  • [25] Min-Max Spaces and Complexity Reduction in Min-Max Expansions
    Stephane Gaubert
    William M. McEneaney
    Applied Mathematics & Optimization, 2012, 65 : 315 - 348
  • [26] Approximation Algorithms for Min-Max Cycle Cover Problems
    Xu, Wenzheng
    Liang, Weifa
    Lin, Xiaola
    IEEE TRANSACTIONS ON COMPUTERS, 2015, 64 (03) : 600 - 613
  • [27] Approximation schemes for the Min-Max Starting Time Problem
    Epstein, L
    Tassa, T
    ACTA INFORMATICA, 2004, 40 (09) : 657 - 674
  • [28] Approximation schemes for the Min-Max Starting Time Problem
    Leah Epstein
    Tamir Tassa
    Acta Informatica, 2004, 40 : 657 - 674
  • [29] MIN-MAX SPANNING TREE PROBLEM AND SOME EXTENSIONS
    CAMERINI, PM
    INFORMATION PROCESSING LETTERS, 1978, 7 (01) : 10 - 14
  • [30] Partial inverse min-max spanning tree problem
    Tayyebi, Javad
    Sepasian, Ali Reza
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (04) : 1075 - 1091
12345