Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.03071 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918482343362560 |
|---|---|
| author | Rozenman, Amit Ganz Kulik, Ariel Schwartz, Roy Singh, Mohit |
| author_facet | Rozenman, Amit Ganz Kulik, Ariel Schwartz, Roy Singh, Mohit |
| contents | We study the problem of maximizing a monotone submodular function subject to a matroid independence constraint. For more than a decade, a rich body of work has studied this problem. Initially, a tight approximation of $ (1-\frac{1}{e})$ was given using the continuous greedy algorithm [Calinescu-Chekuri-Pal-Vondr{á}k STOC`2008] and later non-oblivious local search techniques were able to match this tight approximation guarantee [Filmus-Ward FOCS`2012] and [Buchbinder-Feldman FOCS`2024].
We propose a new and remarkably simple approach to this problem that is based on a stochastic Poisson process. Our approach matches the tight $ (1-\frac{1}{e})$ approximation guarantee and it differs from the known two techniques since it does not require discretization or rounding while performing very few single element swaps. We also present applications of our approach and obtain fast algorithms for submodular welfare maximization, and for the general and separable assignment problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_03071 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Poisson Process for Submodular Maximization Rozenman, Amit Ganz Kulik, Ariel Schwartz, Roy Singh, Mohit Data Structures and Algorithms We study the problem of maximizing a monotone submodular function subject to a matroid independence constraint. For more than a decade, a rich body of work has studied this problem. Initially, a tight approximation of $ (1-\frac{1}{e})$ was given using the continuous greedy algorithm [Calinescu-Chekuri-Pal-Vondr{á}k STOC`2008] and later non-oblivious local search techniques were able to match this tight approximation guarantee [Filmus-Ward FOCS`2012] and [Buchbinder-Feldman FOCS`2024]. We propose a new and remarkably simple approach to this problem that is based on a stochastic Poisson process. Our approach matches the tight $ (1-\frac{1}{e})$ approximation guarantee and it differs from the known two techniques since it does not require discretization or rounding while performing very few single element swaps. We also present applications of our approach and obtain fast algorithms for submodular welfare maximization, and for the general and separable assignment problems. |
| title | A Poisson Process for Submodular Maximization |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.03071 |