{"ID":2860080,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.05321","arxiv_id":"2510.05321","title":"Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding","abstract":"In Capacitated Vehicle Routing with Multiple Depots (CVRP-MD) we are given a set of client locations $C$ and a set of depots $R$ located in a metric space with costs $c(i,j)$ between $u,v \\in C \\cup R$. Additionally, we are given a capacity bound $k$. The goal is to find a collection of tours of minimum total cost such that each tour starts and ends at some depot $r \\in R$ and includes at most $k$ clients and such that each client lies on at least one tour. Our main result is a $3.9365$-approximation based on rounding a new LP relaxation for CVRP-MD.","short_abstract":"In Capacitated Vehicle Routing with Multiple Depots (CVRP-MD) we are given a set of client locations $C$ and a set of depots $R$ located in a metric space with costs $c(i,j)$ between $u,v \\in C \\cup R$. Additionally, we are given a capacity bound $k$. The goal is to find a collection of tours of minimum total cost such...","url_abs":"https://arxiv.org/abs/2510.05321","url_pdf":"https://arxiv.org/pdf/2510.05321v1","authors":"[\"Zachary Friggstad\",\"Tobias Mömke\"]","published":"2025-10-06T19:36:46Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}