| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428703 | Information Processing Letters | 2009 | 4 Pages |
Abstract
We present a differential approximation algorithm for k-customer vehicle routing problem. It is known that this problem is differential approximable for k⩾3. It is also known that if the triangle inequality is satisfied then this problem is differential approximable for k=4 and differential approximable for 5⩽k⩽8. Our algorithm achieves differential approximation ratio for k=4 and differential approximation ratio for k⩾5 without assuming the triangle inequality holds.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
