arxiv: 2605.14296 · v1 · submitted 2026-05-14 · 💻 cs.DS

Recognition: no theorem link

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order

Niv Buchbinder , Moran Feldman , Siyue Liu , Sherry Sarkar

Authors on Pith no claims yet

Pith reviewed 2026-05-15 02:23 UTC · model grok-4.3

classification 💻 cs.DS

keywords semi-streamingsubmodular maximizationrandom ordermatroid constraintsapproximation algorithmsstreaming algorithmscombinatorial constraints

0 comments

The pith

Random arrival order enables semi-streaming algorithms to achieve better approximations than adversarial order for 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 develops algorithms that process submodular maximization problems in one or few passes over a stream of elements arriving in random order. It shows that this random order model allows significantly better performance than the adversarial order model for constraints like matroids. Specifically, for monotone submodular functions under matroid constraints, it achieves a (1 - 1/e - ε) approximation using exponentially fewer passes than previous methods. The results extend to other constraint classes such as matroid p-parity and p-systems, often providing the first improvements over adversarial settings.

Core claim

By introducing a general translation tool from offline algorithms to random order semi-streaming and a specific semi-streaming variant for matroids, the work proves that random order permits a separation from adversarial semi-streaming, with exponential savings in passes for the standard 1-1/e approximation guarantee under matroid constraints.

What carries the argument

A general translation mechanism that converts offline algorithms for various constraints into random order semi-streaming algorithms, along with a semi-streaming adaptation of an offline matroid algorithm.

Load-bearing premise

The elements arrive in an order chosen uniformly at random from all possible permutations.

What would settle it

A concrete matroid instance and monotone submodular function on which any semi-streaming algorithm using the claimed number of passes fails to reach 1-1/e-ε approximation when the arrival order is forced to be adversarial instead of random.

Figures

Figures reproduced from arXiv: 2605.14296 by Moran Feldman, Niv Buchbinder, Sherry Sarkar, Siyue Liu.

read the original abstract

We study random order semi-streaming algorithms for submodular maximization under a wide range of combinatorial constraint classes, including matroids, matroid $p$-parity, $p$-exchange systems and $p$-systems. For most of these classes of constraints, our results are the first improvement over what is known to be achievable for adversarial order. For matroids, matching and $p$-matchoids, previous random order results were known, and we improve over some of these as well. In the case of matroids, our improved results show a separation between adversarial and random order semi-streaming algorithms, and exponentially improve the number of passes necessary for getting $1 - 1/e - \varepsilon$ approximation for maximizing a monotone submodular function subject to a matroid constraint. We also prove a new hardness result showing a similar separation for $p$-systems. Our results are based on two new technical tools. One tool provides a general way to translate offline algorithms for many classes of constraints into random order semi-streaming algorithms. The other tool is a semi-streaming variant of a recently proposed offline algorithm for matroid constraints.

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.

Desk Editor's Note private letter to a colleague

The paper gives the first random-order semi-streaming improvements for several submodular constraint classes and proves separations for matroids and p-systems via two new translation tools, but the gains rest on perfectly uniform random arrival.

read the letter

The main thing to know is that this paper delivers the first random-order semi-streaming results that beat adversarial-order bounds for p-parity, p-exchange, and p-systems, plus a separation for matroids that cuts the number of passes exponentially to reach a (1-1/e - eps) approximation. For matroids, matching, and p-matchoids it also improves on the existing random-order work. The two tools—a general offline-to-random-order translator and a semi-streaming matroid variant—look like the real technical contribution and seem to follow naturally from the cited offline algorithms. The new hardness result for p-systems is a clean addition that shows the separation is not matroid-specific. These pieces are worth checking because they expand what is known in the random-order model. The main limitation is the strict uniform random permutation assumption. The analyses almost certainly rely on symmetry for sampling and concentration, so any deviation or hidden correlation in the arrival order would break the guarantees and erase the claimed separation. That is a real but standard caveat for this line of work rather than a flaw in the math itself. The abstract gives no proof sketches, so soundness cannot be fully verified from what is here, but the description shows no signs of circularity or post-hoc parameter fitting. This paper is for specialists in streaming algorithms and submodular optimization who already work in random-order settings. A reader focused on that model will find the new tools and separations useful. It deserves peer review to confirm the tool translations and the pass-reduction claims hold up in the full proofs.

