3 Search Results for "Panagiotas, Ioannis"

Document

DOI: 10.4230/LIPIcs.AofA.2024.16

Matching Algorithms in the Sparse Stochastic Block Model

Authors: Anna Brandenberger, Byron Chin, Nathan S. Sheffield, and Divya Shyamal

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract

In sparse Erdős-Rényi graphs, it is known that a linear-time algorithm of Karp and Sipser achieves near-optimal matching sizes asymptotically almost surely, giving a law-of-large numbers for the matching numbers of such graphs in terms of solutions to an ODE [Jonathan Aronson et al., 1998]. We provide an extension of this analysis, identifying broad ranges of stochastic block model parameters for which the Karp-Sipser algorithm achieves near-optimal matching sizes, but demonstrating that it cannot perform optimally on general stochastic block model instances. We also consider the problem of constructing a matching online, in which the vertices of one half of a bipartite stochastic block model arrive one-at-a-time, and must be matched as they arrive. We show that, when the expected degrees in all communities are equal, the competitive ratio lower bound of 0.837 found by Mastin and Jaillet for the Erdős-Rényi case [Andrew Mastin and Patrick Jaillet, 2013] is achieved by a simple greedy algorithm, and this competitive ratio is optimal. We then propose and analyze a linear-time online matching algorithm with better performance in general stochastic block models.

Cite as

Anna Brandenberger, Byron Chin, Nathan S. Sheffield, and Divya Shyamal. Matching Algorithms in the Sparse Stochastic Block Model. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{brandenberger_et_al:LIPIcs.AofA.2024.16,
  author =	{Brandenberger, Anna and Chin, Byron and Sheffield, Nathan S. and Shyamal, Divya},
  title =	{{Matching Algorithms in the Sparse Stochastic Block Model}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.16},
  URN =		{urn:nbn:de:0030-drops-204515},
  doi =		{10.4230/LIPIcs.AofA.2024.16},
  annote =	{Keywords: Matching Algorithms, Online Matching, Stochastic Block Model}
}

Document

DOI: 10.4230/LIPIcs.ESA.2023.87

Engineering Fast Algorithms for the Bottleneck Matching Problem

Authors: Ioannis Panagiotas, Grégoire Pichon, Somesh Singh, and Bora Uçar

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

We investigate the maximum bottleneck matching problem in bipartite graphs. Given a bipartite graph with nonnegative edge weights, the problem is to find a maximum cardinality matching in which the minimum weight of an edge is the maximum. To the best of our knowledge, there are two widely used solvers for this problem based on two different approaches. There exists a third known approach in the literature, which seems inferior to those two which is presumably why there is no implementation of it. We take this third approach, make theoretical observations to improve its behavior, and implement the improved method. Experiments with the existing two solvers show that their run time can be too high to be useful in many interesting cases. Furthermore, their performance is not predictable, and slight perturbations of the input graph lead to considerable changes in the run time. On the other hand, the proposed solver’s performance is much more stable; it is almost always faster than or comparable to the two existing solvers, and its run time always remains low.

Cite as

Ioannis Panagiotas, Grégoire Pichon, Somesh Singh, and Bora Uçar. Engineering Fast Algorithms for the Bottleneck Matching Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 87:1-87:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{panagiotas_et_al:LIPIcs.ESA.2023.87,
  author =	{Panagiotas, Ioannis and Pichon, Gr\'{e}goire and Singh, Somesh and U\c{c}ar, Bora},
  title =	{{Engineering Fast Algorithms for the Bottleneck Matching Problem}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{87:1--87:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.87},
  URN =		{urn:nbn:de:0030-drops-187406},
  doi =		{10.4230/LIPIcs.ESA.2023.87},
  annote =	{Keywords: bipartite graphs, assignment problem, matching}
}

Document

DOI: 10.4230/LIPIcs.ESA.2020.76

Engineering Fast Almost Optimal Algorithms for Bipartite Graph Matching

Authors: Ioannis Panagiotas and Bora Uçar

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract

We consider the maximum cardinality matching problem in bipartite graphs. There are a number of exact, deterministic algorithms for this purpose, whose complexities are high in practice. There are randomized approaches for special classes of bipartite graphs. Random 2-out bipartite graphs, where each vertex chooses two neighbors at random from the other side, form one class for which there is an O(m+nlog n)-time Monte Carlo algorithm. Regular bipartite graphs, where all vertices have the same degree, form another class for which there is an expected O(m + nlog n)-time Las Vegas algorithm. We investigate these two algorithms and turn them into practical heuristics with randomization. Experimental results show that the heuristics are fast and obtain near optimal matchings. They are also more robust than the state of the art heuristics used in the cardinality matching algorithms, and are generally more useful as initialization routines.

Cite as

Ioannis Panagiotas and Bora Uçar. Engineering Fast Almost Optimal Algorithms for Bipartite Graph Matching. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 76:1-76:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{panagiotas_et_al:LIPIcs.ESA.2020.76,
  author =	{Panagiotas, Ioannis and U\c{c}ar, Bora},
  title =	{{Engineering Fast Almost Optimal Algorithms for Bipartite Graph Matching}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{76:1--76:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.76},
  URN =		{urn:nbn:de:0030-drops-129424},
  doi =		{10.4230/LIPIcs.ESA.2020.76},
  annote =	{Keywords: bipartite graphs, matching, randomized algorithm}
}

Refine by Author
2 Panagiotas, Ioannis
2 Uçar, Bora
1 Brandenberger, Anna
1 Chin, Byron
1 Pichon, Grégoire
Show More...

Refine by Classification
1 Theory of computation
1 Theory of computation → Design and analysis of algorithms
1 Theory of computation → Graph algorithms analysis

Refine by Keyword
2 bipartite graphs
2 matching
1 Matching Algorithms
1 Online Matching
1 Stochastic Block Model
Show More...

Refine by Type
3 document

Refine by Publication Year
1 2020
1 2023
1 2024