pith. machine review for the scientific record. sign in

arxiv: 2605.03071 · v1 · submitted 2026-05-04 · 💻 cs.DS

Recognition: unknown

A Poisson Process for Submodular Maximization

Amit Ganz Rozenman, Ariel Kulik, Mohit Singh, Roy Schwartz

Pith reviewed 2026-05-08 17:23 UTC · model grok-4.3

classification 💻 cs.DS
keywords submodular maximizationmatroid constraintPoisson processapproximation algorithmmonotone submodular functionwelfare maximizationassignment problem
0
0 comments X

The pith

A Poisson process achieves the tight (1-1/e) approximation for monotone submodular maximization under matroid constraints.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a stochastic method based on a Poisson process to maximize a monotone submodular function subject to a matroid constraint. This technique reaches the optimal approximation ratio of 1 minus 1 over e while avoiding any discretization or rounding steps and requiring only a small number of single-element swaps. It differs from prior continuous greedy and local search methods by using a direct stochastic analysis of marginal contributions. Readers would care because the approach simplifies the algorithm and extends to faster solutions for submodular welfare maximization and assignment problems.

Core claim

By modeling element selection through a Poisson process over the ground set, the expected marginal contribution of each element can be bounded via integral analysis, which yields an overall (1 - 1/e) approximation guarantee for the submodular maximization problem under matroid independence constraints, matching the known optimum while sidestepping the technical machinery of earlier techniques.

What carries the argument

A continuous-time Poisson process that assigns random arrival times to ground-set elements, allowing direct bounding of expected marginal gains through time-based integrals without discretization.

Load-bearing premise

The Poisson process analysis correctly bounds the expected marginal contribution of elements without any hidden discretization or rounding steps.

What would settle it

A concrete matroid and monotone submodular function on which the Poisson-process algorithm returns a solution whose value is strictly less than (1 - 1/e) times the optimum.

