05722013

j

05722013 Nagoya, Takayuki New differential approximation algorithm for $k$-customer vehicle routing problem. Inf. Process. Lett. 109, No. 8, 405-408 (2009). 2009 Elsevier Sciences Publishers (North-Holland), Amsterdam EN approximation algorithms vehicle routing problem differential approximation ratio

doi:10.1016/j.ipl.2008.12.018

Summary: We present a differential approximation algorithm for $k$-customer vehicle routing problem. It is known that this problem is $\frac{1}{2}$ differential approximable for $k \geqslant 3$. It is also known that, if the triangle inequality is satisfied, then this problem is $\frac{3}{5}$ differential approximable for $k=4$ and $\frac{2}{3}$ differential approximable for $5 \leqslant k \leqslant 8$. Our algorithm achieves $\frac{3}{5}$ differential approximation ratio for $k=4$ and $\frac{2}{3}$ differential approximation ratio for $k \geqslant 5$ without assuming the triangle inequality holds.