DROPS

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}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2022.30

A Scalable Work Function Algorithm for the k-Server Problem

Authors: Sharath Raghvendra and Rachita Sowle

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

Abstract

We provide a novel implementation of the classical Work Function Algorithm (WFA) for the k-server problem. In our implementation, processing a request takes O(n²+k²) time per request; where n is the total number of requests and k is the total number of servers. All prior implementations take Ω(kn² +k³) time per request. Previous approaches process a request by solving a min-cost flow problem. Instead, we show that processing a request can be reduced to an execution of the Dijkstra’s shortest-path algorithm on a carefully computed weighted graph leading to the speed-up.

Cite as

Sharath Raghvendra and Rachita Sowle. A Scalable Work Function Algorithm for the k-Server Problem. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{raghvendra_et_al:LIPIcs.SWAT.2022.30,
  author =	{Raghvendra, Sharath and Sowle, Rachita},
  title =	{{A Scalable Work Function Algorithm for the k-Server Problem}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{30:1--30: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.30},
  URN =		{urn:nbn:de:0030-drops-161906},
  doi =		{10.4230/LIPIcs.SWAT.2022.30},
  annote =	{Keywords: k-server, Work Function Algorithm, Minimum-cost Flow}
}

Search Results

Documents authored by Sowle, Rachita

An Improved ε-Approximation Algorithm for Geometric Bipartite Matching

Abstract

Cite as

A Scalable Work Function Algorithm for the k-Server Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message