Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
Niv Buchbinder, Moran Feldman, Siyue Liu, Sherry Sarkar · 2026
Read Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order by Niv Buchbinder, Moran Feldman, Siyue Liu, Sherry Sarkar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14296.txt.
Introduction
Buchbinder and colleagues study semi-streaming algorithms, methods that read data in few passes with limited memory, for maximizing a submodular function, a function with diminishing returns, under combinatorial constraints. For matroids and related constraint classes, their random-order results are the first to beat what adversarial ordering allows. For matroids they sharply cut the passes needed for near-optimal results. A new hardness result shows a similar separation for p-systems. Two new tools drive the work, including a general translation from offline algorithms to random-order streaming ones.
Catalog record
| CREATOR | Niv Buchbinder, Moran Feldman, Siyue Liu, Sherry Sarkar |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 157833 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.14296
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order Niv Buchbinder, Moran Feldman, Siyue Liu, Sherry Sarkar Abstract We study random order semi-streaming algorithms for submodular maximization under a wide range of combinatorial constraint classes, including matroids, matroid p p -parity, p p -exchange systems and p 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 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 − ε 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 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. Keywords: submodular maximization, semi-streaming algorithms, random order, matroids, independence systems 1 Introduction Submodular maximization is a central topic in combinatorial optimization, studied extensively over the past five decades since the seminal works of [ FNW78 , NWF78 , NW78 ] . A typical problem in this field consists of a submodular objective function f:2^{{\mathcal{N}}}\to{\mathbb{R}} over a ground set {\mathcal{N}} and a constraint specifying the set {\mathcal{I}}\subseteq 2^{\mathcal{N}} of feasible solutions. 1 1 1 A set function f\colon 2^{\mathcal{N}}\to{\mathbb{R}} is submodular if for every pair of sets S\subseteq T\subseteq{\mathcal{N}} and element u\in{\mathcal{N}}\setminus T , it holds that f(u\mid S)\geq f(u\mid T) , where f(u\mid S)\triangleq f(S\cup\{u\})-f(S) is the marginal gain of adding u to S . The goal of the problem is to find a set S\in{\mathcal{I}} that (approximately) maximizes f among all the sets of {\mathcal{I}} . Naturally, the approximability of this problem is significantly affected by the properties of the constraint, and accordingly, many results have been obtained for the above problem for particular classes of constraints (see [ NWF78 , CCPV11 , CVZ14 , FW14 , SVW17 , BF24a , BF24b , BF25 ] for a few examples of such results). To make this more concrete, let us introduce some details. It is customary to identify the constraint with the pair ({\mathcal{N}},{\mathcal{I}}) . The constraint is called an independence system if {\mathcal{I}} is non-empty and down-closed (i.e., if A\subseteq B and B\in{\mathcal{I}} , then A\in{\mathcal{I}} ). Independence systems are a very broad class of constraints, and already capture constraints that are hard to approximate even for linear objectives (e.g., maximum independent set in graphs). Thus, much of the literature focuses on structured subclasses of independence systems that do admit good approximation ratios. A well-known example of such a subclass is the class of matroids, which captures a diverse set of scenarios such as linear independence of vectors, forests in graphs and laminar families of bounds. A more general subclass of independence systems is the class of p -systems (parametrized by an integer p\geq 1 ), which admits weaker approximation guarantees, but captures additional kinds of constraints such as (hyper) matching, asymmetric traveling salesperson and packing problems with low column sparsity. As mentioned above, submodular maximization subject to classes of independence systems has been studied extensively. At first, these studies concentrated on the standard offline computational model (see the works referenced above). However, motivated by various applications, later studies considered submodular maximization in a variety of other computational models, including online and secretary settings [ BHZ13 , BFFG20 , BFS19 , FZ18 ] , parallel computation [ BRS22 , BS18 , CQ19a , CQ19b ] and distributed computing [ MKSK16 , dPBENW16 ] . Our focus in this work is the data stream model, which is motivated by modern applications in data science and machine learning involving massive ground sets. In this model, the elements of the ground set {\mathcal{N}} arrive one after the other in a stream. The goal is to design an algorithm that scans the elements of {\mathcal{N}} in one pass over the stream (or a small number of passes), and then outputs a good feasible solution. Since the motivation for this model is in massive ground sets, an algorithm for this model is considered interesting only if its memory is small compared to the size n of {\mathcal{N}} . Note, however, that even storing the output set might require \Theta(r) memory, where r is the maximum size of a feasible set (in the context of independence system constraints, r is known as the rank of the independence system). Thus, it is natural to aim for algorithms whose space complexity is O(r\cdot{\mathtt{Polylog}}(n)) . Such algorithms are called semi-streaming algorithms. 2 2 2 When the class of constraints is parametrized by p , we say that a data stream algorithm is a semi-streaming algorithm if its space complexity simplifies to O(r\cdot{\mathtt{Polylog}}(n)) when p is treated as a constant. Semi-streaming algorithms have been developed for submodular maximization problems involving many kinds of constraints, including cardinality constraints [ BMKK14 , KMZ+19 , AEF+22 , FNSZ23 ] , matroid and matroid intersection constraints [ CK15 , CGQ15 , Sha20 , HKFK22 , RZ22 , FNSZ23 , GJS23 , NVZ25 , FLN+26 ] , matching [ LW21 ] , p -systems [ HKFK20 ] and knapsack [ HKY20 , HK21 ] . Running time is typically a secondary concern in this setting. Accordingly, the literature includes both polynomial-time algorithms with running time {\mathtt{Poly}}(n) and fixed-parameter tractable (FPT) algorithms with running time g(r)\cdot{\mathtt{Poly}}(n) , where the dependence g on r may be arbitrary, while the dependence on n remains polynomial. The standard data stream model assumes an adversarial arrival order of the elements. However, in many applications it is more realistic to assume that the arrival order is not adversarial, but rather uniformly random. This random-order assumption, originating in the classical secretary problem and its many extensions (see, e.g., [ Kle05 , Lac14 , BIKK18 , FSZ18 , FZ18 , STV21 ] ), is well-motivated and has become central in practice (see, e.g., [ Rou20 , Chapter 11] ). 1.1 Our Results We design improved semi-streaming approximation algorithms under a uniformly random arrival order for maximizing linear, submodular and monotone submodular objectives. 3 3 3 A set function f\colon 2^{\mathcal{N}}\to{\mathbb{R}} is monotone if f(S)\leq f(T) for every two sets S\subseteq T\subseteq{\mathcal{N}} . Our algorithms apply to a variety of classes of independence systems from the literature. Readers less familiar with these constraint classes are referred to Section 2 for formal definitions and the relationships between them. Our first result concerns single-pass semi-streaming algorithms. Theorem 1.1 (Single-pass algorithms) . Let {\mathcal{M}}=({\mathcal{N}},{\mathcal{I}}) be an independence system of rank r , and let f\colon 2^{\mathcal{N}}\to{{\mathbb{R}}_{\geq 0}} be a non-negative function. For any sufficiently small \varepsilon>0 , there are single-pass semi-streaming algorithms that under a uniformly random arrival order store O\!\left(\nicefrac{{r}}{{\varepsilon^{2}}}\log^{2}(r/\varepsilon)\right) elements and achieve the approximation ratios appearing in bold on the two rightmost columns of Table 1 —up to an error term of