pith. sign in

arxiv: 2602.08473 · v3 · submitted 2026-02-09 · 💻 cs.DS · cs.DM

Submodular Maximization over a Matroid k-Intersection: Multiplicative Improvement over Greedy

Moran Feldman , Justin Ward This is my paper

Pith reviewed 2026-05-16 06:08 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords submodular maximizationmatroid intersectionapproximation algorithmsgreedy algorithmlocal searchnon-monotone submodular
0
0 comments X

The pith

A hybrid greedy-local search algorithm improves the approximation ratio for monotone submodular maximization under k matroid constraints to roughly 0.819k.

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

The paper studies the maximization of a non-negative monotone submodular function subject to the intersection of k arbitrary matroids. Earlier algorithms achieved at best a k-approximation, matching or approaching the guarantee of the basic greedy method. The authors present a hybrid procedure that interleaves greedy additions with local search improvements to obtain a strictly smaller leading coefficient of 2 ln 2 over 1 plus ln 2. The same framework yields comparable ratios when the objective is permitted to be non-monotone and when the constraint is relaxed to a matroid k-parity condition. All variants run in time polynomial in the ground-set size and independent of k.

Core claim

The central claim is that a hybrid procedure combining greedy selection steps with local search swaps produces a solution whose value is at least 2k ln 2 / (1 + ln 2) plus an O(sqrt(k)) term times the optimum for any monotone submodular objective under k matroid constraints. The same bound holds, up to a change in the additive term to O(k to the 2/3), when monotonicity is dropped. In the special case of linear objectives the procedure simplifies to a variant that guarantees (k + 1) ln 2.

What carries the argument

A hybrid greedy-local search procedure that performs greedy additions while occasionally performing local swaps, with the analysis tracking how submodular marginal gains evolve under the internal randomness of the swaps.

Load-bearing premise

The marginal gains of the submodular function remain sufficiently well-behaved under the randomness of the hybrid procedure so that the weighted-case analysis still applies after suitable modifications.

What would settle it

An explicit instance consisting of a monotone submodular function and k matroids on which the hybrid algorithm returns a value strictly less than 0.819k times the optimum value would refute the claimed ratio.

Figures

Figures reproduced from arXiv: 2602.08473 by Justin Ward, Moran Feldman.

