Geometric Bipartite Matching Based Exact Algorithms for Server Problems

Consider a sequence of requests $\varsigma =⟨r_1,\mathrm{\dots },r_m⟩$ in a metric space equipped with the cost function $\mathrm{d}(\cdot ,\cdot )$. The cost of a single server servicing the requests in $\varsigma$ is the sum of the distances between every consecutive pair of points in the sequence, i.e., $\text{¢}(\varsigma )={\sum }_{i=1}^{m-1}\mathrm{d}(r_i,r_{i+1})$. Given a sequence $\sigma =⟨r_1,\mathrm{\dots }{r}_n⟩$ of $n$ requests and an integer $1\le k\le n$, the $k$-sequence partitioning problem (or simply the $k$-SP problem) requires partitioning the requests in $\sigma$ into $k$ subsequences ${\varsigma }_1,\mathrm{\dots },{\varsigma }_k$ so that ${\sum }_{i=1}^k\text{¢}({\varsigma }_i)$ is minimized. The optimal solution for the $k$-sequence partitioning problem is the cheapest way for $k$ servers to service all of the requests in $\sigma$. We also consider a variant: the $k$-sequence partitioning with initial locations problem (or the $k$-SPI problem). Here, in addition to the requests $\sigma$, we are also given the initial locations $\eta =⟨s_1,\mathrm{\dots },s_k⟩$ for the $k$ servers. The objective of this problem is to partition ${\sigma }^{\prime }=\eta \sigma$ into $k$ subsequences ${\varsigma }_1,\mathrm{\dots },{\varsigma }_k$ so that the initial location $s_j$ of server $j$ appears in the first element of the subsequence ${\varsigma }_j$ and the cost ${\sum }_{i=1}^k\text{¢}({\varsigma }_k)$ is minimized. The optimal solution to the $k$-SPI problem is the offline optimal solution to the well-known $k$-server problem.

We assume that the requests in $\sigma$ and the initial locations in $\eta$ are scaled and translated so that they are contained inside the unit hypercube ${[0,1]}^d$. Such scaling and translation do not impact the optimal solutions for the $k$-SP and $k$-SPI problems. We define the diameter $\mathrm{Diam}(\sigma )$ to be the largest distance between any two request locations in $\sigma$ and the closest pair distance, denoted by $\mathrm{CP}(\sigma )$, to be the smallest non-zero distance between any two requests in $\sigma$. The spread, denoted by $\mathrm{\Delta }$, is the ratio of the diameter to the closest-pair distance, i.e., $\mathrm{\Delta }=\mathrm{Diam}(\sigma )/\mathrm{CP}(\sigma )$.

Consider a weighted bipartite graph $G(A\cup B,E\subseteq A\times B)$, where each edge between $u$ and $v$ is assigned a real-valued cost. Let $n:=\min \{|A|,|B|\}$. A matching of size $t\le n$, or simply a $t$-matching, is a set of $t$ edges in $G$ that are vertex-disjoint. The cost of any matching $M$ is the sum of the costs of its edges. Given a parameter $t\le n$, the minimum-cost bipartite $t$-matching problem seeks to find a $t$-matching with a minimum cost. When $|A|=|B|=n$, a matching of size $n$ is called a perfect matching. When $A$ and $B$ are $d$-dimensional point sets and the cost of any edge between $a\in A$ and $b\in B$ is the ${\mathrm{\ell }}_p$ distance ${\Vert a-b\Vert }_p$, the problem of finding the minimum-cost bipartite $t$-matching is also called the (partial) geometric bipartite matching problem.

Chrobak et al. [4] established a reduction from the minimum-cost bipartite $t$-matching problem to the $k$-SPI problem.

