TY - GEN
T1 - A Tight (1.5 + ϵ)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees
AU - Mathieu, Claire
AU - Zhou, Hang
N1 - Publisher Copyright:
© Claire Mathieu and Hang Zhou.
PY - 2023/7/1
Y1 - 2023/7/1
N2 - In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the root of the tree such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. For the special case when all terminals have equal demands, a long line of research culminated in a quasi-polynomial time approximation scheme [Jayaprakash and Salavatipour, TALG 2023] and a polynomial time approximation scheme [Mathieu and Zhou, TALG 2023]. In this work, we study the general case when the terminals have arbitrary demands. Our main contribution is a polynomial time (1.5 + ϵ)-approximation algorithm for the UCVRP on trees. This is the first improvement upon the 2-approximation algorithm more than 30 years ago. Our approximation ratio is essentially best possible, since it is NP-hard to approximate the UCVRP on trees to better than a 1.5 factor.
AB - In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the root of the tree such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. For the special case when all terminals have equal demands, a long line of research culminated in a quasi-polynomial time approximation scheme [Jayaprakash and Salavatipour, TALG 2023] and a polynomial time approximation scheme [Mathieu and Zhou, TALG 2023]. In this work, we study the general case when the terminals have arbitrary demands. Our main contribution is a polynomial time (1.5 + ϵ)-approximation algorithm for the UCVRP on trees. This is the first improvement upon the 2-approximation algorithm more than 30 years ago. Our approximation ratio is essentially best possible, since it is NP-hard to approximate the UCVRP on trees to better than a 1.5 factor.
KW - approximation algorithms
KW - capacitated vehicle routing
KW - combinatorial optimization
KW - graph algorithms
U2 - 10.4230/LIPIcs.ICALP.2023.91
DO - 10.4230/LIPIcs.ICALP.2023.91
M3 - Conference contribution
AN - SCOPUS:85159723477
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
A2 - Etessami, Kousha
A2 - Feige, Uriel
A2 - Puppis, Gabriele
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
Y2 - 10 July 2023 through 14 July 2023
ER -