pith. sign in

arxiv: 2606.28558 · v1 · pith:AQNMXULKnew · submitted 2026-06-26 · 💻 cs.DS

Incremental Submodular Maximization: Better Than Greedy

Marcin Bienkowski , Joakim Blikstad , Jaros{\l}aw Byrka , Mart\'in Costa , Yann Disser , Annette Lutz This is my paper

Pith reviewed 2026-06-30 01:03 UTC · model grok-4.3

classification 💻 cs.DS
keywords incremental submodular maximizationadaptive scaling algorithmcompetitive ratiogreedy algorithmcardinality constraintapproximation algorithmordering of ground set
0
0 comments X

The pith

An adaptive scaling algorithm achieves a competitive ratio of 1.373 for incremental submodular maximization.

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

The paper studies submodular maximization under a growing cardinality constraint and seeks one ordering of the ground set whose every prefix is a good solution for its own size. The classic greedy algorithm delivers a competitive ratio of roughly 1.582 across all sizes. The authors give an adaptive scaling algorithm that improves the ratio to 1.373 while also proving that no deterministic algorithm can guarantee better than 1.25 in the worst case. A reader would care because many applications need usable solutions at every scale without restarting the computation each time the constraint changes.

Core claim

The central claim is that an adaptive scaling algorithm exists for the incremental submodular maximization problem and attains a competitive ratio of 1.373, strictly better than the e/(e-1) guarantee of the greedy algorithm, together with a deterministic lower bound of 1.25 on the best possible ratio any algorithm can achieve.

What carries the argument

The adaptive scaling algorithm, which dynamically adjusts scaling factors to produce a single ordering competitive for every cardinality.

If this is right

  • A single ordering suffices for all cardinalities instead of recomputing for each k.
  • The new ratio of 1.373 improves the only previously known general guarantee.
  • No deterministic algorithm can beat a ratio of 1.25 on every instance.
  • The ordering remains useful even when the final cardinality is unknown in advance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the algorithm runs in near-linear time it could replace greedy in large-scale sensor or feature-selection pipelines.
  • The same scaling idea might transfer to other incremental problems such as matroid or knapsack maximization.
  • Closing the gap between 1.373 and the 1.25 lower bound would require either a new algorithm or a tighter analysis.

Load-bearing premise

The competitive ratio is measured separately against the optimal solution for each cardinality k.

What would settle it

A concrete submodular function and ground set on which the adaptive scaling algorithm produces a worst-case ratio over all prefixes larger than 1.373.

read the original abstract

We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of the ordering yields a good solution for its respective cardinality. A classical result in this setting is that the greedy algorithm achieves a competitive ratio, i.e., an approximation guarantee across all cardinalities, of $\mathrm{e}/(\mathrm{e}-1) \approx 1.582$. No better general guarantee was previously known. We present an adaptive scaling algorithm achieving a competitive ratio of $1.373$. We complement our result by a deterministic lower bound of $1.25$ on the best possible competitive ratio for incremental submodular maximization.

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

0 major / 0 minor

