Search Results

Documents authored by Raghvendra, Sharath

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 Õ(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.
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}
}
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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.48
A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings

Authors: Nathaniel Lahn and Sharath Raghvendra

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph G(A cup B,E) with edge weights of 0 or 1. Let w <= n be an upper bound on the weight of any matching in G. Consider the subgraph induced by all the edges of G with a weight 0. Suppose every connected component in this subgraph has O(r) vertices and O(mr/n) edges. We present an algorithm to compute a maximum cardinality matching in G in O~(m(sqrt{w} + sqrt{r} + wr/n)) time. When all the edge weights are 1 (symmetrically when all weights are 0), our algorithm will be identical to the well-known Hopcroft-Karp (HK) algorithm, which runs in O(m sqrt{n}) time. However, if we can carefully assign weights of 0 and 1 on its edges such that both w and r are sub-linear in n and wr=O(n^{gamma}) for gamma < 3/2, then we can compute maximum cardinality matching in G in o(m sqrt{n}) time. Using our algorithm, we obtain a new O~(n^{4/3}/epsilon^4) time algorithm to compute an epsilon-approximate bottleneck matching of A,B subsetR^2 and an 1/(epsilon^{O(d)}}n^{1+(d-1)/(2d-1)}) poly log n time algorithm for computing epsilon-approximate bottleneck matching in d-dimensions. All previous algorithms take Omega(n^{3/2}) time. Given any graph G(A cup B,E) that has an easily computable balanced vertex separator for every subgraph G'(V',E') of size |V'|^{delta}, for delta in [1/2,1), we can apply our algorithm to compute a maximum matching in O~(mn^{delta/1+delta}) time improving upon the O(m sqrt{n}) time taken by the HK-Algorithm.
Cite as