We strengthen the connection between the two problems by showing a reduction in the reverse direction, i.e., we reduce the $k$-SP (resp. $k$-SPI) problem to the minimum-cost bipartite $t$-matching problem. Given an input sequence $\sigma$ of requests to the $k$-SP problem, we construct a bipartite graph ${𝒢}_{\sigma }$ with a vertex set $A\cup B$ and a set of edges $ℰ$ as follows. Vertex Set: For each request $r_i$, we create a vertex $b_i$ (resp. $a_i$) in $B$ (resp. $A$) and designate it as the entry (resp. exit) gate for request $r_i$. Edge Set: The exit gate $a_i$ of request $r_i$ is connected to the entry gate $b_j$ of every subsequent request $r_j$ with $j>i$ with an edge. The cost of this edge is $\mathrm{d}(a_i,b_j)={\Vert r_i-r_j\Vert }_p$. Any minimum-cost $(n-k)$-matching $M$ in ${𝒢}_{\sigma }$ can be used to find an optimal solution to the $k$-SP problem. See Figure 1.

For the $k$-SPI problem, for each server $j$, we add a vertex $a^j$ at the initial location $s_j$ to $A$ and connect $a^j$ to the entry gate $b_i$ of every request $r_i$ in $\sigma$. The cost of this edge is $\mathrm{d}(a^j,b_i)={\Vert s_j-b_i\Vert }_p$. A minimum-cost $n$-matching in this graph can be converted to an optimal solution for the $k$-SPI problem.

A different reduction from $k$-SP and $k$-SPI problems to the minimum-cost flow problem has been presented in previous works [4, 22, 24], leading to the development of $O(n^{2}k)$ time algorithm. However, unlike our reduction, their approach generates instances that include edges whose costs are $-\mathrm{\infty }$ and fails to maintain the metric properties of costs.

Finally, we extend the reduction Chrobak et al. [4] to geometric settings and provide a reduction from the geometric minimum-cost matching problem under the ${\mathrm{\ell }}_1$-norm to the geometric version of the $n$-SPI problem. This reduction, however, creates an instance of the $n$-SPI problem with a spread of $3^n$. Lemma 3 follows directly from this reduction.

For a graph with $m$ edges and $n$ vertices, the classical Hungarian algorithm computes a minimum-cost $t$-matching for all values of $0\le t\le n$ [11, 16]. Starting with an empty matching, the Hungarian algorithm iteratively builds a minimum-cost $i$-matching from the maintained minimum-cost $(i-1)$-matching in $O(m+n\log n)$ time by finding a minimum net-cost augmenting path, i.e., an augmenting path that increases the matching cost by the smallest value. The overall execution time of the Hungarian algorithm is $O(nm+n^2\log n)$, or $O(n^3)$ when $m=\mathrm{\Theta }(n^2)$. Despite substantial efforts, this remains the most efficient algorithm for the problem. Notable exceptions include specialized cases, such as graphs with small vertex separators [13] or integer edge weights [2, 5, 6].

In geometric settings, Vaidya showed that each iteration of the Hungarian algorithm can be implemented in $\tilde{O}(n\mathrm{\Phi }(n))$ time, where $\mathrm{\Phi }(n)$ represents the query/update time of a dynamic weighted nearest neighbor (DWNN) data structure. Thus, the minimum-cost $t$-matching can be computed in $O(n^2\mathrm{\Phi }(n))$ time, which is sub-cubic in $n$ provided $\mathrm{\Phi }(n)$ is sub-linear. For instance, for the ${\mathrm{\ell }}_1$ norm and $d$ dimensions, $\mathrm{\Phi }(n)=O({\log }^{d}n)$ [27] and for the ${\mathrm{\ell }}_2$ norm and $2$ dimensions, $\mathrm{\Phi }(n)={\log }^{O(1)}n$ [8]. In these cases, the Hungarian algorithm can be implemented in near-quadratic time.

