DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2025.72

Geometric Bipartite Matching Based Exact Algorithms for Server Problems

Authors: Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

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 Õ(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 Õ(n^{1-1/(2d+1)}log Δ) number of augmenting paths, leading to a total execution time of Õ(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.

Cite as

Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle. Geometric Bipartite Matching Based Exact Algorithms for Server Problems. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{raghvendra_et_al:LIPIcs.SoCG.2025.72,
  author =	{Raghvendra, Sharath and Shirzadian, Pouyan and Sowle, Rachita},
  title =	{{Geometric Bipartite Matching Based Exact Algorithms for Server Problems}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{72:1--72:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.72},
  URN =		{urn:nbn:de:0030-drops-232240},
  doi =		{10.4230/LIPIcs.SoCG.2025.72},
  annote =	{Keywords: Minimum-Cost Bipartite Matching, Server Problems, Primal-Dual Approach}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2022.6

An Improved ε-Approximation Algorithm for Geometric Bipartite Matching

Authors: Pankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract

For two point sets A, B ⊂ ℝ^d, with |A| = |B| = n and d > 1 a constant, and for a parameter ε > 0, we present a randomized algorithm that, with probability at least 1/2, computes in O(n(ε^{-O(d³)}log log n + ε^{-O(d)}log⁴ nlog⁵log n)) time, an ε-approximate minimum-cost perfect matching under any L_p-metric. All previous algorithms take n(ε^{-1}log n)^{Ω(d)} time. We use a randomly-shifted tree, with a polynomial branching factor and O(log log n) height, to define a tree-based distance function that ε-approximates the L_p metric as well as to compute the matching hierarchically. Then, we apply the primal-dual framework on a compressed representation of the residual graph to obtain an efficient implementation of the Hungarian-search and augment operations.

Cite as

Pankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle. An Improved ε-Approximation Algorithm for Geometric Bipartite Matching. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SWAT.2022.6,
  author =	{Agarwal, Pankaj K. and Raghvendra, Sharath and Shirzadian, Pouyan and Sowle, Rachita},
  title =	{{An Improved \epsilon-Approximation Algorithm for Geometric Bipartite Matching}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.6},
  URN =		{urn:nbn:de:0030-drops-161660},
  doi =		{10.4230/LIPIcs.SWAT.2022.6},
  annote =	{Keywords: Euclidean bipartite matching, approximation algorithms, primal dual method}
}

Search Results

Documents authored by Shirzadian, Pouyan

Geometric Bipartite Matching Based Exact Algorithms for Server Problems

Abstract

Cite as

An Improved ε-Approximation Algorithm for Geometric Bipartite Matching

Abstract

Cite as

Thanks for your feedback!

Could not send message