Referee Report

2 major / 2 minor

Summary. The paper develops semi-streaming algorithms for monotone submodular maximization under random arrival order for constraint classes including matroids, matroid p-parity, p-exchange systems, and p-systems. It introduces a general offline-to-random-order translator and a semi-streaming variant of an offline matroid algorithm, claiming improved approximation ratios over adversarial-order results for most classes, improvements on some prior random-order results, a separation between adversarial and random-order semi-streaming for matroids with an exponential reduction in passes to achieve (1-1/e-ε) approximation, and a new hardness result establishing a similar separation for p-systems.

Significance. If the derivations hold, the work is significant for establishing the first improvements over adversarial semi-streaming for several constraint families, demonstrating concrete separations that highlight the benefit of random order, and exponentially reducing pass complexity for near-optimal matroid-constrained submodular maximization. The two technical tools appear to be the key enablers.

major comments (2)

[Abstract and the sections describing the two technical tools] The separation claim for matroids and the exponential pass improvement for (1-1/e-ε) approximation rest on the assumption that the arrival order is a uniformly random permutation. The analyses of both the general translator and the matroid-specific tool must be examined for dependence on perfect permutation symmetry in sampling or concentration arguments; if these arguments fail under approximate randomness or hidden correlations, the separation disappears.
[The hardness result section] The new hardness result for p-systems establishing a separation should be checked for whether its lower bound construction assumes the same uniform random-order model as the algorithms, and whether the bound is tight with the achieved ratios.

minor comments (2)

[Related work or results overview] Add explicit comparisons of the new pass complexities and approximation ratios against prior adversarial and random-order results in a summary table.
[Preliminaries] Clarify the precise definition of 'semi-streaming' (memory bound) and how the translator preserves it for each constraint class.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address the major comments below, clarifying the model assumptions and proof dependencies while maintaining the accuracy of our claims.

read point-by-point responses

Referee: [Abstract and the sections describing the two technical tools] The separation claim for matroids and the exponential pass improvement for (1-1/e-ε) approximation rest on the assumption that the arrival order is a uniformly random permutation. The analyses of both the general translator and the matroid-specific tool must be examined for dependence on perfect permutation symmetry in sampling or concentration arguments; if these arguments fail under approximate randomness or hidden correlations, the separation disappears.

Authors: Our results are stated and proved under the standard uniform random permutation model for random-order streams. The general translator (Section 3) and matroid semi-streaming algorithm (Section 4) explicitly use symmetry properties and concentration bounds that hold for uniform random permutations; these are invoked in the sampling arguments and expectation calculations. We make no claims about robustness to approximate randomness or adversarial correlations, as those constitute different input models. The separation between adversarial-order and random-order semi-streaming is therefore well-defined and holds under the stated uniform random-order assumption. No changes to the manuscript are required. revision: no
Referee: [The hardness result section] The new hardness result for p-systems establishing a separation should be checked for whether its lower bound construction assumes the same uniform random-order model as the algorithms, and whether the bound is tight with the achieved ratios.

Authors: The hardness result (Section 5) is constructed and proved under the identical uniform random-order model used for the algorithms. The lower-bound instance is drawn from a random permutation to demonstrate that, even in random order, semi-streaming algorithms for p-systems cannot achieve the approximation ratios obtained by our algorithms without additional passes. The result is not claimed to be tight; it suffices to establish the separation from the adversarial-order setting. We can insert a brief clarifying sentence in Section 5 to restate the model consistency if the referee prefers. revision: partial

Circularity Check

0 steps flagged

No significant circularity; results derived from new translator tools

full rationale

