2026-07-25T06:42:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20261 2024-07-02T07:52:54Z ddc:004 open_access

Adaptive Sparsification for Matroid Intersection Quanrud, Kent Matroid intersection adaptive sparsification multiplicative-weight udpates primal-dual We consider the matroid intersection problem in the independence oracle model. Given two matroids over n common elements such that the intersection has rank k, our main technique reduces approximate matroid intersection to logarithmically many primal-dual instances over subsets of size Õ(k). This technique is inspired by recent work by [Assadi, 2024] and requires additional insight into structuring and efficiently approximating the dual LP. This combination of ideas leads to faster approximate maximum cardinality and maximum weight matroid intersection algorithms in the independence oracle model. We obtain the first nearly linear time/query approximation schemes for the regime where k ≤ n^{2/3}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kent Quanrud 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.118 urn:nbn:de:0030-drops-202614 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.118 eng https://creativecommons.org/licenses/by/4.0/legalcode