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

Research output: Journal article publication › Journal article › Academic research › 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
Number of pages	5
Journal	Operations Research Letters
Volume	38
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2010.02.004
Publication status	Published - 1 May 2010

Keywords

Inapproximability bound
Min-max
Tree covers
Vehicle routing

ASJC Scopus subject areas

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

More information

10.1016/j.orl.2010.02.004

Cite this

@article{4ce0bae078374adfa806437f18ef279a,

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,

day = "1",

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/1

Y1 - 2010/5/1

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

U2 - 10.1016/j.orl.2010.02.004

DO - 10.1016/j.orl.2010.02.004

M3 - Journal article

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

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this