New differential approximation algorithm for k-customer vehicle routing problem

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.