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

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

Cited in

(8)

• Adaptive sparsification for matroid intersection
• Subquadratic submodular maximization with a general matroid constraint
• Faster matroid partition algorithms
• Fast combinatorial algorithms for efficient sortation
• Breaking O(nr) for matroid intersection
• Matroid and knapsack house allocation
• Learning partitions using rank queries
• Deterministic (2/3-)-approximation of matroid intersection using nearly-linear independence-oracle queries

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)