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.2021.31
URN: urn:nbn:de:0030-drops-141004
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14100/
Go to the corresponding LIPIcs Volume Portal

Blikstad, Joakim

Breaking O(nr) for Matroid Intersection

pdf-format:
LIPIcs-ICALP-2021-31.pdf (0.9 MB)

Abstract

We present algorithms that break the Õ(nr)-independence-query bound for the Matroid Intersection problem for the full range of r; where n is the size of the ground set and r ≤ n is the size of the largest common independent set. The Õ(nr) bound was due to the efficient implementations [CLSSW FOCS'19; Nguyên 2019] of the classic algorithm of Cunningham [SICOMP'86]. It was recently broken for large r (r = ω(√n)), first by the Õ(n^{1.5}/ε^{1.5})-query (1-ε)-approximation algorithm of CLSSW [FOCS'19], and subsequently by the Õ(n^{6/5}r^{3/5})-query exact algorithm of BvdBMN [STOC'21]. No algorithm - even an approximation one - was known to break the Õ(nr) bound for the full range of r. We present an Õ(n√r/ε)-query (1-ε)-approximation algorithm and an Õ(nr^{3/4})-query exact algorithm. Our algorithms improve the Õ(nr) bound and also the bounds by CLSSW and BvdBMN for the full range of r.

BibTeX - Entry

@InProceedings{blikstad:LIPIcs.ICALP.2021.31,
  author =	{Blikstad, Joakim},
  title =	{{Breaking O(nr) for Matroid Intersection}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14100},
  URN =		{urn:nbn:de:0030-drops-141004},
  doi =		{10.4230/LIPIcs.ICALP.2021.31},
  annote =	{Keywords: Matroid Intersection, Combinatorial Optimization, Approximation Algorithms}
}

Keywords: Matroid Intersection, Combinatorial Optimization, Approximation Algorithms
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

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