License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.25
URN: urn:nbn:de:0030-drops-163662
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16366/
Go to the corresponding LIPIcs Volume Portal

Blikstad, Joakim

Sublinear-Round Parallel Matroid Intersection

pdf-format:
LIPIcs-ICALP-2022-25.pdf (0.8 MB)

Abstract

Despite a lot of recent progress in obtaining faster sequential matroid intersection algorithms, the fastest parallel poly(n)-query algorithm was still the straightforward O(n)-round parallel implementation of Edmonds' augmenting paths algorithm from the 1960s.
Very recently, Chakrabarty-Chen-Khanna [FOCS'21] showed the lower bound that any, possibly randomized, parallel matroid intersection algorithm making poly(n) rank-queries requires Ω̃(n^{1/3}) rounds of adaptivity. They ask, as an open question, if the lower bound can be improved to Ω̃(n), or if there can be sublinear-round, poly(n)-query algorithms for matroid intersection.
We resolve this open problem by presenting the first sublinear-round parallel matroid intersection algorithms. Perhaps surprisingly, we do not only break the Õ(n)-barrier in the rank-oracle model, but also in the weaker independence-oracle model. Our rank-query algorithm guarantees O(n^{3/4}) rounds of adaptivity, while the independence-query algorithm uses O(n^{7/8}) rounds of adaptivity, both making a total of poly(n) queries.

BibTeX - Entry

@InProceedings{blikstad:LIPIcs.ICALP.2022.25,
  author =	{Blikstad, Joakim},
  title =	{{Sublinear-Round Parallel Matroid Intersection}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16366},
  URN =		{urn:nbn:de:0030-drops-163662},
  doi =		{10.4230/LIPIcs.ICALP.2022.25},
  annote =	{Keywords: Matroid Intersection, Combinatorial Optimization, Parallel Algorithms}
}

Keywords: Matroid Intersection, Combinatorial Optimization, Parallel Algorithms
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI