Geometry Seminar

---

Sub-Quadratic Exact Algorithms for Geometric k-Disjoint Path Cover via Euclidean Bipartite Matching

Speaker: Sharath Raghvendra, North Carolina State

Location: Online

Date: Tuesday, November 18, 2025, 2 p.m.

Synopsis:

We study the geometric k-disjoint path cover problem, where a sequence of requests arrives over time and the goal is to construct k vertex-disjoint paths that collectively serve all requests in order of arrival while minimizing the total cost. This problem is also the offline version of the classical k-server problem.

In this talk, I will present a sub-quadratic-time exact algorithm for Euclidean instances of this problem, obtained via a reduction to Euclidean bipartite matching. Although no general sub-quadratic algorithms are known for exact Euclidean matching, we show that the structured instances arising from the path cover formulation admit a more efficient solution. Our analysis leverages the geometric and temporal properties of the request sequence to achieve these improvements.

Furthermore, our approach extends to a stochastic variant of Euclidean bipartite matching, where the bipartite graph is formed from two sets of n points independently drawn from the same unknown distribution inside a unit square, and we again obtain a sub-quadratic time exact solution.

Notes:

On Zoom.  Please contact Boris Aronov to be put on the email announcement list and obtain Zoom details.