Summary. The manuscript considers incremental submodular maximization under a sequence of increasing cardinality constraints. It seeks an ordering of the ground set such that every prefix yields a competitive solution for its respective cardinality k. The central contribution is an adaptive scaling algorithm claimed to achieve a competitive ratio of 1.373 (improving on the greedy algorithm's e/(e-1) ≈ 1.582), together with a deterministic lower bound of 1.25 on the best possible competitive ratio.

Significance. If the claimed ratio and its analysis hold, the result is significant: it supplies the first general improvement over the long-standing greedy guarantee in the incremental setting. The 1.373 ratio constitutes a concrete advance in approximation algorithms for submodular functions, while the 1.25 lower bound supplies a useful benchmark. The adaptive scaling technique itself may be of independent interest.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their review and for acknowledging the potential significance of the result if the analysis holds. No specific major comments were listed in the report, so we have no point-by-point items to address.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The abstract presents the 1.373 competitive ratio as the output of an adaptive scaling algorithm and states a separate deterministic lower bound of 1.25, with no equations, fitted parameters, or self-citations shown that would reduce the claimed guarantee to an input by construction. No load-bearing step matches any of the enumerated circularity patterns because the derivation chain itself is not supplied in inspectable form and the given material contains no self-referential definitions or renamings of known results. The result is therefore treated as self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Insufficient information from the abstract alone to identify any free parameters, axioms, or invented entities used by the algorithm or proof.

pith-pipeline@v0.9.1-grok · 5661 in / 1079 out tokens · 50958 ms · 2026-06-30T01:03:26.438965+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

20 extracted references · 16 canonical work pages

  1. [1]

    Badanidiyuru, B

    A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, and A. Krause. Streaming submodular maximization: Massive data summarization on the fly. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) , pages 671--680, 2014. doi:10.1145/2623330.2623637

    work page doi:10.1145/2623330.2623637 2014

  2. [2]

    Bernstein, Y

    A. Bernstein, Y. Disser, M. Groß, and S. Himburg. General bounds for incremental maximization. Mathematical Programming, 191 0 (2): 0 953--979, 2022. doi:10.1007/s10107-020-01576-0

    work page doi:10.1007/s10107-020-01576-0 2022

  3. [3]

    A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek. Guarantees for greedy maximization of non-submodular functions with applications. In Proceedings of the 34th International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pages 498--507, 2017. URL https://proceedings.mlr.press/v70/bian17a.html

    2017

  4. [4]

    Buchbinder, M

    N. Buchbinder, M. Feldman, J. Naor, and R. Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1433--1452, 2014. doi:10.1137/1.9781611973402.106

    work page doi:10.1137/1.9781611973402.106 2014

  5. [5]

    Buchbinder, M

    N. Buchbinder, M. Feldman, J. Naor, and R. Schwartz. A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM Journal on Computing, 44 0 (5): 0 1384--1402, 2015. doi:10.1137/130929205

    work page doi:10.1137/130929205 2015

  6. [6]

    Calinescu, C

    G. Calinescu, C. Chekuri, M. P \'a l, and J. Vondr \'a k. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40 0 (6): 0 1740--1766, 2011. doi:10.1137/080733991

    work page doi:10.1137/080733991 2011

  7. [7]

    Das and D

    A. Das and D. Kempe. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. Journal of Machine Learning Research, 19 0 (3): 0 1--34, 2018. URL https://jmlr.org/papers/v19/16-534.html

    2018

  8. [8]

    Disser and D

    Y. Disser and D. Weckbecker. Unified greedy approximability beyond submodular maximization. SIAM Journal on Discrete Mathematics, 38 0 (1): 0 348--379, 2024. doi:10.1137/22M1526952

    work page doi:10.1137/22m1526952 2024

  9. [9]

    Disser and D

    Y. Disser and D. Weckbecker. Incremental maximization for a broad class of objectives. In Proceedings of the 33rd European Symposium on Algorithms (ESA), pages 92:1--92:14, 2025. doi:10.4230/LIPIcs.ESA.2025.92

    work page doi:10.4230/lipics.esa.2025.92 2025

  10. [10]

    Disser, M

    Y. Disser, M. Klimm, K. Schewior, and D. Weckbecker. Incremental maximization via continuization. In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP), pages 47:1--47:17, 2023. doi:10.4230/LIPIcs.ICALP.2023.47

    work page doi:10.4230/lipics.icalp.2023.47 2023

  11. [11]

    E. R. Elenberg, R. Khanna, A. G. Dimakis, and S. Negahban. Restricted strong convexity implies weak submodularity. Annals of Statistics, 46 0 (6B): 0 3539--3568, 2018. doi:10.1214/17-AOS1679

    work page doi:10.1214/17-aos1679 2018

  12. [12]

    U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45 0 (4): 0 634--652, 1998. doi:10.1145/285055.285059

    work page doi:10.1145/285055.285059 1998

  13. [13]

    Feige, V

    U. Feige, V. S. Mirrokni, and J. Vondr \'a k. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40 0 (4): 0 1133--1153, 2011. doi:10.1137/090779346

    work page doi:10.1137/090779346 2011

  14. [14]

    Harshaw, M

    C. Harshaw, M. Feldman, J. Ward, and A. Karbasi. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pages 2634--2643, 2019. URL http://proceedings.mlr.press/v97/harshaw19a.html

    2019

  15. [15]

    G. L. Nemhauser and L. A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3 0 (3): 0 177--188, 1978. doi:10.1287/moor.3.3.177

    work page doi:10.1287/moor.3.3.177 1978

  16. [16]

    G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14 0 (1): 0 265--294, 1978. doi:10.1007/BF01588971

    work page doi:10.1007/bf01588971 1978

  17. [17]

    R. Rado. A theorem on independence relations. The Quarterly Journal of Mathematics, 13 0 (1): 0 83--89, 1942. doi:10.1093/qmath/os-13.1.83

    work page doi:10.1093/qmath/os-13.1.83 1942

  18. [18]

    Sviridenko

    M. Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operartions Research Letters, 32: 0 41--43, 2004. doi:10.1016/s0167-6377(03)00062-2

    work page doi:10.1016/s0167-6377(03)00062-2 2004

  19. [19]

    Vondr\' a k

    J. Vondr\' a k. Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42 0 (1): 0 265--304, 2013. doi:10.1137/110832318

    work page doi:10.1137/110832318 2013

  20. [20]

    Weckbecker

    D. Weckbecker. Competitive Analysis for Incremental Maximization. PhD thesis, Technische Universit \"a t Darmstadt, 2024

    2024