Designing algorithms that compute a minimum-cost matching using sub-quadratic DWNN queries remains a central open problem in computational geometry. There are three notable exceptions. First, for points with integer coordinates and the ${\mathrm{\ell }}_1$ and ${\mathrm{\ell }}_{\mathrm{\infty }}$ norms, Sharathkumar and Agarwal [26] adapted a cost-scaling algorithm [5] and presented an algorithm that executes in $\tilde{O}(n^{3/2}\mathrm{\Phi }(n))$ time. Second, Sharathkumar [25] extended this result to 2-dimensional point sets with integer coordinates and the ${\mathrm{\ell }}_2$ costs. Their result, however, relies on planarity as well as the edge costs being the square root of integers and does not extend to $d$-dimensional points with real-valued coordinates. Third, Gattani et al. [7] presented a divide-and-conquer algorithm (GRS algorithm) with a worst-case runtime of $\tilde{O}(n^2\mathrm{\Phi }(n)\log \mathrm{\Delta })$, where $\mathrm{\Delta }$ is the spread of the points. For 2-dimensional stochastic points drawn from an unknown distribution, however, the expected runtime of the GRS algorithm improves to $\tilde{O}(n^{7/4}\mathrm{\Phi }(n)\log \mathrm{\Delta })$.

The GRS algorithm uses a randomly-shifted quadtree to divide the problem into smaller subproblems. Within each square $\mathrm{\square }$ of the quadtree, it recursively computes a minimum-cost extended matching, allowing each point of $B$ in $\mathrm{\square }$ to match either to a point of $A$ in $\mathrm{\square }$ or to the boundaries of $\mathrm{\square }$ (Figure 2(left)). The algorithm then combines the matchings of the child squares by erasing their common boundaries, freeing points of $B$ that were matched to those boundaries (Figure 2(middle)), and then it iteratively matches the freed points.

Gattani et al. [7] showed that for stochastic point sets $A$ and $B$, most points in $B$ will match to a close-by point in $A$ and only $\tilde{O}(n^{3/4})$ points will match to boundaries. Thus, erasing these boundaries creates $\tilde{O}(n^{3/4})$ free points, each again matched in $O(n\mathrm{\Phi }(n))$ time, resulting in an overall runtime of $\tilde{O}(n^{7/4}\mathrm{\Phi }(n))$. However, this efficiency does not extend to arbitrary point sets. For instance, if all points in $A$ lie in one child ${\mathrm{\square }}_1$ and all points in $B$ lie in another child ${\mathrm{\square }}_2$, then all edges of a minimum-cost matching cross the boundaries. In this case, the minimum-cost extended matching in ${\mathrm{\square }}_2$ matches all points in $B$ to its boundary (Figure 2(right)), and erasing the boundary creates $n$ free points. Hence, the merge step takes $\mathrm{\Omega }(n^2\mathrm{\Phi }(n))$ time. Furthermore, unlike the Hungarian algorithm, the GRS algorithm does not guarantee optimal intermediate matchings and cannot compute minimum-cost $t$-matchings.

The optimal solutions to the $k$-SP (resp. $k$-SPI) problems can be computed in $\tilde{O}(nk\mathrm{\Phi }(n))$ time by non-trivially adapting the Hungarian algorithm to find a minimum-cost $(n-k)$-matching (resp. $n$-matching) in ${𝒢}_{\sigma }$ (resp. ${𝒢}_{{\sigma }^{\prime }}$). This algorithm, however, makes quadratic queries to a DWNN data structure when $k=\mathrm{\Theta }(n)$. The main contribution of this paper is the design of a novel algorithm that, for any $k$, computes the optimal solution to the $k$-SP and $k$-SPI problems using only a sub-quadratic number of DWNN queries.

Our algorithm also extends to higher dimensions, and for any dimension $d\ge 2$, it computes optimal solutions to the $k$-SP and $k$-SPI problems in $\tilde{O}(\min \{nk,n^{2-\frac{1}{2d+1}}\log \mathrm{\Delta }\}\cdot \mathrm{\Phi }(n))$ time.

