arXiv preprint ·
Routing Multiple Agents Below the Sum of Distances
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study Transient Multiagent Pathfinding, a variant of the classical Multi-Agent Pathfinding problem in which a set of agents must be routed without collisions from designated start vertices to designated destination vertices in a graph. We analyze the problem within the above-and-below-guarantee paradigm of parameterized complexity. In particular, we consider the natural upper bound \(L\), given by the sum of the shortest-path distances between pairs of agents' terminals (corresponding to sequential routing of the agents). The parameterization is given by the gap \(ζ= L - λ\) between this bound and the target makespan \(λ\), together with the number \(k\) of agents. Our main result establishes fixed-parameter tractability for the combined parameter \(k + ζ\). Matching lower bounds show that parameterization by \(k\) alone is W[1]-hard, and that parameterization by \(ζ\) alone is W[1]-hard when terminals are not required to be distinct. On the positive side, if all terminals are distinct, the problem becomes fixed-parameter tractable when parameterized solely by \(ζ\). Finally, we show that Transient Multiagent Pathfinding is unlikely to admit a polynomial kernel when parameterized by \(k + ζ\). Together, our results provide an almost complete characterization of the parameterized complexity landscape of the problem for the considered parameters.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Efficient Algorithms for Subdeterminant Maximization under Partition Matroids
Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
Improved Algorithms for Beck--Fiala with Bounded Sets
Optimizing Both Checking and Update Costs in Random Walk Search
Integrality gap preserving reductions
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.