Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/13581
Title: Approximation hardness of min-max tree covers
Authors: Xu, Z 
Wen, Q
Keywords: Inapproximability bound
Min-max
Tree covers
Vehicle routing
Issue Date: 2010
Publisher: Elsevier Science Bv
Source: Operations research letters, 2010, v. 38, no. 3, p. 169-173 How to cite?
Journal: Operations Research Letters 
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.
URI: http://hdl.handle.net/10397/13581
DOI: 10.1016/j.orl.2010.02.004
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

11
Last Week
0
Last month
1
Citations as of Jun 19, 2017

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
0
Citations as of Jun 21, 2017

Page view(s)

36
Last Week
0
Last month
Checked on Jun 18, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.