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 条
  • [31] An in-place min-max priority search tree
    De, Minati
    Maheshwari, Anil
    Nandy, Subhas C.
    Smid, Michiel
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2013, 46 (03): : 310 - 327
  • [32] Better Inapproximability Bounds and Approximation Algorithms for Min-Max Tree/Cycle/Path Cover Problems
    Yu, Wei
    Liu, Zhaohui
    COMPUTING AND COMBINATORICS, COCOON 2017, 2017, 10392 : 542 - 554
  • [33] A Distributed Algorithm for Min-Max Tree and Max-Min Cut Problems in Communication Networks
    Guo, Song
    Leung, Victor C. M.
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2010, 18 (04) : 1067 - 1076
  • [34] On the complexity and approximation of the min-sum and min-max disjoint paths problems
    Zhang, Peng
    Zhao, Wenbo
    COMBINATORICS, ALGORITHMS, PROBABILISTIC AND EXPERIMENTAL METHODOLOGIES, 2007, 4614 : 70 - +
  • [35] ON A MIN-MAX THEOREM
    CHEN FANGQI
    Applied Mathematics:A Journal of Chinese Universities(Series B), 1997, (03) : 43 - 48
  • [36] Improved approximation algorithms for the Min-Max Selecting Items problem
    Doerr, Benjamin
    INFORMATION PROCESSING LETTERS, 2013, 113 (19-21) : 747 - 749
  • [37] Approximation Algorithms for the Min-Max Cycle Cover Problem With Neighborhoods
    Deng, Lijia
    Xu, Wenzheng
    Liang, Weifa
    Peng, Jian
    Zhou, Yingjie
    Duan, Lei
    Das, Sajal K.
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2020, 28 (04) : 1845 - 1858
  • [38] Min-Max Propagation
    Srinivasa, Christopher
    Givoni, Inmar
    Ravanbakhsh, Siamak
    Frey, Brendan J.
    ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 30 (NIPS 2017), 2017, 30
  • [39] Approximation Algorithms for the Capacitated Min-Max Correlation Clustering Problem
    Ji, Sai
    Li, Jun
    Wu, Zijun
    Xu, Yicheng
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2023, 40 (01)
  • [40] Approximation Algorithm for Min-Max Correlation Clustering Problem with Outliers
    Ji, Sai
    Li, Min
    Liang, Mei
    Zhang, Zhenning
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2021, 2021, 13135 : 668 - 675
12345