PTAS for ktour cover poblem on the plane for moderately large values of k
(2010) In International Journal of Foundations of Computer Science 21(6). p.893904 Abstract
 Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the ktour cover problem (called frequently the capacitated vehicle routing problem), the goal is to minimize the total length of tours that cover all points in P, such that each tour starts and ends in O and covers at most k points from P. The ktour cover problem is known to be NPhard. It is also known to admit constant factor approximation algorithms for all values of k and even a polynomialtime approximation scheme (PTAS) for small values of k, k = circle divide (log n/ log log n). In this paper, we significantly enlarge the set of values of k for which a PTAS is provable. We present a new PTAS for all values of k <= 2(log delta n),... (More)
 Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the ktour cover problem (called frequently the capacitated vehicle routing problem), the goal is to minimize the total length of tours that cover all points in P, such that each tour starts and ends in O and covers at most k points from P. The ktour cover problem is known to be NPhard. It is also known to admit constant factor approximation algorithms for all values of k and even a polynomialtime approximation scheme (PTAS) for small values of k, k = circle divide (log n/ log log n). In this paper, we significantly enlarge the set of values of k for which a PTAS is provable. We present a new PTAS for all values of k <= 2(log delta n), where delta = delta(epsilon). The main technical result proved in the paper is a novel reduction of the ktour cover problem with a set of n points to a small set of instances of the problem, each with circle divide((k/epsilon)(circle divide(1))) points. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1859794
 author
 Adamaszek, Anna ; Czumaj, Artur and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2010
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Approximation algorithms, capacitated vehicle routing, ktour cover, polynomialtime approximation scheme
 in
 International Journal of Foundations of Computer Science
 volume
 21
 issue
 6
 pages
 893  904
 publisher
 World Scientific
 external identifiers

 wos:000286806000003
 scopus:78649403560
 ISSN
 01290541
 DOI
 10.1142/S0129054110007623
 language
 English
 LU publication?
 yes
 id
 1b34a2c36b7e4836a9f750f22151f8cb (old id 1859794)
 date added to LUP
 20160401 09:58:17
 date last changed
 20200119 03:07:52
@article{1b34a2c36b7e4836a9f750f22151f8cb, abstract = {Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the ktour cover problem (called frequently the capacitated vehicle routing problem), the goal is to minimize the total length of tours that cover all points in P, such that each tour starts and ends in O and covers at most k points from P. The ktour cover problem is known to be NPhard. It is also known to admit constant factor approximation algorithms for all values of k and even a polynomialtime approximation scheme (PTAS) for small values of k, k = circle divide (log n/ log log n). In this paper, we significantly enlarge the set of values of k for which a PTAS is provable. We present a new PTAS for all values of k <= 2(log delta n), where delta = delta(epsilon). The main technical result proved in the paper is a novel reduction of the ktour cover problem with a set of n points to a small set of instances of the problem, each with circle divide((k/epsilon)(circle divide(1))) points.}, author = {Adamaszek, Anna and Czumaj, Artur and Lingas, Andrzej}, issn = {01290541}, language = {eng}, number = {6}, pages = {893904}, publisher = {World Scientific}, series = {International Journal of Foundations of Computer Science}, title = {PTAS for ktour cover poblem on the plane for moderately large values of k}, url = {http://dx.doi.org/10.1142/S0129054110007623}, doi = {10.1142/S0129054110007623}, volume = {21}, year = {2010}, }