The paper introduces two explicit new technical tools—an offline-to-random-order translator and a semi-streaming matroid variant—whose analyses convert known offline guarantees into streaming approximations under the stated uniform random permutation model. No equations or claims reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations; the separation for matroids and pass improvements follow directly from the properties of these tools rather than tautological renaming or imported uniqueness theorems. The random-order assumption is stated upfront and is not derived from the results themselves.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract does not introduce new fitted constants or invented entities; it relies on standard definitions of submodularity, matroids, and random permutation arrival.

axioms (2)

standard math Submodular functions satisfy diminishing returns: f(A ∪ {e}) - f(A) ≥ f(B ∪ {e}) - f(B) for A ⊆ B.
Invoked implicitly as the objective class throughout the abstract.
domain assumption Arrival order is a uniform random permutation of the ground set.
Central modeling assumption stated in the title and abstract.

pith-pipeline@v0.9.0 · 5504 in / 1332 out tokens · 144182 ms · 2026-05-15T02:23:31.956116+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

300 extracted references · 300 canonical work pages · 5 internal anchors

[1]

Niv Buchbinder and Moran Feldman , title =

work page
[2]

Nguyen and Andrew Suh , title =

Naor Alaluf and Alina Ene and Moran Feldman and Huy L. Nguyen and Andrew Suh , title =. Math. Oper. Res. , volume =

work page
[3]

Streaming Submodular Maximization Under Matroid Constraints , booktitle = proc #

Moran Feldman and Paul Liu and Ashkan Norouzi. Streaming Submodular Maximization Under Matroid Constraints , booktitle = proc #

work page
[4]

The one-way communication complexity of submodular maximization with applications to streaming and robustness , booktitle = proc #

Moran Feldman and Ashkan Norouzi. The one-way communication complexity of submodular maximization with applications to streaming and robustness , booktitle = proc #

work page
[5]

Ehsan Kazemi and Marko Mitrovic and Morteza Zadimoghaddam and Silvio Lattanzi and Amin Karbasi , title =

work page
[6]

2013 , url =

MohammadHossein Bateni and Mohammad Taghi Hajiaghayi and Morteza Zadimoghaddam , title =. 2013 , url =

work page 2013
[7]

Niv Buchbinder and Moran Feldman and Yuval Filmus and Mohit Garg , title =. Math. Program. , volume =. 2020 , url =

work page 2020
[8]

2018 , url =

Moran Feldman and Rico Zenklusen , title =. 2018 , url =

work page 2018
[9]

Eric Balkanski and Aviad Rubinstein and Yaron Singer , title =. Oper. Res. , volume =. 2022 , url =

work page 2022
[10]

Eric Balkanski and Yaron Singer , title =

work page
[11]

Chandra Chekuri and Kent Quanrud , title =

work page
[12]

Baharan Mirzasoleiman and Amin Karbasi and Rik Sarkar and Andreas Krause , title =. J. Mach. Learn. Res. , volume =

work page
[13]

A New Framework for Distributed Submodular Maximization , booktitle = proc #

work page
[14]

SIGecom Exchanges , volume =

Sepehr Assadi and Sahil Singla , title =. SIGecom Exchanges , volume =

work page
[15]

Shahar Dobzinski and Uriel Feige and Michal Feldman , title =

work page
[16]

Elenberg and Moran Feldman and Amin Karbasi , title =

Loay Raed Mualem and Ethan R. Elenberg and Moran Feldman and Amin Karbasi , title =

work page
[17]

A Primal-Dual Analysis of Monotone Submodular Maximization , journal =

Deeparnab Chakrabarty and Luc C. A Primal-Dual Analysis of Monotone Submodular Maximization , journal =

work page
[18]

An improved cutting plane method for convex optimization, convex-concave games, and its applications , author=

work page
[19]

Niv Buchbinder and Moran Feldman and Roy Schwartz , title =. Math. Oper. Res. , volume =

work page
[20]

