Unsplittable Euclidean Capacitated Vehicle Routing: A 2+\epsilon)(2+ϵ)-Approximation Algorithm

on YouTube ↗22m

" summary

Proves a 2+ε approximation for unsplittable Euclidean CVRP with arbitrary demands by clustering small terminals in each cell into ε-sized groups, moving terminals to cell centers, and reducing to a big-demand instance solved via adaptive rounding and enumerated configurations; uses Baker-style bounded-distance, iterated tour partitioning for clustering, and Aurora’s TSP scheme when the optimal has few tours. Also gives 1+ε for big demands only, beats prior 2.694 bound, lower bound 1.5.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:32Capacitated vehicle routing problem (CVRP)
3. 5:40Euclidean CVRP for big demands only
4. 6:45Reducing the number of locations (1/3)
5. 10:36Summary for big demands only
6. 11:29Warm up: Iterated tour partitioning
7. 14:52Case 1: Optimal solution has sufficiently many tours (1/3)
8. 18:42Case 2: Optimal solution has a bounded number of tours