Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.15702 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917278272978944 |
|---|---|
| author | Dudeja, Aditi Grilnberger, Mara |
| author_facet | Dudeja, Aditi Grilnberger, Mara |
| contents | Given two matroids $\mathcal{M}_1$ and $\mathcal{M}_2$ over the same ground set, the matroid intersection problem is to find the maximum cardinality common independent set. In the weighted version of the problem, the goal is to find a maximum weight common independent set. It has been a matter of interest to find efficient approximation algorithms for this problem in various settings. In many of these models, there is a gap between the best known results for the unweighted and weighted versions. In this work, we address the question of closing this gap. Our main result is a reduction which converts any $α$-approximate unweighted matroid intersection algorithm into an $α(1-\varepsilon)$-approximate weighted matroid intersection algorithm, while increasing the runtime of the algorithm by a $\log W$ factor, where $W$ is the aspect ratio. Our framework is versatile and translates to settings such as streaming and one-way communication complexity where matroid intersection is well-studied. As a by-product of our techniques, we derive new results for weighted matroid intersection in these models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15702 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Weighted-to-Unweighted Reduction for Matroid Intersection Dudeja, Aditi Grilnberger, Mara Data Structures and Algorithms Given two matroids $\mathcal{M}_1$ and $\mathcal{M}_2$ over the same ground set, the matroid intersection problem is to find the maximum cardinality common independent set. In the weighted version of the problem, the goal is to find a maximum weight common independent set. It has been a matter of interest to find efficient approximation algorithms for this problem in various settings. In many of these models, there is a gap between the best known results for the unweighted and weighted versions. In this work, we address the question of closing this gap. Our main result is a reduction which converts any $α$-approximate unweighted matroid intersection algorithm into an $α(1-\varepsilon)$-approximate weighted matroid intersection algorithm, while increasing the runtime of the algorithm by a $\log W$ factor, where $W$ is the aspect ratio. Our framework is versatile and translates to settings such as streaming and one-way communication complexity where matroid intersection is well-studied. As a by-product of our techniques, we derive new results for weighted matroid intersection in these models. |
| title | A Weighted-to-Unweighted Reduction for Matroid Intersection |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.15702 |