Nathaniel Lahn and Sharath Raghvendra. A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lahn_et_al:LIPIcs.SoCG.2019.48,
  author =	{Lahn, Nathaniel and Raghvendra, Sharath},
  title =	{{A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{48:1--48:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.48},
  URN =		{urn:nbn:de:0030-drops-104528},
  doi =		{10.4230/LIPIcs.SoCG.2019.48},
  annote =	{Keywords: Bipartite matching, Bottleneck matching}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.67
Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line

Authors: Sharath Raghvendra

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
In the online metric bipartite matching problem, we are given a set S of server locations in a metric space. Requests arrive one at a time, and on its arrival, we need to immediately and irrevocably match it to a server at a cost which is equal to the distance between these locations. A alpha-competitive algorithm will assign requests to servers so that the total cost is at most alpha times the cost of M_{Opt} where M_{Opt} is the minimum cost matching between S and R. We consider this problem in the adversarial model for the case where S and R are points on a line and |S|=|R|=n. We improve the analysis of the deterministic Robust Matching Algorithm (RM-Algorithm, Nayyar and Raghvendra FOCS'17) from O(log^2 n) to an optimal Theta(log n). Previously, only a randomized algorithm under a weaker oblivious adversary achieved a competitive ratio of O(log n) (Gupta and Lewi, ICALP'12). The well-known Work Function Algorithm (WFA) has a competitive ratio of O(n) and Omega(log n) for this problem. Therefore, WFA cannot achieve an asymptotically better competitive ratio than the RM-Algorithm.
Cite as

Sharath Raghvendra. Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{raghvendra:LIPIcs.SoCG.2018.67,
  author =	{Raghvendra, Sharath},
  title =	{{Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.67},
  URN =		{urn:nbn:de:0030-drops-87803},
  doi =		{10.4230/LIPIcs.SoCG.2018.67},
  annote =	{Keywords: Bipartite Matching, Online Algorithms, Adversarial Model, Line Metric}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.28
Improved Approximate Rips Filtrations with Shifted Integer Lattices

Authors: Aruni Choudhary, Michael Kerber, and Sharath Raghvendra

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Rips complexes are important structures for analyzing topological features of metric spaces. Unfortunately, generating these complexes constitutes an expensive task because of a combinatorial explosion in the complex size. For n points in R^d, we present a scheme to construct a 4.24-approximation of the multi-scale filtration of the Rips complex in the L-infinity metric, which extends to a O(d^{0.25})-approximation of the Rips filtration for the Euclidean case. The k-skeleton of the resulting approximation has a total size of n2^{O(d log k)}. The scheme is based on the integer lattice and on the barycentric subdivision of the d-cube.
Cite as

Aruni Choudhary, Michael Kerber, and Sharath Raghvendra. Improved Approximate Rips Filtrations with Shifted Integer Lattices. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.ESA.2017.28,
  author =	{Choudhary, Aruni and Kerber, Michael and Raghvendra, Sharath},
  title =	{{Improved Approximate Rips Filtrations with Shifted Integer Lattices}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.28},
  URN =		{urn:nbn:de:0030-drops-78259},
  doi =		{10.4230/LIPIcs.ESA.2017.28},
  annote =	{Keywords: Persistent homology, Rips filtrations, Approximation algorithms, Topological Data Analysis}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.18
A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching

Authors: Sharath Raghvendra

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
We study the Online Minimum Metric Bipartite Matching Problem. In this problem, we are given point sets S and R which correspond to the server and request locations; here |S|=|R|=n. All these locations are points from some metric space and the cost of matching a server to a request is given by the distance between their locations in this space. In this problem, the request points arrive one at a time. When a request arrives, we must immediately and irrevocably match it to a "free" server. The matching obtained after all the requests are processed is the online matching M. The cost of M is the sum of the cost of its edges. The performance of any online algorithm is the worst-case ratio of the cost of its online solution M to the minimum-cost matching. We present a deterministic online algorithm for this problem. Our algorithm is the first to simultaneously achieve optimal performances in the well-known adversarial and the random arrival models. For the adversarial model, we obtain a competitive ratio of 2n-1 + o(1); it is known that no deterministic algorithm can do better than 2n-1. In the random arrival model, our algorithm obtains a competitive ratio of 2H_n - 1 + o(1); where H_n is the n-th Harmonic number. We also prove that any online algorithm will have a competitive ratio of at least 2H_n - 1-o(1) in this model. We use a new variation of the offline primal-dual method for computing minimum cost matching to compute the online matching. Our primal-dual method is based on a relaxed linear-program. Under metric costs, this specific relaxation helps us relate the cost of the online matching with the offline matching leading to its robust properties.
Cite as

Sharath Raghvendra. A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{raghvendra:LIPIcs.APPROX-RANDOM.2016.18,
  author =	{Raghvendra, Sharath},
  title =	{{A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.18},
  URN =		{urn:nbn:de:0030-drops-66410},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.18},
  annote =	{Keywords: Online Algorithms, Metric Bipartite Matching}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.31
Polynomial-Sized Topological Approximations Using the Permutahedron

Authors: Aruni Choudhary, Michael Kerber, and Sharath Raghvendra

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Classical methods to model topological properties of point clouds, such as the Vietoris-Rips complex, suffer from the combinatorial explosion of complex sizes. We propose a novel technique to approximate a multi-scale filtration of the Rips complex with improved bounds for size: precisely, for n points in R^d, we obtain a O(d)-approximation with at most n2^{O(d log k)} simplices of dimension k or lower. In conjunction with dimension reduction techniques, our approach yields a O(polylog (n))-approximation of size n^{O(1)} for Rips filtrations on arbitrary metric spaces. This result stems from high-dimensional lattice geometry and exploits properties of the permutahedral lattice, a well-studied structure in discrete geometry. Building on the same geometric concept, we also present a lower bound result on the size of an approximate filtration: we construct a point set for which every (1+epsilon)-approximation of the Cech filtration has to contain n^{Omega(log log n)} features, provided that epsilon < 1/(log^{1+c}n) for c in (0,1).
Cite as

Aruni Choudhary, Michael Kerber, and Sharath Raghvendra. Polynomial-Sized Topological Approximations Using the Permutahedron. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.SoCG.2016.31,
  author =	{Choudhary, Aruni and Kerber, Michael and Raghvendra, Sharath},
  title =	{{Polynomial-Sized Topological Approximations Using the Permutahedron}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.31},
  URN =		{urn:nbn:de:0030-drops-59236},
  doi =		{10.4230/LIPIcs.SoCG.2016.31},
  annote =	{Keywords: Persistent Homology, Topological Data Analysis, Simplicial Approximation, Permutahedron, Approximation Algorithms}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact