Reproduce “Parameterized Complexity of Vehicle Routing” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Michelle Döring, Jan Fehse, Tobias Friedrich, Paula Marten, Niklas Mohrin, Kirill Simonov, Farehe Soheil, Jakob Timm and 1 more
The paper studies vehicle routing on weighted networks with depots, clients, and a travel-cost budget. For uncapacitated routes, the authors give an FPT algorithm parameterized by treewidth, with running time 2^{O(tw log tw)}n^{O(1)}. Capacitated variants have hardness results, including on trees, and XP algorithms when treewidth and capacities are combined; whether these cases are FPT remains open.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.