I know that there is a 1.5 approximate solution for metric traveling salesman problem (TSP), e.g., Christofedes algorithm guarantees this. Is there an algorithm that guarantees a constant factor approximate solution for CVRP as well?

I searched papers but could not find anything except for some very special cases where constant factor is achieved, but not for general metric CVRP.

  • 1
    $\begingroup$ Maybe this link would be useful. $\endgroup$
    – A.Omidi
    Commented May 9 at 16:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.