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: North-Holland
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
ISSN: 0167-6377
EISSN: 1872-7468
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 Aug 18, 2017

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
0
Citations as of Aug 20, 2017

Page view(s)

43
Last Week
0
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



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