Approximation hardness of min-max tree covers

Zhou Xu; Qi Wen

doi:10.1016/j.orl.2010.02.004

Approximation hardness of min-max tree covers

Zhou Xu^*
, Qi Wen

^*Corresponding author for this work

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

39 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	169-173
Journal	Operations Research Letters
Volume	38
Issue number	3
Online published	10 Feb 2010
DOIs	https://doi.org/10.1016/j.orl.2010.02.004
Publication status	Published - May 2010

Research Keywords

Inapproximability bound
Min-max
Tree covers
Vehicle routing

Access Output

10.1016/j.orl.2010.02.004

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{18cfa812cc3c45e8885adcaafcf12edf,

title = "Approximation hardness of min-max tree covers",

abstract = "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. ",

keywords = "Inapproximability bound, Min-max, Tree covers, Vehicle routing",

author = "Zhou Xu and Qi Wen",

year = "2010",

month = may,

doi = "10.1016/j.orl.2010.02.004",

language = "English",

volume = "38",

pages = "169--173",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Approximation hardness of min-max tree covers

AU - Xu, Zhou

AU - Wen, Qi

PY - 2010/5

Y1 - 2010/5

N2 - 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.

AB - 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.

KW - Inapproximability bound

KW - Min-max

KW - Tree covers

KW - Vehicle routing

UR - https://www.scopus.com/pages/publications/77949915632

UR - https://www.scopus.com/pages/publications/77949915632#tab=impact

U2 - 10.1016/j.orl.2010.02.004

DO - 10.1016/j.orl.2010.02.004

M3 - RGC 21 - Publication in refereed journal

SN - 0167-6377

VL - 38

SP - 169

EP - 173

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

Approximation hardness of min-max tree covers

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Corrigendum to "Approximation hardness of min-max tree covers" [Oper. Res. Lett. 38 (3) (2010) 169-173]

Cite this