Geometric Bipartite Matching Based Exact Algorithms for Server Problems

Sharath Raghvendra, Pouyan Shirzadian, Rachita Sowle

Abstract

This paper introduces the first sub-quadratic exact algorithm for the offline $k$-server problem in geometric settings. By reducing the problem to a novel "extended" bipartite matching framework and utilizing hierarchical spatial partitioning, the authors achieve a significant speedup over traditional $O(nk)$ methods for points in $d$-dimensional space.

Introduction

The $k$-server problem is a cornerstone of online algorithms and operations research. It involves $k$ mobile servers and a sequence of request locations; the goal is to move servers to satisfy requests while minimizing total distance. While the online version is widely studied, the offline version—where the entire request sequence is known beforehand—is essential for establishing optimal benchmarks.

Traditionally, the offline problem is solved via reduction to minimum-cost flow or bipartite matching. However, standard geometric matching algorithms often scale quadratically $O(n^2)$ or as $O(nk)$, which becomes computationally prohibitive as the number of requests ($n$) and servers ($k$) increases. This work targets a sub-quadratic complexity by minimizing queries to geometric data structures, effectively breaking the $O(nk)$ barrier for geometric metric spaces.

Geometric Primal-Dual Framework

The proposed algorithm is built upon a Geometric Primal-Dual Framework consisting of three primary components:

  1. Hierarchical Partitioning: The $d$-dimensional space is recursively divided into axis-parallel rectangles (cells). Dividers are strategically chosen to pass through sparse regions, minimizing the number of points near boundaries.
  2. Extended Bipartite Matching: Unlike standard matching where points must pair directly, this "extended" version allows points within a cell to match either to another point in the same cell or to the cell's boundary. This localization allows sub-problems to be solved independently at the leaf level.
  3. The Merge Step: Processing proceeds from leaf cells upward. When two cells merge, their shared boundary is removed. Points previously matched to that boundary become "free" and are re-matched using a specialized version of the Hungarian algorithm.
Hierarchical spatial partitioning and extended bipartite matching, where points can match to cell boundaries to allow local sub-problem optimization.

Key Insights and Results

The efficiency of the algorithm stems from the observation that in an optimal matching, only a small fraction of points need to be matched across cell boundaries. The authors prove that the number of augmenting paths required to refine a matching is limited by the underlying geometry.

The merge step resolves boundary matches. By exploiting geometric sparsity, the algorithm efficiently re-matches points across previously divided regions.

Theoretical Complexity

  • 2D Plane: $\tilde{O}(n^{1.8} \Phi(n) \log \Delta)$ time, where $\Phi(n)$ is the nearest-neighbor search time and $\Delta$ is the spread.
  • High Dimensions ($d$): $\tilde{O}(n^{2-\frac{1}{2d+1}} \Phi(n) \log \Delta)$.
  • Stochastic Distribution: For points distributed uniformly at random, the expected time improves to $\tilde{O}(n^{7/4} \Phi(n) \log \Delta)$.

These results represent a significant theoretical advancement over the previous state-of-the-art $O(nk \Phi(n))$ algorithms, particularly when $k$ is large.

Conclusion and Future Work

While the algorithm introduces a sub-quadratic bound, it retains a logarithmic dependency on the spread ($\Delta$)—the ratio of the point set's diameter to the minimum distance between points. Whether this dependency can be entirely removed remains an open question. Additionally, while focused on the offline problem, the reduction to dense bipartite matching may offer improvements for the Work Function Algorithm used in online $k$-server scenarios. Extending these bounds to more general metric spaces, such as those with low doubling dimension, is a key area for future research.

Summary updated

Abstract

For any given metric space, obtaining an offline optimal solution to the classical k-server problem can be reduced to solving a minimum-cost partial bipartite matching between two point sets A and B within that metric space. For d-dimensional 𝓁_p metric space, we present an Õ(min{nk, n^{2-1/(2d+1)}log Δ}⋅ Φ(n)) time algorithm for solving this instance of minimum-cost partial bipartite matching; here, Δ represents the spread of the point set, and Φ(n) is the query/update time of a d-dimensional dynamic weighted nearest neighbor data structure. Our algorithm improves upon prior algorithms that require at least Ω(nkΦ(n)) time. The design of minimum-cost (partial) bipartite matching algorithms that make sub-quadratic queries to a weighted nearest-neighbor data structure, even for bounded spread instances, is a major open problem in computational geometry. We resolve this problem at least for the instances that are generated by the offline version of the k-server problem. Our algorithm employs a hierarchical partitioning approach, dividing the points of A∪ B into rectangles. It maintains a partial minimum-cost matching where any point b ∈ B is either matched to another point a ∈ A or to the boundary of the rectangle it is located in. The algorithm involves iteratively merging pairs of rectangles by erasing the shared boundary between them and recomputing the minimum-cost partial matching. This continues until all boundaries are erased and we obtain the desired minimum-cost partial matching of A and B. We exploit geometry in our analysis to show that each point participates in only Õ(n^{1-1/(2d+1)}log Δ) number of augmenting paths, leading to a total execution time of Õ(n^{2-1/(2d+1)}Φ(n)log Δ). We also show that, for the 𝓁₁ norm and d dimensions, any algorithm that can solve instances of the offline n-server problem with an exponential spread in T(n) time can be used to compute minimum-cost bipartite matching in a complete graph defined on two (d-1)-dimensional point sets under the 𝓁₁ norm within T(n) time. This suggests that removing spread from the execution time of our algorithm may be difficult as it immediately results in a sub-quadratic algorithm for bipartite matching under the 𝓁₁ norm.
BibTeX
@inproceedings{raghvendra2025geometric,
  author = {Sharath Raghvendra and Pouyan Shirzadian and Rachita Sowle},
  title = {{Geometric Bipartite Matching Based Exact Algorithms for Server Problems}},
  booktitle = {SoCG},
  year = {2025},
  url = {https://openreview.net/forum?id=C2xxQU63rj},
}
Figure