The Vehicle Routing Problem (VRP) is a fundamental optimization problem in Operations Research and theoretical computer science and has been studied in many variations. In this presentation we have a look at some well-known approximation algorithms for the capacitated vehicle routing problem (CVRP) and then discuss a recent result on the Euclidean version, where all points are in the Euclidean plane. It has been a long-standing conjecture that a Polynomial Time Approximation Scheme (PTAS) for the Euclidean CVRP should exist. We make a big step towards proving this conjecture and present a so called quasi-PTAS for the capacitated VRP, where the running time is n^{O(log(log n))}. This is a major improvement over the so far best-known running time.
René Sitters: Towards a PTAS for the Euclidean CVRP. 19 November 2025 16:00 - 17:00
About René Sitters: Towards a PTAS for the Euclidean CVRP.
Starting date
- 19 November 2025
Time
- 16:00 - 17:00
Location
- VU Main Building
Address
- De Boelelaan 1105
- 1081 HV Amsterdam
Organised by
- Operations Analytics
Language
- English
René Sitters
Rene Sitters is associate professor at the department of Supply Chain Analytics at the Vrije Universiteit Amsterdam. His research focuses on algorithms for and complexity of combinatorial optimization problems.
Interested in attending the seminar or in giving a talk?
Please send an email to Tim Oosterwijk