Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.06079 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912316482650112 |
|---|---|
| author | Raghvendra, Sharath Shirzadian, Pouyan Sowle, Rachita |
| author_facet | Raghvendra, Sharath Shirzadian, Pouyan Sowle, Rachita |
| contents | 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 $\ell_p$ metric space, we present an $\tilde{O}(\min\{nk, n^{2-\frac{1}{2d+1}}\log Δ\}\cdot Φ(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\cup B$ into rectangles. It maintains a minimum-cost partial matching where any point $b \in B$ is either matched to a point $a\in 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 $\tilde{O}(n^{1-\frac{1}{2d+1}}\log Δ)$ number of augmenting paths, leading to a total execution time of $\tilde{O}(n^{2-\frac{1}{2d+1}}Φ(n)\log Δ)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06079 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Geometric Bipartite Matching Based Exact Algorithms for Server Problems Raghvendra, Sharath Shirzadian, Pouyan Sowle, Rachita Computational Geometry 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 $\ell_p$ metric space, we present an $\tilde{O}(\min\{nk, n^{2-\frac{1}{2d+1}}\log Δ\}\cdot Φ(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\cup B$ into rectangles. It maintains a minimum-cost partial matching where any point $b \in B$ is either matched to a point $a\in 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 $\tilde{O}(n^{1-\frac{1}{2d+1}}\log Δ)$ number of augmenting paths, leading to a total execution time of $\tilde{O}(n^{2-\frac{1}{2d+1}}Φ(n)\log Δ)$. |
| title | Geometric Bipartite Matching Based Exact Algorithms for Server Problems |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2504.06079 |