Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/17498
Title: Approximation results for a min-max location-routing problem
Authors: Xu, Z 
Xu, D
Zhu, W
Keywords: Approximation algorithm
Approximation hardness
Minmax location-routing
Issue Date: 2012
Publisher: Elsevier Science Bv
Source: Discrete applied mathematics, 2012, v. 160, no. 3, p. 306-320 How to cite?
Journal: Discrete Applied Mathematics 
Abstract: This paper studies a minmax location-routing problem, which aims to determine both the home depots and the tours for a set of vehicles to service all the customers in a given weighted graph, so that the maximum working time of the vehicles is minimized. The minmax objective is motivated by the needs of balancing or fairness in vehicle routing applications. We have proved that unless NP=P, it is impossible for the problem to have an approximation algorithm that achieves an approximation ratio of less than 4/3. Thus, we have developed the first constant ratio approximation algorithm for the problem. Moreover, we have developed new approximation algorithms for several variants, which improve the existing best approximation ratios in the previous literature.
URI: http://hdl.handle.net/10397/17498
DOI: 10.1016/j.dam.2011.09.014
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

7
Last Week
0
Last month
1
Citations as of Aug 21, 2017

WEB OF SCIENCETM
Citations

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

Page view(s)

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