Better Approximation for Weighted $k$-Matroid Intersection
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913601951891456 |
|---|---|
| author | Singer, Neta Thiery, Theophile |
| author_facet | Singer, Neta Thiery, Theophile |
| contents | We consider the problem of finding an independent set of maximum weight simultaneously contained in $k$ matroids over a common ground set. This $k$-matroid intersection problem appears naturally in many contexts, for example in generalizing graph and hypergraph matching problems. In this paper, we provide a $(k+1)/(2 \ln 2)$-approximation algorithm for the weighted $k$-matroid intersection problem. This is the first improvement over the longstanding $(k-1)$-guarantee of Lee, Sviridenko and Vondrák (2009). Along the way, we also give the first improvement over greedy for the more general weighted matroid $k$-parity problem.
Our key innovation lies in a randomized reduction in which we solve almost unweighted instances iteratively. This perspective allows us to use insights from the unweighted problem for which Lee, Sviridenko, and Vondrák have designed a $k/2$-approximation algorithm. We analyze this procedure by constructing refined matroid exchanges and leveraging randomness to avoid bad local minima. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19366 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Better Approximation for Weighted $k$-Matroid Intersection Singer, Neta Thiery, Theophile Data Structures and Algorithms Discrete Mathematics F.2.2; G.1.6 We consider the problem of finding an independent set of maximum weight simultaneously contained in $k$ matroids over a common ground set. This $k$-matroid intersection problem appears naturally in many contexts, for example in generalizing graph and hypergraph matching problems. In this paper, we provide a $(k+1)/(2 \ln 2)$-approximation algorithm for the weighted $k$-matroid intersection problem. This is the first improvement over the longstanding $(k-1)$-guarantee of Lee, Sviridenko and Vondrák (2009). Along the way, we also give the first improvement over greedy for the more general weighted matroid $k$-parity problem. Our key innovation lies in a randomized reduction in which we solve almost unweighted instances iteratively. This perspective allows us to use insights from the unweighted problem for which Lee, Sviridenko, and Vondrák have designed a $k/2$-approximation algorithm. We analyze this procedure by constructing refined matroid exchanges and leveraging randomness to avoid bad local minima. |
| title | Better Approximation for Weighted $k$-Matroid Intersection |
| topic | Data Structures and Algorithms Discrete Mathematics F.2.2; G.1.6 |
| url | https://arxiv.org/abs/2411.19366 |