Fully Dynamic k -Median with Near-Optimal Update Time and Recourse , author=

work page
[21]

Fully dynamic consistent k-center clustering , author=

work page
[22]

Consistent k-clustering for general metrics , author=

work page
[23]

Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary , author=

work page
[24]

The power of recourse for online MST and TSP , author=

work page
[25]

Fully-dynamic submodular cover with bounded recourse , author=

work page
[26]

arXiv preprint arXiv:2504.17679 , year=

Extremal negative dependence and the strongly Rayleigh property , author=. arXiv preprint arXiv:2504.17679 , year=

work page arXiv
[27]

Deterministic algorithm and faster algorithm for submodular maximization subject to a matroid constraint , author=

work page
[28]

A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization , booktitle =

Yin Tat Lee and Aaron Sidford and Sam Chiu. A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization , booktitle =

work page
[29]

Vaidya , title =

Pravin M. Vaidya , title =. Math. Program. , volume =

work page
[30]

SSR Computational Mathematics and Mathematical Physics , volume =

Leonid G Khachiyan , title =. SSR Computational Mathematics and Mathematical Physics , volume =

work page
[31]

Maintaining assignments online: Matching, scheduling, and flows , author=

work page
[32]

Online discrepancy with recourse for vectors and graphs , author=

work page
[33]

Proceedings of the 9th ACM conference on Electronic commerce , pages=

Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions , author=. Proceedings of the 9th ACM conference on Electronic commerce , pages=

work page
[34]

Fast algorithms for maximizing submodular functions , author=

work page
[35]

Operations Research Letters (ORL) , volume=

A note on maximizing a submodular set function subject to a knapsack constraint , author=. Operations Research Letters (ORL) , volume=

work page
[36]

A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint , author=

work page
[37]

Mathematics of Operations Research (MOR) , volume=

Approximations for monotone and nonmonotone submodular maximization with knapsack constraints , author=. Mathematics of Operations Research (MOR) , volume=

work page
[38]

C. J. Argue and Anupam Gupta and Ziye Tang and Guru Guruganesh , title =. J

work page
[39]

Maximizing non-monotone submodular functions , author=

work page
[40]

Chasing nested convex bodies nearly optimally , author=

work page
[41]

ACM Journal of Experimental Algorithmics , volume=

Recent advances in fully dynamic graph algorithms--a quick reference guide , author=. ACM Journal of Experimental Algorithmics , volume=. 2022 , note =

work page 2022
[42]

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity , author=

work page
[43]

arXiv preprint arXiv:2403.02582 , year=

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication , author=. arXiv preprint arXiv:2403.02582 , year=

work page arXiv
[44]

arXiv preprint arXiv:2404.06069 , year=

Fully Dynamic Matching and Ordered Ruzsa-Szemer\'edi Graphs , author=. arXiv preprint arXiv:2404.06069 , year=

work page arXiv
[45]

Communications in Statistics - Theory and Methods , volume=

Positive dependence in multivariate distributions , author=. Communications in Statistics - Theory and Methods , volume=. 1981 , publisher=

work page 1981
[46]

The Annals of Statistics , pages=

Negative association of random variables with applications , author=. The Annals of Statistics , pages=

work page
[47]

BRICS Report Series , volume=

Balls and bins: A study in negative dependence , author=. BRICS Report Series , volume=

work page
[48]

Random Structures & Algorithms , volume=

Tail bounds for occupancy and the satisfiability threshold conjecture , author=. Random Structures & Algorithms , volume=

work page
[49]

Panconesi, Alessandro and Srinivasan, Aravind , title =

work page
[50]

Balanced matroids , booktitle = proc #

Feder, Tom. Balanced matroids , booktitle = proc #

work page
[51]

Journal of Theoretical Probability , volume=

A comparison theorem on moment inequalities between negatively associated and independent random variables , author=. Journal of Theoretical Probability , volume=

work page
[52]

A note on the almost sure convergence of sums of negatively dependent random variables , journal=