Designing geometric bipartite matching algorithms that perform a sub-quadratic number of queries to a DWNN data structure is challenging. Nevertheless, Theorem 4 shows that the bipartite matching instances generated by $k$-SP and $k$-SPI problems with bounded spread can be solved using sub-quadratic DWNN queries. For unbounded spread cases, the challenge remains elusive, at least for the $k$-SPI problem since, by Lemma 3, such an algorithm yields a sub-quadratic solution for the $d$-dimensional minimum-cost bipartite matching problem under ${\mathrm{\ell }}_1$ costs.

Our algorithm uses a hierarchical partitioning tree, whose nodes (referred to as cells) are axis-parallel rectangles with an aspect ratio of at most $3$, and each cell splits into two smaller rectangles, forming its children. Our algorithm maintains a set of current cells $𝒞$ that partition the input points and computes a minimum-cost extended $(n-k)$-matching, where the points in $B$ are allowed to match to the cell boundaries. It then replaces a pair of sibling rectangles in $𝒞$ with their parent, effectively erasing their shared boundary and creating additional free points. These free points are then matched again by finding minimum net-cost augmenting paths. When all the boundaries are erased, the algorithm terminates with the desired minimum-cost $(n-k)$-matching.

Our efficiency analysis faces three main hurdles. First, while finding a minimum net-cost augmenting path typically requires a search on the entire graph, we show that for extended matchings, such paths lie entirely within a current cell, allowing efficient local searches inside each current cell and selecting the global minimum across cells. Second, bounding the time to merge two cells is challenging, especially since some current cells may hold $\mathrm{\Theta }(n)$ points, where each point is matched to a far away point in the optimal solution (Figure 3(left)). We address this challenge by showing that any minimum-cost extended matching has only $O(n^{0.8})$ points matched to the shared boundary. To establish this, we critically use the fact that every sub-problem has a hidden low-cost high-cardinality matching with sub-linearly many free points (see Figure 3 (right)). Finally, the $k$ free points in our extended matching $M$ may differ from those in the minimum-cost $(n-k)$-matching $M^{\ast }$. For instance, a point $b\in B$ may be free in $M^{\ast }$ but matched to the boundary in $M$, leaving another point $b^{\prime }$ unmatched. While correcting such mismatches via alternating and augmenting paths can take $\mathrm{\Theta }(n)$ time each (leading to a naïve bound of $O(nk)$), we use geometry to show that only $O(n^{0.8})$ such corrections occur for each cell, yielding an overall runtime to $\tilde{O}(n^{1.8}\mathrm{\Phi }(n)\log \mathrm{\Delta })$.

Our proof techniques also refine the analysis of the GRS algorithm when the cost between points $a\in A$ and $b\in B$ is ${\Vert a-b\Vert }_2^q$ for any $q\ge 2$. Prior work showed that the GRS algorithm computes the minimum-cost perfect matching between two 2-dimensional stochastic point sets in $\tilde{O}(n^{2-\frac{1}{2(q+1)}}\mathrm{\Phi }(n))$ time [7], which implies a quadratic number of queries to the DWNN data structure as $q\to \mathrm{\infty }$. Raghvendra et al. [20] observed that, for any $q\ge 1$, there exists a low-cost, high-cardinality matching with sublinear free points. Building on a similar observation and our novel analysis techniques, we show that the GRS algorithm makes only a sub-quadratic number of DWNN queries, regardless of the value of $q$.

The setting originally considered in the analysis of the GRS algorithm [7], where $A$ and $B$ are samples from the same distribution, is a special case of randomly partitioning a set of $2n$ points into two sets $A$ and $B$ of $n$ points, considered in Theorem 5.

Due to space limitations, we restrict the description of our algorithm and its analysis to the $k$-SP problem in $2$ dimensions. All other results, including extensions to higher dimensions, are presented in the full version of our paper.