read the original abstract

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{\'a}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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a new algorithm for maximizing a monotone submodular function subject to a matroid independence constraint, based on a stochastic Poisson process. It claims to achieve the tight (1-1/e) approximation guarantee while avoiding discretization and rounding steps required by prior continuous-greedy and non-oblivious local-search methods, performing only a small number of single-element swaps. The approach is further applied to obtain fast algorithms for submodular welfare maximization and the general/separable assignment problems.

Significance. If the Poisson-process analysis directly establishes the (1-1/e) bound on expected marginal contributions using only elementary properties of the process (independent increments and exponential waiting times) without hidden continuous relaxations, this would constitute a meaningful simplification of the analytic toolkit for submodular maximization. It could yield more intuitive discrete algorithms that still match the optimal guarantee, with potential benefits for implementation and extensions to the listed applications.

major comments (2)
  1. [Main theorem and Poisson-process analysis] Main theorem and Poisson-process analysis section: the central claim that the stochastic process yields an expected marginal contribution of at least (1-1/e)OPT under the matroid constraint must be shown to rely solely on independent increments and exponential waiting times, without invoking the multilinear extension, solving an ODE for the expectation, or approximating the process by a discrete-time chain. If any such step appears, the claimed distinction from Calinescu et al. (STOC 2008) and Filmus-Ward (FOCS 2012) is undermined.
  2. [Algorithm description and swap analysis] Algorithm description and swap analysis: the statement that the method performs 'very few' single-element swaps while remaining fully discrete must be accompanied by an explicit bound on the number of swaps (or expected number) that is independent of any continuous-time discretization; otherwise the practical advantage over rounding-based methods is not established.
minor comments (2)
  1. [Abstract and Introduction] The abstract and introduction should include a brief pointer to the specific section containing the Poisson-process proof so that readers can immediately locate the claimed departure from prior continuous-greedy techniques.
  2. [Preliminaries] Notation for the Poisson process intensity and the matroid rank function should be introduced consistently before the main theorem to avoid forward references.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We appreciate the recognition of the potential for a simpler analytic toolkit via the Poisson process. We address each major comment below.

read point-by-point responses

  1. Referee: [Main theorem and Poisson-process analysis] Main theorem and Poisson-process analysis section: the central claim that the stochastic process yields an expected marginal contribution of at least (1-1/e)OPT under the matroid constraint must be shown to rely solely on independent increments and exponential waiting times, without invoking the multilinear extension, solving an ODE for the expectation, or approximating the process by a discrete-time chain. If any such step appears, the claimed distinction from Calinescu et al. (STOC 2008) and Filmus-Ward (FOCS 2012) is undermined.

    Authors: Our analysis derives the (1-1/e) factor directly from the independent increments and exponential waiting times of the Poisson process. For each element, the probability it has not arrived by time t is e^{-t} by the exponential distribution; the expected marginal contribution is then obtained by integrating (1 - e^{-t}) over t in [0,1] and applying linearity of expectation over the ground set. The matroid constraint is enforced by maintaining an independent set and performing swaps only when an arriving element improves the current solution while preserving independence. No multilinear extension is used, no ODE is solved, and the implementation remains fully discrete (generating exponential times per element and executing swaps). We will add an explicit paragraph in the main theorem section stating these properties to remove any ambiguity. revision: partial

  2. Referee: [Algorithm description and swap analysis] Algorithm description and swap analysis: the statement that the method performs 'very few' single-element swaps while remaining fully discrete must be accompanied by an explicit bound on the number of swaps (or expected number) that is independent of any continuous-time discretization; otherwise the practical advantage over rounding-based methods is not established.

    Authors: We agree an explicit bound clarifies the practical advantage. The algorithm simulates the Poisson process by independently sampling an exponential random variable for each of the n elements. Each element triggers at most one swap (upon its arrival, if it can be exchanged into the current matroid basis). Thus the total number of swaps is at most n, a bound that depends only on the ground-set size and holds without any discretization parameter. The expected number is strictly smaller. We will insert this O(n) worst-case bound into the algorithm description. revision: yes

Circularity Check

0 steps flagged

Poisson process yields independent (1-1/e) bound without reduction to prior analytic machinery

full rationale

The paper introduces a stochastic Poisson process model for monotone submodular maximization under matroid constraints. Its abstract states that the approach matches the tight (1-1/e) guarantee while avoiding discretization or rounding and using only few single-element swaps, explicitly distinguishing it from continuous greedy (Calinescu et al.) and local search (Filmus-Ward, Buchbinder-Feldman). No equations, fitted parameters, or self-citation chains are exhibited that would reduce the central bound to inputs by construction; the derivation relies on elementary process properties (independent increments, exponential waiting times) for expected marginal contributions. This renders the result self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only; no explicit free parameters, axioms, or invented entities are stated. The Poisson process itself may function as an invented modeling device whose independent justification is not visible.

pith-pipeline@v0.9.0 · 5486 in / 1039 out tokens · 28414 ms · 2026-05-08T17:23:28.674628+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

74 extracted references · 15 canonical work pages

  1. [1]

    , author=

    Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. , author=. Journal of machine learning research , volume=

  2. [2]

    Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Submodular maximization with cardinality constraints , author=. Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2014 , organization=

    2014

  3. [3]

    Mathematics of Operations Research , volume=

    Comparing apples and oranges: Query trade-off in submodular maximization , author=. Mathematics of Operations Research , volume=. 2017 , publisher=

    2017

  4. [4]

    Information Processing Letters , volume=

    An efficient approximation for the generalized assignment problem , author=. Information Processing Letters , volume=. 2006 , publisher=

    2006

  5. [5]

    Proceedings of the AAAI Conference on Artificial Intelligence , year=

    Lazier than lazy greedy , author=. Proceedings of the AAAI Conference on Artificial Intelligence , year=

  6. [6]

    51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , pages=

    Subquadratic Submodular Maximization with a General Matroid Constraint , author=. 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , pages=. 2024 , organization=

    2024

  7. [7]

    International Colloquium on Automata, Languages, and Programming , volume=

    Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint , author=. International Colloquium on Automata, Languages, and Programming , volume=

  8. [8]

    Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

    A nearly quadratic-time FPTAS for knapsack , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

  9. [9]

    SODA , volume=

    Tight approximation algorithms for maximum general assignment problems , author=. SODA , volume=

  10. [10]

    2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) , pages=

    Approximation algorithms for allocation problems: Improving the factor of 1-1/e , author=. 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) , pages=. 2006 , organization=

    2006

  11. [11]

    2025 , booktitle =

    Buchbinder, Niv and Feldman, Moran , title =. 2025 , booktitle =

    2025

  12. [12]

    2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Deterministic algorithm and faster algorithm for submodular maximization subject to a matroid constraint , author=. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2024 , organization=

    2024

  13. [13]

    Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Fast algorithms for maximizing submodular functions , author=. Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2014 , organization=

    2014

  14. [14]

    2014 , edition=

    Introduction to Probability Models , author=. 2014 , edition=

    2014

  15. [15]

    SIAM Journal on Computing , volume=

    Monotone submodular maximization over a matroid via non-oblivious local search , author=. SIAM Journal on Computing , volume=. 2014 , publisher=

    2014

  16. [16]

    SIAM Journal on Computing , volume=

    Maximizing non-monotone submodular functions , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  17. [17]

    Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms , pages=

    Submodular maximization by simulated annealing , author=. Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms , pages=. 2011 , organization=

    2011

  18. [18]

    Mathematics of Operations Research , volume=

    Submodular maximization over multiple matroids via generalized exchange properties , author=. Mathematics of Operations Research , volume=. 2010 , publisher=

    2010

  19. [19]

    Mathematics of Operations Research , volume =

    Jon Lee and Maxim Sviridenko and Jan Vondrák , title =. Mathematics of Operations Research , volume =. 2009 , publisher =

    2009

  20. [20]

    SIAM Journal on Computing , volume=

    Maximizing a monotone submodular function subject to a matroid constraint , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  21. [21]

    46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , pages=

    A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint , author=. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , pages=

    2019

  22. [22]

    Mathematics of Operations Research , volume=

    Approximations for monotone and nonmonotone submodular maximization with knapsack constraints , author=. Mathematics of Operations Research , volume=. 2013 , publisher=

    2013

  23. [23]

    Proceedings of the forty-third annual ACM symposium on Theory of computing , pages=

    Submodular function maximization via the multilinear relaxation and contention resolution schemes , author=. Proceedings of the forty-third annual ACM symposium on Theory of computing , pages=

  24. [24]

    International Conference on Machine Learning , pages=

    Fast constrained submodular maximization: Personalized data summarization , author=. International Conference on Machine Learning , pages=. 2016 , organization=

    2016

  25. [25]

    Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining , pages=

    Maximizing the spread of influence through a social network , author=. Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining , pages=

  26. [26]

    Mathematical programming , volume=

    An analysis of approximations for maximizing submodular set functions—I , author=. Mathematical programming , volume=. 1978 , publisher=

    1978

  27. [27]

    Fisher, M. L. and Nemhauser, G. L. and Wolsey, L. A. An analysis of approximations for maximizing submodular set functions--- II. Math. Prog. Study. 1978

    1978

  28. [28]

    Mathematics of operations research , volume=

    Best algorithms for approximating the maximum of a submodular set function , author=. Mathematics of operations research , volume=. 1978 , publisher=

    1978

  29. [29]

    and Sviridenko, M.I

    Ageev, A.A. and Sviridenko, M.I. Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee. Journal of Combinatorial Optimization. 2004

    2004

  30. [30]

    Gandhi, Rajiv and Khuller, Samir and Parthasarathy, Srinivasan and Srinivasan, Aravind , title =. J. ACM , issue_date =. 2006 , pages =

    2006

  31. [31]

    Srinivasan , booktitle=

    A. Srinivasan , booktitle=. Distributions on level-sets with applications to approximation algorithms , year=

  32. [32]

    SIAM Journal on Computing , volume=

    A tight linear time (1/2)-approximation for unconstrained submodular maximization , author=. SIAM Journal on Computing , volume=. 2015 , publisher=

    2015

  33. [33]

    Symmetry and Approximability of Submodular Maximization Problems , journal =

    Vondr\'. Symmetry and Approximability of Submodular Maximization Problems , year =. doi:10.1137/110832318 , journal =

    work page doi:10.1137/110832318

  34. [34]

    Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm , pages =

    Dobzinski, Shahar and Schapira, Michael , title =. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm , pages =. 2006 , isbn =

    2006

  35. [35]

    2011 , isbn =

    Feldman, Moran and Naor, Joseph (Seffi) and Schwartz, Roy , title =. 2011 , isbn =. doi:10.1109/FOCS.2011.46 , booktitle =

    work page doi:10.1109/focs.2011.46 2011

  36. [36]

    Chakrabarty, Deeparnab and Goel, Gagan , title =. SIAM J. Comput. , month = mar, pages =. 2010 , issue_date =

    2010

  37. [37]

    2006 , isbn =

    Feige, Uriel , title =. 2006 , isbn =. doi:10.1145/1132516.1132523 , booktitle =

    work page doi:10.1145/1132516.1132523 2006

  38. [38]

    Theory of Computing , volume =

    Feige, Uriel and Vondr\'ak, Jan , title =. Theory of Computing , volume =. 2010 , pages =. doi:10.4086/toc.2010.v006a011 , publisher =

    work page doi:10.4086/toc.2010.v006a011 2010

  39. [39]

    and Markakis, Evangelos and Mehta, Aranyak , title =

    Khot, Subhash and Lipton, Richard J. and Markakis, Evangelos and Mehta, Aranyak , title =. Algorithmica , month = sep, pages =. 2008 , issue_date =

    2008

  40. [40]

    2001 , isbn =

    Lehmann, Benny and Lehmann, Daniel and Nisan, Noam , title =. 2001 , isbn =. doi:10.1145/501158.501161 , booktitle =

    work page doi:10.1145/501158.501161 2001

  41. [41]

    and Vondr\'

    Feige, Uriel and Mirrokni, Vahab S. and Vondr\'. Maximizing Non-monotone Submodular Functions , year =. doi:10.1137/090779346 , journal =

    work page doi:10.1137/090779346

  42. [42]

    2015 , issue_date =

    Buchbinder, Niv and Feldman, Moran and Naor, Joseph (Seffi) and Schwartz, Roy , title =. 2015 , issue_date =. doi:10.1137/130929205 , journal =

    work page doi:10.1137/130929205 2015

  43. [43]

    2013 , isbn =

    Bach, Francis , title =. 2013 , isbn =

    2013

  44. [44]

    2008 , isbn =

    Hartline, Jason and Mirrokni, Vahab and Sundararajan, Mukund , title =. 2008 , isbn =. doi:10.1145/1367497.1367524 , booktitle =

    work page doi:10.1145/1367497.1367524 2008

  45. [45]

    Krause, Andreas and Singh, Ajit and Guestrin, Carlos , title =. J. Mach. Learn. Res. , month = jun, pages =. 2008 , issue_date =

    2008

  46. [46]

    Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics , pages =

    Lin, Hui and Bilmes, Jeff , title =. Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics , pages =. 2010 , isbn =

    2010

  47. [47]

    A Class of Submodular Functions for Document Summarization

    Lin, Hui and Bilmes, Jeff. A Class of Submodular Functions for Document Summarization. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies. 2011

    2011

  48. [48]

    Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes , journal =

    Chekuri, Chandra and Vondr\'. Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes , journal =. 2014 , doi =

    2014

  49. [49]

    1969 , publisher=

    Differential and integral inequalities: theory and applications: volume I: ordinary differential equations , author=. 1969 , publisher=

    1969

  50. [50]

    arXiv preprint arXiv:2305.00122 , year=

    Faster submodular maximization for several classes of matroids , author=. arXiv preprint arXiv:2305.00122 , year=

    work page arXiv

  51. [51]

    29th Annual European Symposium on Algorithms, ESA 2021 , pages=

    Modular and submodular optimization with multiple knapsack constraints via fractional grouping , author=. 29th Annual European Symposium on Algorithms, ESA 2021 , pages=

    2021

  52. [52]

    Bulletin of the Australian Mathematical Society , volume=

    Comments on bases in dependence structures , author=. Bulletin of the Australian Mathematical Society , volume=. 1969 , publisher=

    1969

  53. [53]

    , booktitle=

    Ene, Alina and Nguyen, Huy L. , booktitle=. Constrained Submodular Maximization: Beyond 1/e , year=

  54. [54]

    2019 , issue_date =

    Buchbinder, Niv and Feldman, Moran , title =. 2019 , issue_date =. doi:10.1287/moor.2018.0955 , journal =

    work page doi:10.1287/moor.2018.0955 2019

  55. [55]

    Constrained submodular maximization via new bounds for DR-submodular functions , year=

    Buchbinder, Niv and Feldman, Moran , booktitle=. Constrained submodular maximization via new bounds for DR-submodular functions , year=

  56. [56]

    Submodular maximization by simulated annealing , year =

    Gharan, Shayan Oveis and Vondr\'. Submodular maximization by simulated annealing , year =. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

  57. [57]

    On maximizing sums of non-monotone submodular and linear functions.Algorithmica, 86:1080–1134, 2024

    Qi, Benjamin , title =. 2023 , issue_date =. doi:10.1007/s00453-023-01183-3 , journal =

    work page doi:10.1007/s00453-023-01183-3 2023

  58. [58]

    Journal of Water Resources Planning and Management , volume =

    Andreas Krause and Jure Leskovec and Carlos Guestrin and Jeanne VanBriesen and Christos Faloutsos , title =. Journal of Water Resources Planning and Management , volume =. 2008 , doi =

    2008

  59. [59]

    2022 , isbn =

    Bao, Wei-Xuan and Hang, Jun-Yi and Zhang, Min-Ling , title =. 2022 , isbn =. doi:10.1145/3534678.3539292 , booktitle =

    work page doi:10.1145/3534678.3539292 2022

  60. [60]

    Submodular feature selection for high-dimensional acoustic score spaces , booktitle =

    Liu, Yuzong and Wei, Kai and Kirchhoff, Katrin and Song, Yisong and Bilmes, Jeff , year =. Submodular feature selection for high-dimensional acoustic score spaces , booktitle =

  61. [61]

    2017 , editor =

    Khanna, Rajiv and Elenberg, Ethan and Dimakis, Alex and Negahban, Sahand and Ghosh, Joydeep , booktitle =. 2017 , editor =

    2017

  62. [62]

    Proceedings of the 31st International Conference on Neural Information Processing Systems , pages =

    Karimi, Mohammad Reza and Lucic, Mario and Hassani, Hamed and Krause, Andreas , title =. Proceedings of the 31st International Conference on Neural Information Processing Systems , pages =. 2017 , isbn =

    2017

  63. [63]

    Stochastic Greedy Algorithm Is Still Good: Maximizing Submodular + Supermodular Functions

    Ji, Sai and Xu, Dachuan and Li, Min and Wang, Yishui and Zhang, Dongmei. Stochastic Greedy Algorithm Is Still Good: Maximizing Submodular + Supermodular Functions. Optimization of Complex Systems: Theory, Models, Algorithms and Applications. 2020

    2020

  64. [64]

    Transactions on Machine Learning Research , issn=

    Revisiting stochastic submodular maximization with cardinality constraint: A bandit perspective , author=. Transactions on Machine Learning Research , issn=. 2024 , url=

    2024

  65. [65]

    , title =

    Malioutov, Dmitry and Kumar, Abhishek and Yen, Ian E.H. , title =. Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence , pages =. 2016 , isbn =

    2016

  66. [66]

    SIAM Journal on Computing , volume =

    Mossel, Elchanan and Roch, Sebastien , title =. SIAM Journal on Computing , volume =. 2010 , doi =

    2010

  67. [67]

    2014 , isbn =

    Rozenshtein, Polina and Anagnostopoulos, Aris and Gionis, Aristides and Tatti, Nikolaj , title =. 2014 , isbn =. doi:10.1145/2623330.2623674 , booktitle =

    work page doi:10.1145/2623330.2623674 2014

  68. [68]

    Learning the Structure of Deep Convolutional Networks , year=

    Feng, Jiashi and Darrell, Trevor , booktitle=. Learning the Structure of Deep Convolutional Networks , year=

  69. [69]

    2014 , isbn =

    Shakarian, Paulo and Salmento, Joseph and Pulleyblank, William and Bertetto, John , title =. 2014 , isbn =. doi:10.1145/2623330.2623331 , booktitle =

    work page doi:10.1145/2623330.2623331 2014

  70. [70]

    Adaptive Keyframe Selection for Video Summarization , year=

    Chakraborty, Shayok and Tickoo, Omesh and Iyer, Ravi , booktitle=. Adaptive Keyframe Selection for Video Summarization , year=

  71. [71]

    Submodular Maximization over Multiple Matroids via Generalized Exchange Properties , year =

    Lee, Jon and Sviridenko, Maxim and Vondr\'. Submodular Maximization over Multiple Matroids via Generalized Exchange Properties , year =. doi:10.1287/moor.1100.0463 , journal =

    work page doi:10.1287/moor.1100.0463

  72. [72]

    and Nagarajan, Viswanath and Sviridenko, Maxim , title =

    Lee, Jon and Mirrokni, Vahab S. and Nagarajan, Viswanath and Sviridenko, Maxim , title =. SIAM Journal on Discrete Mathematics , volume =. 2010 , doi =

    2010

  73. [73]

    Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

    Optimal approximation for the submodular welfare problem in the value oracle model , author=. Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

  74. [74]

    Feige, Uriel , title =. J. ACM , month =. 1998 , issue_date =

    1998