{"ID":2892229,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.15549","arxiv_id":"2507.15549","title":"An $n^{O(\\log\\log n)}$ time approximation scheme for capacitated VRP in the Euclidean plane","abstract":"We present a quasi polynomial time approximation scheme (Q-PTAS) for the capacitated vehicle routing problem (CVRP) on $n$ points in the Euclidean plane for arbitrary capacity $c$. The running time is $n^{f(ε)\\cdot\\log\\log n}$ for any $c$, and where $f$ is a function of $ε$ only. This is a major improvement over the so far best known running time of $n^{\\log^{O(1/ε)}n}$ time and a big step towards a PTAS for Euclidean CVRP. In our algorithm, we first give a polynomial time reduction of the CVRP in $\\mathbb{R}^d$ (for any fixed $d$) to an uncapacitated routing problem in $\\mathbb{R}^d$ that we call the $m$-paths problem. Here, one needs to find exactly $m$ paths between two points $a$ and $b$, covering all the given points in the Euclidean space. We then give a Q-PTAS for the $m$-paths problem in the pane. Any PTAS for the (arguably easier to handle) Euclidean $m$-paths problem is most likely to imply a PTAS for the Euclidean CVRP.","short_abstract":"We present a quasi polynomial time approximation scheme (Q-PTAS) for the capacitated vehicle routing problem (CVRP) on $n$ points in the Euclidean plane for arbitrary capacity $c$. The running time is $n^{f(ε)\\cdot\\log\\log n}$ for any $c$, and where $f$ is a function of $ε$ only. This is a major improvement over the so...","url_abs":"https://arxiv.org/abs/2507.15549","url_pdf":"https://arxiv.org/pdf/2507.15549v1","authors":"[\"René Sitters\"]","published":"2025-07-21T12:28:05Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}