Robust Sparsification for Matroid Intersection with Applications

• 成果类型: Article
• 署名作者: Huang, Chien-Chung; Sellier, Francois
• 署名单位: Universite PSL; Centre National de la Recherche Scientifique (CNRS); Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; MINES ParisTech
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0562
• 发表日期: 2026-08
• 关键词: discrete optimization; matroid intersection; sparsification; Streaming; one-way communication; algorithms

摘要

Matroid intersection is a classical optimization problem where given two matroids over the same ground set, the goal is to find the largest common independent set. In this paper, we show that there exists a certain sparsifer: a subset of elements of size O(|Sopt| 1/E), where Sopt denotes the optimal solution, that is guaranteed to contain a 3/2 + E approximation while guaranteeing certain robustness properties. We call such a small subset a density constrained subset, which is inspired by the edge-degree constrained subgraph, originally designed for the maximum cardinality matching problem in a graph. Our proof is constructive and hinges on a greedy decomposition of matroids, which we call the density-based decomposition. We show that this sparsifier has certain robustness properties that can be used in one-way communication and random-order streaming models.