Matu. A note on the almost sure convergence of sums of negatively dependent random variables , journal=

work page
[53]

Stochastic Processes and Their Applications , volume=

Shao, Qi-Man and Su, Chun , title=. Stochastic Processes and Their Applications , volume=

work page
[54]

Negative dependence and the geometry of polynomials , journal=

Borcea, Julius and Br. Negative dependence and the geometry of polynomials , journal=

work page
[55]

Bhattiprolu, Vijay and Wajc, David , year=

work page
[56]

Communications in Mathematical Physics , volume=

Fortuin, Cees M and Kasteleyn, Pieter W and Ginibre, Jean , title=. Communications in Mathematical Physics , volume=

work page
[57]

BRICS Report Series , volume=

Negative dependence through the FKG inequality , author=. BRICS Report Series , volume=

work page
[58]

Multi-budgeted matchings and matroid intersection via dependent rounding , booktitle = proc #

Chekuri, Chandra and Vondr. Multi-budgeted matchings and matroid intersection via dependent rounding , booktitle = proc #

work page
[59]

Wallenius, Kenneth T , title=

work page
[60]

Biometrika , volume=

Geary, RC , title=. Biometrika , volume=

work page
[61]

Combinatorics, Probability and Computing , volume=

Pemantle, Robin and Peres, Yuval , title=. Combinatorics, Probability and Computing , volume=. 2014 , publisher=

work page 2014
[62]

Panconesi, Alessandro and Srinivasan, Aravind , title=

work page
[63]

Naval research logistics quarterly , volume=

Kuhn, Harold W , title=. Naval research logistics quarterly , volume=

work page
[64]

Proceedings of the National Academy of Sciences , volume=

Berge, Claude , title=. Proceedings of the National Academy of Sciences , volume=. 1957 , publisher=

work page 1957
[65]

Canadian Journal of mathematics , volume=

Edmonds, Jack , title=. Canadian Journal of mathematics , volume=

work page
[66]

Hopcroft, John E and Karp, Richard M , journal=. An n\^. 1973 , publisher=

work page 1973
[67]

Micali, Silvio and Vazirani, Vijay V , booktitle = proc #. An

work page
[68]

Gabow, Harold N and Kariv, Oded , title=

work page
[69]

Cole, Richard and Hopcroft, John , title=

work page
[70]

Schrijver, Alexander , title=

work page
[71]

Combinatorica , volume=

Cole, Richard and Ost, Kirstin and Schirra, Stefan , title=. Combinatorica , volume=

work page
[72]

ACM Transactions on Algorithms (TALG) , volume=

Goel, Ashish and Kapralov, Michael and Khanna, Sanjeev , title=. ACM Transactions on Algorithms (TALG) , volume=

work page
[73]

Perfect Matchings in \~O(n^{1.5}) Time in Regular Bipartite Graphs

Goel, Ashish and Kapralov, Michael and Khanna, Sanjeev , title=. arXiv preprint arXiv:0902.1617 , year=

work page internal anchor Pith review Pith/arXiv arXiv
[74]

Goel, Ashish and Kapralov, Michael and Khanna, Sanjeev , title=

work page
[75]

1993 , publisher=

Ahuja, Ravindra K and Magnanti, Thomas L and Orlin, James B , title=. 1993 , publisher=

work page 1993
[76]

Matching theory , volume=

Lov. Matching theory , volume=. 2009 , publisher=

work page 2009
[77]

2010 , publisher=

Motwani, Rajeev and Raghavan, Prabhakar , title=. 2010 , publisher=

work page 2010
[78]

Aggarwal, Gagan and Motwani, Rajeev and Shah, Devavrat and Zhu, An , title=

work page
[79]

Modern graph theory , year=2013, publisher=

Bollob. Modern graph theory , year=2013, publisher=

work page 2013
[80]

Information Processing Letters (IPL) , volume=

Alon, Noga , title=. Information Processing Letters (IPL) , volume=

work page

Showing first 80 references.