An $n^{O(\log\log n)}$ time approximation scheme for capacitated VRP in the Euclidean plane
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916853821997056 |
|---|---|
| author | Sitters, René |
| author_facet | Sitters, René |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_15549 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An $n^{O(\log\log n)}$ time approximation scheme for capacitated VRP in the Euclidean plane Sitters, René Data Structures and Algorithms 90 F.2; E.1; G.2 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. |
| title | An $n^{O(\log\log n)}$ time approximation scheme for capacitated VRP in the Euclidean plane |
| topic | Data Structures and Algorithms 90 F.2; E.1; G.2 |
| url | https://arxiv.org/abs/2507.15549 |