Figure 1
Figure 1. Figure 1: The four families of constraints discussed in Section [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original abstract

We study the problem of maximizing a non-negative monotone submodular objective $f$ subject to the intersection of $k$ arbitrary matroid constraints. The natural greedy algorithm guarantees $(k+1)$-approximation for this problem, and the state-of-the-art algorithm only improves this approximation ratio to $k$. We give a $\frac{2k\ln2}{1+\ln2}+O(\sqrt{k})<0.819k+O(\sqrt{k})$ approximation for this problem. Our result is the first multiplicative improvement over the approximation ratio of the greedy algorithm for general $k$. We further show that our algorithm can be used to obtain roughly the same approximation ratio also for the more general problem in which the objective is not guaranteed to be monotone (the sublinear term in the approximation ratio becomes $O(k^{2/3})$ rather than $O(\sqrt{k})$ in this case). All of our results hold also when the $k$-matroid intersection constraint is replaced with a more general matroid $k$-parity constraint. Furthermore, unlike the case in many of the previous works, our algorithms run in time that is independent of $k$ and polynomial in the size of the ground set. Our algorithms are based on a hybrid greedy local search approach recently introduced by Singer and Thiery (STOC 2025) for the weighted matroid $k$-intersection problem, which is a special case of the problem we consider. Leveraging their approach in the submodular setting requires several non-trivial insights and algorithmic modifications since the marginals of a submodular function $f$, which correspond to the weights in the weighted case, are not independent of the algorithm's internal randomness. In the special weighted case studied by Singer and Thiery, our algorithms reduce to a variant of their algorithm with an improved approximation ratio of $(k+1)\ln2<0.694k+0.694$, compared to an approximation ratio of $\frac{k+1}{2\ln2}\approx0.722k+0.722$ guaranteed by Singer and Thiery.

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

1 major / 2 minor

Summary. The paper studies maximizing a non-negative monotone submodular function subject to the intersection of k arbitrary matroids (or more generally matroid k-parity constraints). It presents a hybrid greedy-local-search algorithm that achieves approximation ratio 2k ln2/(1+ln2) + O(sqrt(k)) < 0.819k + O(sqrt(k)), the first multiplicative improvement over the greedy algorithm's (k+1) ratio. The same framework yields a comparable ratio for the non-monotone case (with O(k^{2/3}) additive term) and runs in time polynomial in the ground-set size and independent of k. The algorithm adapts the Singer-Thiery hybrid approach, with non-trivial modifications to handle the dependence of submodular marginal gains on the algorithm's internal randomness.

Significance. If the central analysis holds, the result supplies the first multiplicative improvement over greedy for general k in this fundamental submodular maximization setting, extending recent weighted-case advances while preserving k-independent runtime. The explicit handling of randomness-dependent marginals and the extension to non-monotone objectives and parity constraints are technically substantive and could influence subsequent hybrid-algorithm work.

major comments (1)
  1. Abstract: the claimed ratio 2k ln2/(1+ln2) + O(sqrt(k)) rests on the assertion that the hybrid greedy-local-search procedure yields the same (1+ln2) factor improvement after replacing fixed weights by random marginals. No proof sketch or error analysis is supplied, so it is impossible to verify whether the O(sqrt(k)) term uniformly absorbs any extra variance term that scales with solution size, as required by the skeptic's concern on dependence of marginal gains on internal randomness.
minor comments (2)
  1. Abstract: the reduction to the weighted case is stated to recover an improved ratio (k+1)ln2 < 0.694k+0.694, but the precise algorithmic variant used in that reduction should be spelled out.
  2. Abstract: clarify whether the O(sqrt(k)) term remains unchanged when the k-matroid intersection is replaced by a matroid k-parity constraint.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive assessment of the significance of our results and for the careful reading. We address the single major comment below.

read point-by-point responses

  1. Referee: [—] Abstract: the claimed ratio 2k ln2/(1+ln2) + O(sqrt(k)) rests on the assertion that the hybrid greedy-local-search procedure yields the same (1+ln2) factor improvement after replacing fixed weights by random marginals. No proof sketch or error analysis is supplied, so it is impossible to verify whether the O(sqrt(k)) term uniformly absorbs any extra variance term that scales with solution size, as required by the skeptic's concern on dependence of marginal gains on internal randomness.

    Authors: We agree that the abstract is too concise to convey the error analysis. The full manuscript (Sections 3–4) adapts the Singer–Thiery hybrid framework by replacing deterministic weights with random marginal gains and controls the dependence via a martingale concentration argument: the deviation of each marginal from its conditional expectation is bounded using Azuma–Hoeffding, yielding an additive O(sqrt(k log n)) term that is absorbed into the stated O(sqrt(k)) with high probability. The same concentration also ensures that the (1+ln2) multiplicative improvement carries over. To make this transparent, we will add a one-paragraph proof sketch to the introduction in the revision. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation extends external hybrid framework via independent modifications

full rationale

The paper adapts the hybrid greedy-local-search framework from Singer and Thiery (STOC 2025, distinct authors) to the submodular k-matroid-intersection setting. It explicitly notes that marginal gains depend on internal randomness and requires 'several non-trivial insights and algorithmic modifications' to carry over the analysis, yielding the stated ratio 2k ln2/(1+ln2) + O(sqrt(k)) and the improved (k+1)ln2 bound even in the weighted special case. No equation or claim reduces by construction to a fitted parameter, self-citation chain, or renamed input; the central guarantee rests on new technical arguments for randomness dependence rather than on any load-bearing self-referential step.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard definitions of submodularity and matroids together with the correctness of the Singer-Thiery hybrid framework; no new free parameters or invented entities are introduced.

axioms (2)
  • domain assumption A set function f is non-negative and monotone submodular.
    Standard assumption stated in the problem definition.
  • domain assumption Matroid intersection and matroid parity constraints are given as input.
    Core constraint class of the problem.

pith-pipeline@v0.9.0 · 5695 in / 1319 out tokens · 33817 ms · 2026-05-16T06:08:09.461547+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

42 extracted references · 42 canonical work pages

  1. [1]

    Arkin and Refael Hassin

    Esther M. Arkin and Refael Hassin. On local search for weightedk-set packing.Mathematics of Operations Research, 23(3):640–648, 1998

    work page 1998

  2. [2]

    Barvinok

    Alexander I. Barvinok. New algorithms for lineark-matroid intersection and matroidk-parity problems.Mathematical Programming, 69:449–470, 1995

    work page 1995

  3. [3]

    Ad/2 approximation for maximum weight independent set ind-claw free graphs.Nordic J

    Piotr Berman. Ad/2 approximation for maximum weight independent set ind-claw free graphs.Nordic J. Computing, 7(3):178–184, 2000

    work page 2000

  4. [4]

    Optimizing misdirection

    Piotr Berman and Piotr Krysta. Optimizing misdirection. InACM-SIAM Symposium on Discrete Algorithms (SODA), pages 192–201, 2003

    work page 2003

  5. [5]

    A tight linear time (1/2)- approximation for unconstrained submodular maximization.SIAM J

    Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. A tight linear time (1/2)- approximation for unconstrained submodular maximization.SIAM J. Computing, 44(5):1384– 1402, 2015

    work page 2015

  6. [6]

    Submodular maximization meets streaming: matchings, matroids, and more.Mathematical Programming, 154(1-2):225–247, 2015

    Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: matchings, matroids, and more.Mathematical Programming, 154(1-2):225–247, 2015

    work page 2015

  7. [7]

    Halld´ orsson

    Barun Chandra and Magn´ us M. Halld´ orsson. Greedy local improvement and weighted set packing approximation.J. Algorithms, 39(2):223–240, 2001

    work page 2001

  8. [8]

    Streaming algorithms for submodular function maximization

    Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. Streaming algorithms for submodular function maximization. InInternational Colloquium on Automata, Languages, and Program- ming ICALP, pages 318–330, 2015

    work page 2015

  9. [9]

    Maximizing a monotone submodular function subject to a matroid constraint.SIAM J

    Gruia Cualinescu, Chandra Chekuri, Martin P´ al, and Jan Vondr´ ak. Maximizing a monotone submodular function subject to a matroid constraint.SIAM J. Computing, 40(6):1740–1766, 2011. 28

    work page 2011

  10. [10]

    Cunningham

    William H. Cunningham. Improved bounds for matroid partition and intersection algorithms. SIAM J. Computing, 15(4):948–957, 1986

    work page 1986

  11. [11]

    Improved approximation for 3-dimensional matching via bounded pathwidth local search

    Marek Cygan. Improved approximation for 3-dimensional matching via bounded pathwidth local search. InIEEE Symposium on Foundations of Computer Science, FOCS, pages 509–518, 2013

    work page 2013

  12. [12]

    Submodular functions, matroids, and certain polyhedra

    Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Michael J¨ unger, Gerhard Reinelt, and Giovanni Rinaldi, editors,Combinatorial Optimization — Eureka, You Shrink!: Papers Dedicated to Jack Edmonds, pages 11–26. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003

    work page 2003

  13. [13]

    How do you want your greedy: Simultaneous or repeated?J

    Moran Feldman, Christopher Harshaw, and Amin Karbasi. How do you want your greedy: Simultaneous or repeated?J. Machine Learning Research, 24:72:1–72:87, 2023

    work page 2023

  14. [14]

    Improved approximations fork-exchange systems - (extended abstract)

    Moran Feldman, Joseph Naor, Roy Schwartz, and Justin Ward. Improved approximations fork-exchange systems - (extended abstract). InEuropean Symposium on Algorithms (ESA), pages 784–798, 2011

    work page 2011

  15. [15]

    Fisher, George L

    Marshall L. Fisher, George L. Nemhauser, and Laurence A. Wolsey. An analysis of approx- imations for maximizing submodular set functions—II.Mathematical Programming Studies, 8:73–87, 1978

    work page 1978

  16. [16]

    Approximating thek-set packing problem by local improve- ments

    Martin F¨ urer and Huiwen Yu. Approximating thek-set packing problem by local improve- ments. InInternational Symposium on Combinatorial Optimization ISCO, pages 408–420, 2014

    work page 2014

  17. [17]

    Magnanti

    Curtis Greene and Thomas L. Magnanti. Some abstract pivot algorithms.SIAM J. Applied Mathematics, 29(3):530–539, 1975

    work page 1975

  18. [18]

    Constrained non- monotone submodular maximization: Offline and secretary algorithms

    Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained non- monotone submodular maximization: Offline and secretary algorithms. InInternational Work- shop on Internet and Network Economics (WINE), pages 246–257, 2010

    work page 2010

  19. [19]

    On the complexity of approximatingk-set packing.Computational Complexity, 15(1):20–39, 2006

    Elad Hazan, Shmuel Safra, and Oded Schwartz. On the complexity of approximatingk-set packing.Computational Complexity, 15(1):20–39, 2006

    work page 2006

  20. [20]

    Matroid-constrained vertex cover.Theoretical Com- puter Science, 965:113977, 2023

    Chien-Chung Huang and Fran¸ cois Sellier. Matroid-constrained vertex cover.Theoretical Com- puter Science, 965:113977, 2023

    work page 2023

  21. [21]

    A weighted linear matroid parity algorithm.SIAM J

    Satoru Iwata and Yusuke Kobayashi. A weighted linear matroid parity algorithm.SIAM J. Computing, 51(2):17–238, 2022

    work page 2022

  22. [22]

    T.A. Jenkyns. The efficacy of the ”greedy” algorithm. InSoutheastern Conf. on Combinatorics, Graph Theory and Computing, pages 341–350, 1976

    work page 1976

  23. [23]

    Jensen and Bernhard Korte

    Per M. Jensen and Bernhard Korte. Complexity of matroid property algorithms.SIAM J. Computing, 11(1):184–190, 1982

    work page 1982

  24. [24]

    Richard M. Karp. Reducibility among combinatorial problems. InSymposium on the Com- plexity of Computer Computations, pages 85–103, 1972

    work page 1972

  25. [25]

    An analysis of the greedy heuristic for independence systems.Annals of Discrete Mathematics, 2:65–74, 1978

    Bernhard Korte and Dirk Hausmann. An analysis of the greedy heuristic for independence systems.Annals of Discrete Mathematics, 2:65–74, 1978. 29

    work page 1978

  26. [26]

    Lawler.Combinatorial optimization - networks and matroids

    E. Lawler.Combinatorial optimization - networks and matroids. Holt, Rinehart and Winston, New York, 1976

    work page 1976

  27. [27]

    Asymptotically optimal hardness fork-set packing and k-matroid intersection

    Euiwoong Lee, Ola Svensson, and Theophile Thiery. Asymptotically optimal hardness fork-set packing and k-matroid intersection. InACM Symposium on Theory of Computing (STOC), pages 54–61, 2025

    work page 2025

  28. [28]

    Submodular maximization over multiple ma- troids via generalized exchange properties.Mathematics of Operations Research, 35(4):795– 806, 2010

    Jon Lee, Maxim Sviridenko, and Jan Vondr´ ak. Submodular maximization over multiple ma- troids via generalized exchange properties.Mathematics of Operations Research, 35(4):795– 806, 2010

    work page 2010

  29. [29]

    Matroid matching: The power of local search

    Jon Lee, Maxim Sviridenko, and Jan Vondr´ ak. Matroid matching: The power of local search. SIAM J. Computing, 42(1):357–379, 2013

    work page 2013

  30. [30]

    Matroid matching and some applications.J

    L´ aszl´ o Lov´ asz. Matroid matching and some applications.J. of Combinatorial Theory, Series B, 28(2):208–236, 1980

    work page 1980

  31. [31]

    The matroid matching problem

    L´ aszl´ o Lov´ asz. The matroid matching problem. In L. Lov´ asz and V. T. S´ os, editors,Algebraic Methods in Graph Theory, Vol. II, pages 495–517. North-Holland, Amsterdam, 1981

    work page 1981

  32. [32]

    A parameterized view on matroid optimization problems.Theoretical Computer Science, 410(44):4471–4479, 2009

    D´ aniel Marx. A parameterized view on matroid optimization problems.Theoretical Computer Science, 410(44):4471–4479, 2009

    work page 2009

  33. [33]

    Fast constrained submodular maximization: Personalized data summarization

    Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submodular maximization: Personalized data summarization. InInternational Conference on Machine Learning (ICML), pages 1358–1367, 2016

    work page 2016

  34. [34]

    An improved approximation algorithm for the maximum weight indepen- dent set problem ind-claw free graphs

    Meike Neuwohner. An improved approximation algorithm for the maximum weight indepen- dent set problem ind-claw free graphs. InInternational Symposium on Theoretical Aspects of Computer Science, STACS, pages 53:1–53:20, 2021

    work page 2021

  35. [35]

    Passing the limits of pure local search for weightedk-set packing

    Meike Neuwohner. Passing the limits of pure local search for weightedk-set packing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1090–1137, 2023

    work page 2023

  36. [36]

    The limits of local search for weightedk-set packing.Mathematical Pro- gramming, 206(1):389–427, 2024

    Meike Neuwohner. The limits of local search for weightedk-set packing.Mathematical Pro- gramming, 206(1):389–427, 2024

    work page 2024

  37. [37]

    Springer-Verlag, Berlin Heidelberg, 2003

    Alexander Schrijver.Combinatorial Optimization: Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics. Springer-Verlag, Berlin Heidelberg, 2003

    work page 2003

  38. [38]

    Better approximation for weighted k-matroid intersection

    Neta Singer and Theophile Thiery. Better approximation for weighted k-matroid intersection. InACM Symposium on Theory of Computing (STOC), pages 1142–1153, 2025

    work page 2025

  39. [39]

    Large neighborhood local search for the maximum set packing problem

    Maxim Sviridenko and Justin Ward. Large neighborhood local search for the maximum set packing problem. InInternational Colloquium on Automata, Languages, and Programming (ICALP), pages 792–803, 2013

    work page 2013

  40. [40]

    Theophile Thiery.Approximation Algorithms for Independence Systems. Ph.D. thesis, Queen Mary University of London, London, United Kingdom, 2023

    work page 2023

  41. [41]

    An improved approximation for maximum weightedk-set packing

    Theophile Thiery and Justin Ward. An improved approximation for maximum weightedk-set packing. InACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1138–1162, 2023. 30

    work page 2023

  42. [42]

    A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems

    Justin Ward. A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems. InInternational Symposium on Theoretical Aspects of Computer Science (STACS), pages 42–53, 2012. 31

    work page 2012