Faster matroid intersection

DOI10.1109/FOCS.2019.00072MaRDI QIDQ6944165zbMATH OpenFDO

Authors Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2019.00072

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Nonnumerical algorithms (68W05) Combinatorial aspects of matroids and geometric lattices (05B35)

Cited in

(7)

• Fast combinatorial algorithms for efficient sortation
• Breaking O(nr) for matroid intersection
• Adaptive sparsification for matroid intersection
• Subquadratic submodular maximization with a general matroid constraint
• Matroid and knapsack house allocation
• Learning partitions using rank queries
• Faster matroid partition algorithms

This page was built for publication: Faster matroid intersection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6944165)