Introduction
Online algorithms with recourse have emerged as a central paradigm for optimization over evolving inputs: they maintain good solutions as the input changes, while limiting how much these solutions change, either at each update or in aggregate over the entire sequence. This paradigm has been developed for a broad range of fundamental problems, including Steiner trees [32 , 29 ] , minimum spanning trees and TSP [36 ] , scheduling [40 ] , bin packing [24 ] , set cover [31 ] , bipartite matching [10 , 7 ] , k k k -clustering [34 , 26 ] , and submodular maximization [19 , 20 ] .
Such algorithms face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. Approximation guarantees reflect the joint effect of all three, so they do not reveal what stability itself costs. Isolating this cost requires removing the other two obstacles, which leads to the following question:
How much solution quality must be sacrificed to maintain stability when the entire future is known and computation is unlimited?
We study this question for monotone submodular maximization under a cardinality constraint [33 ] (Nemhauser et al. 1978). We give the algorithm full knowledge of the arrival sequence and unrestricted computational power. Each maintained solution must use only elements that have already arrived, and consecutive solutions may differ by only a constant number of elements. Even with full foresight, preparing a solution for future arrivals can compromise its current value, while postponing changes can leave too little time to complete them. The challenge is to plan solutions and transitions that remain close to the current optimum while respecting the recourse bound.
The Model
Let f : 2 X → R ≥ 0 f : 2^{X} \to\mathbb{R}_{\ge0} f : 2 X → R ≥ 0 be a monotone submodular function accessible through value queries, and let k ≥ 1 k \ge1 k ≥ 1 be an integer cardinality bound. Elements x 1 , … , x n ∈ X x_1,\ldots,x_n \in X x 1 , … , x n ∈ X arrive one at a time, and the algorithm knows the entire arrival sequence in advance. After the t t t -th arrival, the algorithm must maintain a solution A L G t ⊆ X t \mathrm{ALG}_t \subseteq X_t ALG t ⊆ X t , where X t = { x 1 , … , x t } X_t = \{x_1,\ldots,x_t\} X t = { x 1 , … , x t } , satisfying ∣ A L G t ∣ ≤ k |\mathrm{ALG}_t| \le k ∣ ALG t ∣ ≤ k for every realization of its randomness. We set A L G 0 = ∅ \mathrm{ALG}_0 = \varnothing ALG 0 = ∅ and let O P T t \mathrm{OPT}_t OPT t denote a set maximizing f ( S ) f(S) f ( S ) over all S ⊆ X t S \subseteq X_t S ⊆ X t with ∣ S ∣ ≤ k |S| \le k ∣ S ∣ ≤ k . Computation and the number of value queries are unrestricted, and queries may involve elements that have not yet arrived.
We evaluate a possibly randomized algorithm according to two guarantees:
Approximation. For α ≤ 1 \alpha\le1 α ≤ 1 , an algorithm is an α \alpha α -approximation if, on every instance and at every time t t t , E [ f ( A L G t ) ] ≥ α f ( O P T t ) \mathbb{E}[f(\mathrm{ALG}_t)] \ge\alpha f(\mathrm{OPT}_t) E [ f ( ALG t )] ≥ α f ( OPT t ) . The expectation is over the algorithm’s internal randomness, with the instance and time t t t fixed; the guarantee need not hold simultaneously at all times for a single realization. For deterministic algorithms, we use f ( A L G t ) f(\mathrm{ALG}_t) f ( ALG t ) instead of E [ f ( A L G t ) ] \mathbb{E}[f(\mathrm{ALG}_t)] E [ f ( ALG t )] .
Consistency. An algorithm is C C C -consistent if, on every instance and for every realization of its randomness, ∣ A L G t △ A L G t − 1 ∣ ≤ C |\mathrm{ALG}_t \mathbin{\triangle} \mathrm{ALG}_{t-1}| \le C ∣ ALG t △ ALG t − 1 ∣ ≤ C for all t = 1 , … , n t = 1,\ldots,n t = 1 , … , n . Here △ \triangle △ denotes the symmetric difference.1 An algorithm is consistent if it is C C C -consistent for some constant C C C independent of the input instance, including k k k and n n n . For algorithms parameterized by an accuracy ε > 0 \varepsilon> 0 ε > 0 , the constant C C C may depend on ε \varepsilon ε .
We allow arbitrary constant recourse budgets to identify approximation barriers that persist for every fixed number of changes permitted per arrival.
Apart from the algorithm’s knowledge of the arrival sequence, this is the model of consistent submodular maximization introduced by Dütting et al. [ [19 ] and further studied by Dütting et al. [ [20 ] and Fu et al. [ [28 ] , in which each element is revealed only upon arrival.2 We refer to their setting as non-clairvoyant and to ours as clairvoyant .
Results and Techniques
We establish tight information-theoretic bounds for consistent clairvoyant algorithms, both deterministic and randomized.
For randomized algorithms we show:
Main Result 1 (Tight randomized bound; see Thm. 1 & Thm. 2). For every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , there is a randomized clairvoyant algorithm for monotone submodular maximization under a cardinality constraint that is O ( ε − 2 ) O(\varepsilon^{-2}) O ( ε − 2 ) -consistent and achieves a ( ξ ⋆ − ε ) (\xi^\star-\varepsilon) ( ξ ⋆ − ε ) -approximation, where ξ ⋆ ≈ 0.7942 \xi^\star\approx0.7942 ξ ⋆ ≈ 0.7942 .‡ No consistent randomized clairvoyant algorithm can achieve an approximation ratio greater than ξ ⋆ \xi^\star ξ ⋆ , even for coverage functions.
For this result, we handle transitions through the addition-robustness framework of Dütting et al. [ [20 ] . The algorithm periodically samples a new set of elements that have already arrived and transitions to it at a random time, so that any fixed time is rarely affected. This framework reduces the problem to constructing an addition-robust distribution , whose samples stay competitive in expectation as new elements arrive.
Foresight changes the nature of this task: the upcoming arrivals are known, but a single distribution must still be good at all times. Via minimax duality, as in the non-clairvoyant setting, it suffices to compare a single solution, fixed in advance, with the best choice in hindsight when the evaluation time is random. Our key insight is that, because the future arrival prefixes form a known nested sequence, this question can be cast as an interval-selection problem , quite different from the correlation-gap question that arises without foresight [20 ] .
We solve this problem exactly. The crux is to show that the worst case consists of only three consecutive intervals, corresponding to just two future insertions; optimizing over such instances yields ξ ⋆ \xi^\star ξ ⋆ . The same analysis yields both bounds at once: every instance admits a robust distribution that is ξ ⋆ \xi^\star ξ ⋆ -competitive, and the worst case translates directly into a family of coverage instances that rules out a better approximation ratio for consistent algorithms.
For deterministic algorithms we show:
Main Result 2 (Tight deterministic bound; see Thm. 3 & Thm. 4). For every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , there is a deterministic clairvoyant algorithm for monotone submodular maximization under a cardinality constraint that is O ( ε − 3 log ( 1 / ε ) ) O(\varepsilon^{-3}\log(1/\varepsilon)) O ( ε − 3 log ( 1/ ε )) -consistent and achieves a ( 3 / 4 − ε ) (3/4-\varepsilon) ( 3/4 − ε ) -approximation. No consistent deterministic clairvoyant algorithm can achieve an approximation ratio greater than 3 / 4 3/4 3/4 , even for coverage functions.
The randomized construction places transitions at random times, so that any fixed time is affected by a transition only with small probability. A deterministic algorithm must maintain its approximation guarantee throughout each transition. A simple coverage construction makes this obstacle concrete: the algorithm is forced to move gradually from the rows of a k × k k \times k k × k grid to increasingly valuable columns. Halfway through, its k / 2 k/2 k /2 rows and k / 2 k/2 k /2 columns cover only 3 / 4 3/4 3/4 of the grid, while the optimal solution covers all of it.
Obtaining the matching algorithmic guarantee requires a way to construct safe transitions. We introduce a framework of clairvoyant certificates , which combines a fractional solution that remains valuable throughout a window of arrivals with a transition path of controlled complexity connecting the initial and final optimizers through that solution. The entry and exit portions satisfy the required value guarantees under the initial and final objectives, respectively. A certificate thus balances preparing for future arrivals against protecting the current solution. The main technical contribution is a reduction that rounds the entire transition path simultaneously, preserving the required value guarantees while controlling the number of changes. The rounding argument establishes the existence of a single realization satisfying all requirements, which can be found deterministically by exhaustive search. Scheduling the resulting changes then yields a consistent algorithm with an arbitrarily small loss in approximation.
This framework reduces the algorithmic problem to establishing the existence of suitable fractional certificates. We give an elementary construction at level 1 / 2 > 1 − 1 / e 1/\sqrt{2} > 1 - 1/e 1/ 2 > 1 − 1/ e that illustrates the framework, and prove in Lean that every window admits a certificate at the sharp level 3 / 4 3/4 3/4 , yielding the optimal deterministic guarantee.
Discussion
Discussion. Even with full foresight and unrestricted computation, constant recourse imposes a strict approximation loss. Our results quantify this loss exactly and show that randomization remains beneficial in the absence of uncertainty about future arrivals. Figure 1 compares our thresholds with those for non-clairvoyant algorithms: foresight raises the deterministic threshold from at most 1 / 2 1/2 1/2 [19 ] to 3 / 4 3/4 3/4 , and the randomized threshold from 2 / 3 2/3 2/3 to ξ ⋆ \xi^\star ξ ⋆ for submodular functions and from 3 / 4 3/4 3/4 to ξ ⋆ \xi^\star ξ ⋆ for coverage functions [20 ] . Without foresight, randomized algorithms do better on coverage functions than on general submodular functions; with foresight, the two classes have the same thresholds.
Figure 1. Overview of results. A single value is a tight threshold; an interval gives the best known lower and upper bounds. Poly time refers to algorithms that make polynomially many value queries and run in polynomial time, and info-theoretic to algorithms with unrestricted computation. The upper bound of 1 − 1 / e 1-1/e 1 − 1/ e in polynomial time holds even without consistency constraints [39 , 23 ] .
Open Problems
Open Problems. Both of our thresholds exceed 1 − 1 / e 1 - 1/e 1 − 1/ e , the best ratio achievable efficiently even without stability constraints [39 , 23 ] . Can efficient clairvoyant algorithms with constant recourse approach 1 − 1 / e 1 - 1/e 1 − 1/ e , so that stability costs nothing beyond computation? This would require exploiting foresight: without it, deterministic algorithms cannot exceed 1 / 2 1/2 1/2 [19 ] , and efficient randomized algorithms cannot exceed 2 − 2 2 - \sqrt{2} 2 − 2 [28 ] . The information-theoretic threshold for deterministic non-clairvoyant algorithms also remains open, between 0.3818 and 1/2 [19 ] . More broadly, it would be interesting to determine the cost of stability for the other problems and constraints studied with recourse.
Related Work
Consistent Submodular Maximization. In the non-clairvoyant setting, Dütting et al. [2024] gave a deterministic ( 0.3818 − ε ) (0.3818-\varepsilon) ( 0.3818 − ε ) -approximation with constant recourse and showed that no consistent deterministic algorithm can exceed 1 / 2 1/2 1/2 . Dütting et al. [2025] introduced addition robustness and a randomized checkpointing reduction, and determined the information-theoretic thresholds for randomized algorithms: 2 / 3 2/3 2/3 for monotone submodular functions and 3 / 4 3/4 3/4 for coverage functions. Fu et al. [2026] showed that 2 − 2 2-\sqrt{2} 2 − 2 is the best ratio achievable with polynomially many value queries. Dütting et al. [2026] studied consistency in the fully dynamic setting, with both insertions and deletions. A different notion of stability underlies the submodular objectives chasing problem of Buchbinder et al. [2025], in which both the objective and the ground set change over time: their algorithms maintain a ( 1 − 1 / e − ε ) (1-1/e-\varepsilon) ( 1 − 1/ e − ε ) -approximation while keeping the total recourse competitive with that of exact offline algorithms. In contrast, we bound the recourse of every step by a constant.
Incremental and Multistage Optimization. Several models study how solutions evolve when the input is known in advance. In incremental maximization, the solutions for increasing budgets must be nested, and each must be competitive for its own budget [8 , 16 ] ; for submodular functions under increasing cardinality constraints, the greedy algorithm achieves 1 − 1 / e 1-1/e 1 − 1/ e , and Bienkowski et al. [2026] recently improved on it. In incremental-decremental maximization, an initial solution is transformed one element at a time, and the order must keep every intermediate stage competitive with the optimum for that stage [17 ] . In multistage optimization, a sequence of instances is given, and the quality of each stage’s solution is traded off against the cost of changing it, or the changes between consecutive stages are bounded [30 , 22 , 1 , 5 , 27 ] . In our model, by contrast, the cardinality is fixed while the ground set grows, every solution must approximate the current optimum, and only a constant number of elements may change per arrival.
Streaming, Preemptive, and Dynamic Submodular Maximization. Streaming submodular maximization [13 , 2 , 25 ] focuses on bounding working memory ( O ( k log k / ε ) (O(k \log k/\varepsilon) ( O ( k log k / ε ) for a ( 1 / 2 − ε ) (1/2-\varepsilon) ( 1/2 − ε ) -approximation) rather than solution stability. Buchbinder et al. [2019], Chan et al. [2018] study online submodular maximization under cardinality constraints with preemption but no recall. Fully dynamic submodular maximization under insertions and deletions [35 , 37 , 15 , 18 , 6 ] optimizes query update time; however, dynamic algorithms can achieve polylogarithmic expected amortized update time while still incurring Ω ( k ) \Omega(k) Ω ( k ) worst-case recourse during rebuild steps.
Online Algorithms with Bounded Recourse. Maintaining solutions with bounded recourse has been widely studied for combinatorial problems including Steiner trees [32 ] , set cover [31 ] , k k k -clustering [34 , 26 ] , and matching [7 ] . Studying clairvoyant (offline dynamic) counterparts of online recourse problems separates the intrinsic cost of smooth transitions from online uncertainty; our results show that for submodular maximization, step-by-step consistency imposes a fundamental approximation barrier even under full foresight.
The Tight Randomized Bound
The optimal approximation ratio for randomized clairvoyant algorithms with a consistency bound independent of the cardinality constraint is ξ ⋆ ≈ 0.794 \xi^\star\approx0.794 ξ ⋆ ≈ 0.794 for both coverage and monotone submodular functions, where ξ ⋆ \xi^\star ξ ⋆ is the unique4 root in ( 1 / 2 , 1 ) (1/2,1) ( 1/2 , 1 ) of the polynomial
Ψ ( ξ ) = 89 ξ 4 − 44 ξ 3 − 19 ξ 2 − 3 ξ + 1. \Psi(\xi) = 89\xi^4 - 44\xi^3 - 19\xi^2 - 3\xi+ 1. Ψ ( ξ ) = 89 ξ 4 − 44 ξ 3 − 19 ξ 2 − 3 ξ + 1.
We give the impossibility result in § 4.1 using a simple hard instance, then obtain a matching algorithmic guarantee in § 4.2 –§ 4.5 by showing that this instance is a worst-case instance. The proofs for this section are deferred to Appendix § 8 .
The Impossibility Result for Randomized Algorithms
Quite surprisingly, there is a very simple hard-instance construction based on only two insertions which yields this impossibility result for possibly randomized consistent algorithms. Moreover, the instance is based on a coverage function, thus showing—together with the matching algorithm—that there is no separation between coverage and monotone submodular functions. We state the result and provide a proof sketch, while the details can be found in Section A.2.
Theorem 1. For any ε ∈ [ 1 / k , 1 ] \varepsilon\in[1/k,1] ε ∈ [ 1/ k , 1 ] , no randomized ε k \varepsilon k ε k -consistent clairvoyant algorithm can achieve an approximation ratio better than ξ ⋆ + O ( ε ) ≈ 0.7942 + O ( ε ) \xi^\star+ O(\varepsilon) \approx0.7942 + O(\varepsilon) ξ ⋆ + O ( ε ) ≈ 0.7942 + O ( ε ) for Maximum Coverage subject to a cardinality constraint k k k .
Proof sketch. We describe a weighted coverage instance on which every randomized ε k \varepsilon k ε k -consistent clairvoyant algorithm has approximation ratio at most ξ ⋆ + O ( ε ) \xi^\star+ O(\varepsilon) ξ ⋆ + O ( ε ) . Appendix § 8 .§ 4 converts it to an unweighted instance. Partition a universe U U U of 3 k 3k 3 k elements into groups U 0 U_0 U 0 , U 1 U_1 U 1 , U 2 U_2 U 2 of k k k elements each, with respective element weights 1 > u 1 > u 2 > 0 1 > u_1 > u_2 > 0 1 > u 1 > u 2 > 0 . The arrival sequence consists of the 3 k 3k 3 k singleton subsets of U U U , followed by the two large sets U 0 U_0 U 0 and U 1 U_1 U 1 , in that order. Thus the sequence contains 3 k + 2 3k+2 3 k + 2 sets; the singleton sets may arrive in any order. Figure 2 illustrates the construction.
Figure 2. The hard coverage instance for the randomized lower bound.
Relabel the last three time steps as 0, 1, and 2: immediately before U 0 U_0 U 0 arrives, immediately after U 0 U_0 U 0 arrives, and immediately after U 1 U_1 U 1 arrives. Let k i k_i k i be the expected number of singleton sets from U i U_i U i in the algorithm’s solution at time 0. These counts suffice to bound the algorithm’s expected value at all three time steps: we include each large set in the algorithm’s solution as soon as it arrives, without counting it toward the cardinality constraint, and consistency limits the algorithm to at most ε k \varepsilon k ε k additional singleton sets per insertion. Since every singleton has weight at most 1, these additions contribute only O ( ε k ) O(\varepsilon k) O ( ε k ) to its value.
In this sketch, we omit the O ( ε k ) O(\varepsilon k) O ( ε k ) contribution of these additional singleton sets to the value of the solutions of the algorithm and assume the large sets also do not count toward the cardinality constraint for the optimal solutions. With these simplifications, the algorithm’s expected values at time steps 0, 1, and 2 are at most k 0 + u 1 k 1 + u 2 k 2 k_0 + u_1k_1 + u_2k_2 k 0 + u 1 k 1 + u 2 k 2 , k + u 1 k 1 + u 2 k 2 k + u_1k_1 + u_2k_2 k + u 1 k 1 + u 2 k 2 , and k ( 1 + u 1 ) + u 2 k 2 k(1 + u_1) + u_2k_2 k ( 1 + u 1 ) + u 2 k 2 . The corresponding optimal values are k k k , k ( 1 + u 1 ) k(1 + u_1) k ( 1 + u 1 ) , and k ( 1 + u 1 + u 2 ) k(1 + u_1 + u_2) k ( 1 + u 1 + u 2 ) . We can thus bound the optimal approximation ratio with the following LP.
Maximize ρ subject to k 0 + k 1 + k 2 ≤ k , k 0 + u 1 k 1 + u 2 k 2 ≥ ρ ⋅ k , k + u 1 k 1 + u 2 k 2 ≥ ρ ( 1 + u 1 ) ⋅ k , k ( 1 + u 1 ) + u 2 k 2 ≥ ρ ( 1 + u 1 + u 2 ) ⋅ k , k i ≥ 0 for i = 0 , 1 , 2. \begin{aligned}
\text{Maximize}\quad& \rho\\
\text{subject to}\quad& k_0 + k_1 + k_2 \le k, \\
& k_0 + u_1k_1 + u_2k_2 \ge\rho\cdot k, \\
& k + u_1k_1 + u_2k_2 \ge\rho(1 + u_1) \cdot k, \\
& k(1 + u_1) + u_2k_2 \ge\rho(1 + u_1 + u_2) \cdot k, \\
& k_i \ge0 \quad\text{for } i = 0,1,2.
\end{aligned} Maximize subject to ρ k 0 + k 1 + k 2 ≤ k , k 0 + u 1 k 1 + u 2 k 2 ≥ ρ ⋅ k , k + u 1 k 1 + u 2 k 2 ≥ ρ ( 1 + u 1 ) ⋅ k , k ( 1 + u 1 ) + u 2 k 2 ≥ ρ ( 1 + u 1 + u 2 ) ⋅ k , k i ≥ 0 for i = 0 , 1 , 2.
To bound the optimal value of this program, we take a convex combination of its three approximation constraints with weights u 2 u_2 u 2 , u 2 u 1 − u 2 \frac{u_2}{u_1} - u_2 u 1 u 2 − u 2 , and 1 − u 2 u 1 1 - \frac{u_2}{u_1} 1 − u 1 u 2 and obtain
ρ ≤ 1 + u 1 − u 2 ( 1 + u 1 + u 2 − u 1 u 2 − u 2 2 u 1 ) . \rho\le\frac{1 + u_1 - u_2}{\left(1 + u_1 + u_2 - u_1u_2 - \frac{u_2^2}{u_1}\right)}. ρ ≤ ( 1 + u 1 + u 2 − u 1 u 2 − u 1 u 2 2 ) 1 + u 1 − u 2 .
To minimize this bound on ρ \rho ρ , we choose u 1 u_1 u 1 as the unique root in ( 0 , 1 ) (0,1) ( 0 , 1 ) of the polynomial Φ ( x ) = x 4 + x 3 − 2 x 2 − 3 x + 2 \Phi(x) = x^4 + x^3 - 2x^2 - 3x + 2 Φ ( x ) = x 4 + x 3 − 2 x 2 − 3 x + 2 and set u 2 = u 1 2 ( 1 + u 1 ) u_2 = u_1^2(1 + u_1) u 2 = u 1 2 ( 1 + u 1 ) , which makes the bound equal to 1 / ( 1 + u 1 u 2 ) = ξ ⋆ 1/(1 + u_1u_2) = \xi^\star 1/ ( 1 + u 1 u 2 ) = ξ ⋆ .
Overview of the Randomized Algorithm
In this section, we present the randomized algorithm that achieves the tight ξ ⋆ \xi^\star ξ ⋆ approximation. The result follows from a chain of reductions, summarized in Figure 3 . As a first step, in § 4.3 , we introduce the notion of clairvoyant addition-robust algorithms, building on the non-clairvoyant notion introduced by Dütting et al. [ [20 ] . Using a similar checkpoint-based construction, we show that finding a solution robust to prefixes of the known arrival sequence suffices to obtain consistent algorithms with a comparable approximation guarantee. Minimax duality applied to the linear program induced by addition-robustness then reformulates the task: instead of finding a single randomized solution that performs well at every prefix, it suffices to find, for each fixed distribution over prefixes, a deterministic solution that performs well in expectation.
Figure 3. Proof roadmap for the randomized algorithm.
Our main technical contribution in this section is to connect this minimax problem to an interval selection problem and give a tight analysis of it. In this formulation, each interval corresponds to a prefix of the arrival sequence: its left endpoint is the value of that prefix, and its length is the maximum marginal contribution of a feasible solution to that prefix. In § 4.5 , we then reduce the general interval selection problem to instances with consecutive intervals of nonincreasing lengths. Finally, we pinpoint the exact approximation guarantee ξ ⋆ \xi^\star ξ ⋆ by explicitly solving the interval selection problem for this restricted family, whose worst-case instance consists of only three intervals and corresponds to the hard coverage instance from Theorem 1.
Theorem 2. For every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , there is a randomized clairvoyant algorithm for monotone submodular maximization under a cardinality constraint k k k that is O ( 1 / ε 2 ) O(1/\varepsilon^2) O ( 1/ ε 2 ) -consistent and achieves a ( ξ ⋆ − ε ) (\xi^\star-\varepsilon) ( ξ ⋆ − ε ) -approximation.
The Clairvoyant Addition-Robust Problem
In clairvoyant addition-robust submodular maximization , we are given a monotone submodular function f f f , a partition of the ground set into present elements V n o w V_{\mathrm{now}} V now and future elements V f u t u r e = ( v 1 , … , v m ) V_{\mathrm{future}}=(v_1,\ldots,v_m) V future = ( v 1 , … , v m ) whose arrival order is given in advance, and a cardinality budget κ \kappa κ . Write R j = { v 1 , … , v j } R_j=\{v_1,\ldots,v_j\} R j = { v 1 , … , v j } , with R 0 = ∅ R_0=\varnothing R 0 = ∅ , and let
O j ∈ arg max O ⊆ V n o w ∣ O ∣ ≤ κ f ( O ∪ R j ) . O_j \in\arg\max_{\substack{O\subseteq V_{\mathrm{now}}\\ |O|\leq\kappa}} f(O\cup R_j). O j ∈ arg O ⊆ V now ∣ O ∣ ≤ κ max f ( O ∪ R j ) .
The goal is to find a (possibly randomized) set S ⊆ V n o w S\subseteq V_{\mathrm{now}} S ⊆ V now of cardinality at most κ \kappa κ which is “robust” with respect to the insertion of all possible prefixes of V f u t u r e V_{\mathrm{future}} V future , i.e., such that the value of S ∪ R j S\cup R_j S ∪ R j is a good approximation of that of O j ∪ R j O_j\cup R_j O j ∪ R j , for all j j j at the same time.
Definition 2.1 (Clairvoyant Addition Robustness). In the clairvoyant setting, a possibly randomized set S ⊆ V n o w S\subseteq V_{\mathrm{now}} S ⊆ V now is α \alpha α -addition-robust if
E [ f ( S ∪ R j ) ] ≥ α f ( O j ∪ R j ) ∀ j = 0 , … , m . \mathbb{E}[f(S\cup R_j)]\geq\alpha f(O_j\cup R_j)\qquad\forall j=0,\ldots,m. E [ f ( S ∪ R j )] ≥ α f ( O j ∪ R j ) ∀ j = 0 , … , m . We call such a distribution α \alpha α -addition-robust.
The algorithm knows V f u t u r e V_{\mathrm{future}} V future , so it can compute up front all sets O i O_i O i , which are best responses to the corresponding prefixes R i R_i R i . In the consistent problem, however, it cannot move freely from one O i O_i O i to O i + 1 O_{i+1} O i + 1 . The addition-robust algorithm therefore commits, possibly in a randomized way, to one fixed set of present elements. We highlight that the difference with respect to the non-clairvoyant definition in Dütting et al. [ [20 ] lies in the fact that here the robustness is only with respect to known prefixes of the known sequence V f u t u r e V_{\mathrm{future}} V future of “future” elements, and not with respect to all possible unknown futures. The benchmark f ( O i ∪ R i ) f(O_i\cup R_i) f ( O i ∪ R i ) upper-bounds the optimum attainable from V n o w ∪ R i V_{\mathrm{now}}\cup R_i V now ∪ R i with at most κ \kappa κ elements. The following reduction converts addition robustness into a consistent algorithm.
Lemma 1. Suppose that, for every instance of the clairvoyant addition-robust problem, an algorithm returns an α \alpha α -addition-robust distribution, where 0 ≤ α ≤ 1 0\leq\alpha\leq1 0 ≤ α ≤ 1 . For every γ ∈ ( 0 , 1 / 8 ) \gamma\in(0,1/8) γ ∈ ( 0 , 1/8 ) , this yields a randomized clairvoyant O ( γ − 2 ) O(\gamma^{-2}) O ( γ − 2 ) -consistent algorithm that achieves an ( α − 3 γ ) (\alpha-3\gamma) ( α − 3 γ ) -approximation.
The structure of the reduction is similar to the one in Dütting et al. [ [20 ] . It relies on a partition of the arrivals into contiguous blocks of γ κ \gamma\kappa γ κ elements, interleaved by checkpoints. At each checkpoint, the algorithm computes an addition-robust solution using as V n o w V_{\mathrm{now}} V now the elements that have arrived so far, and as V f u t u r e V_{\mathrm{future}} V future all the elements in the following two blocks. Then the algorithm selects uniformly at random a subblock of size γ 2 κ \gamma^2\kappa γ 2 κ where it transitions from the addition-robust solution inherited from the previous checkpoint to the solution computed at the current checkpoint. Robustness guarantees that the approximation factor is maintained throughout each block, while the random choice of the transition subblock ensures that, at each time step, the probability of hosting a transition is at most γ \gamma γ . Consistency is ensured because we use γ 2 κ \gamma^2\kappa γ 2 κ time steps to transition from one solution to the other maintaining O ( γ − 2 ) O(\gamma^{-2}) O ( γ − 2 ) consistency. For more details on the checkpoint algorithm and the proof of Lemma 1, we refer to Section A.3.
The addition-robustness LP. To obtain the desired guarantee, it suffices to consider distributions supported on O 0 , … , O m O_0,\ldots,O_m O 0 , … , O m . The best such distribution is given by the following LP, which generalizes the LP in the analysis of the hard instance for Theorem 1.
Maximize ρ subject to ∑ i = 0 m α i f ( O i ∪ R j ) ≥ ρ f ( O j ∪ R j ) for j = 0 , … , m , ∑ i = 0 m α i = 1 , α i ≥ 0 for i = 0 , … , m , 0 ≤ ρ ≤ 1. (1) \begin{aligned}
\text{Maximize}\quad& \rho\\
\text{subject to}\quad& \sum_{i=0}^{m}\alpha_i f(O_i\cup R_j)\geq\rho f(O_j\cup R_j) && \text{for }j=0,\ldots,m,\\
& \sum_{i=0}^{m}\alpha_i=1,\quad\alpha_i\geq0 && \text{for }i=0,\ldots,m,\quad0\leq\rho\leq1. \tag*{(1)}
\end{aligned} Maximize subject to ρ i = 0 ∑ m α i f ( O i ∪ R j ) ≥ ρ f ( O j ∪ R j ) i = 0 ∑ m α i = 1 , α i ≥ 0 for j = 0 , … , m , for i = 0 , … , m , 0 ≤ ρ ≤ 1. (1)
For the normalized formulation below, assume κ ≥ 1 \kappa\geq1 κ ≥ 1 and f ( O 0 ) > 0 f(O_0)>0 f ( O 0 ) > 0 . Optimality and monotonicity then give f ( O j ∪ R j ) ≥ f ( O 0 ) > 0 f(O_j\cup R_j)\geq f(O_0)>0 f ( O j ∪ R j ) ≥ f ( O 0 ) > 0 for every j j j . Let Δ \Delta Δ denote the simplex of probability distributions over { 0 , … , m } \{0,\ldots,m\} { 0 , … , m } . Writing ρ ⋆ \rho^\star ρ ⋆ for the value of the linear program (1), we have
ρ ⋆ = max α ∈ Δ min j = 0 , … , m ∑ i = 0 m α i ⋅ f ( O i ∪ R j ) f ( O j ∪ R j ) . \rho^\star=\max_{\alpha\in\Delta}\min_{j=0,\ldots,m}\sum_{i=0}^{m}\alpha_i\cdot\frac{f(O_i\cup R_j)}{f(O_j\cup R_j)}. ρ ⋆ = α ∈ Δ max j = 0 , … , m min i = 0 ∑ m α i ⋅ f ( O j ∪ R j ) f ( O i ∪ R j ) .
This program can be interpreted as a game between the algorithm which picks a distribution over sets O i O_i O i , knowing that there is an adversary which is going to select the prefix R j R_j R j for which the expected normalized value of the randomized solution is worst. By finite minimax duality, we may reverse the order of play: the adversary first commits to a distribution β ∈ Δ \beta\in\Delta β ∈ Δ over prefixes, and the algorithm then chooses a deterministic solution O i O_i O i maximizing its expected normalized value:
ρ ⋆ = min β ∈ Δ max i = 0 , … , m ∑ j = 0 m β j ⋅ f ( O i ∪ R j ) f ( O j ∪ R j ) . \rho^\star=\min_{\beta\in\Delta}\max_{i=0,\ldots,m}\sum_{j=0}^{m}\beta_j\cdot\frac{f(O_i\cup R_j)}{f(O_j\cup R_j)}. ρ ⋆ = β ∈ Δ min i = 0 , … , m max j = 0 ∑ m β j ⋅ f ( O j ∪ R j ) f ( O i ∪ R j ) .
The Interval Selection Problem
There is a geometric interpretation of the minimax formulation for ρ ⋆ \rho^\star ρ ⋆ in terms of an interval selection problem. In this problem, given a distribution over intervals, an interval is selected before the realized interval is drawn. If interval [ ℓ i , r i ] [\ell_i,r_i] [ ℓ i , r i ] is chosen and interval [ ℓ j , r j ] [\ell_j,r_j] [ ℓ j , r j ] is realized, the value is v ( i , j ) = ℓ j + ∣ [ ℓ i , r i ] ∩ [ ℓ j , ∞ ) ∣ v(i,j)=\ell_j+\lvert[\ell_i,r_i]\cap[\ell_j,\infty)\rvert v ( i , j ) = ℓ j + ∣[ ℓ i , r i ] ∩ [ ℓ j , ∞ )∣ , the sum of the left endpoint of [ ℓ j , r j ] [\ell_j,r_j] [ ℓ j , r j ] and the length of [ ℓ i , r i ] [\ell_i,r_i] [ ℓ i , r i ] that extends to the right of ℓ j \ell_j ℓ j .
Definition 2.2. Let [ ℓ 0 , r 0 ] , … , [ ℓ N , r N ] [\ell_0,r_0],\ldots,[\ell_N,r_N] [ ℓ 0 , r 0 ] , … , [ ℓ N , r N ] be intervals with 0 ≤ ℓ i ≤ r i 0\leq\ell_i\leq r_i 0 ≤ ℓ i ≤ r i , and let p = ( p 0 , … , p N ) p=(p_0,\ldots,p_N) p = ( p 0 , … , p N ) be a probability distribution over their indices. The adaptivity gap of the interval-selection problem is
Γ ( ℓ , r , p ) = max i = 0 , … , N E j ∼ p [ v ( i , j ) ] E j ∼ p [ max i = 0 , … , N v ( i , j ) ] . \Gamma(\ell,r,p)=\frac{\max_{i=0,\ldots,N}\mathbb{E}_{j\sim p}[v(i,j)]}{\mathbb{E}_{j\sim p}\left[\max_{i=0,\ldots,N}v(i,j)\right]}. Γ ( ℓ , r , p ) = E j ∼ p [ max i = 0 , … , N v ( i , j ) ] max i = 0 , … , N E j ∼ p [ v ( i , j )] . The numerator is the best expected value of a fixed interval; the denominator allows the choice to depend on the realized interval. In the reduction from clairvoyant addition-robustness, each interval corresponds to a prefix of the future elements; its left endpoint ℓ i = f ( R i ) \ell_i=f(R_i) ℓ i = f ( R i ) is the value of the prefix alone, while its right endpoint r i = f ( O i ∪ R i ) r_i=f(O_i\cup R_i) r i = f ( O i ∪ R i ) is the addition-robustness benchmark at
prefix R i R_i R i . Selecting interval i i i corresponds to committing to O i O_i O i , and realization j j j corresponds to evaluating this choice against prefix R j R_j R j . The interval value v ( i , j ) v(i,j) v ( i , j ) then lower-bounds f ( O i ∪ R j ) f(O_i\cup R_j) f ( O i ∪ R j ) , the value of this set of present elements together with the realized prefix.
The interval distribution p p p is obtained from the minimax distribution β \beta β by reweighting each probability β j \beta_j β j by 1 / r j 1/r_j 1/ r j and normalizing. An adaptivity-gap bound that holds for every distribution p p p can therefore be converted, through minimax duality, into one randomized choice of a set of present elements that performs well against every future prefix simultaneously. The following lemma makes this connection precise.
Lemma 2. Let α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] . If Γ ( ℓ , r , p ) ≥ α \Gamma(\ell,r,p)\ge\alpha Γ ( ℓ , r , p ) ≥ α for every interval-selection instance, then every instance of clairvoyant addition-robust submodular maximization admits an α \alpha α -addition-robust distribution.
It remains to bound the adaptivity gap of the interval selection problem.
The Hard Structure for Interval Selection
We establish the adaptivity gap of the interval selection problem through a lossless reduction to the family of nonincreasing consecutive intervals with the equalizing distribution, for which we establish an adaptivity gap of ξ ∗ \xi^* ξ ∗ .
Definition 2.3. An instance ( ℓ , r , p ) (\ell,r,p) ( ℓ , r , p ) has nonincreasing consecutive intervals if ℓ 0 = 0 \ell_0=0 ℓ 0 = 0 , ℓ i + 1 = r i \ell_{i+1}=r_i ℓ i + 1 = r i for i < N i<N i < N , and r 0 − ℓ 0 ≥ ⋯ ≥ r N − ℓ N > 0 r_0-\ell_0\ge\cdots\ge r_N-\ell_N>0 r 0 − ℓ 0 ≥ ⋯ ≥ r N − ℓ N > 0 . Its distribution p p p is equalizing if every fixed interval i i i has the same expected value E j ∼ p [ v ( i , j ) ] \mathbb{E}_{j\sim p}[v(i,j)] E j ∼ p [ v ( i , j )] .
Appendix A.5 derives the unique equalizing distribution for these intervals. We show that restricting our attention to this structured family is without loss.
Lemma 3. Let α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] . If Γ ( ℓ , r , p ) ≥ α \Gamma(\ell,r,p)\ge\alpha Γ ( ℓ , r , p ) ≥ α for every instance of nonincreasing consecutive intervals with the equalizing distribution, then Γ ( ℓ , r , p ) ≥ α \Gamma(\ell,r,p)\ge\alpha Γ ( ℓ , r , p ) ≥ α for every interval-selection instance.
The final step of the proof of our positive result for randomized algorithms establishes that the adaptivity gap of this family of instances is ξ ∗ \xi^* ξ ∗ .
Lemma 4. For every instance ( ℓ , r , p ) (\ell,r,p) ( ℓ , r , p ) of nonincreasing consecutive intervals with the equalizing distribution, Γ ( ℓ , r , p ) ≥ ξ ∗ \Gamma(\ell,r,p)\ge\xi^* Γ ( ℓ , r , p ) ≥ ξ ∗ . Equality holds for the three-interval instance [ ℓ 0 , r 0 ] = [ 0 , 1 ] [\ell_0,r_0]=[0,1] [ ℓ 0 , r 0 ] = [ 0 , 1 ] , [ ℓ 1 , r 1 ] = [ 1 , 1 + u 1 ] [\ell_1,r_1]=[1,1+u_1] [ ℓ 1 , r 1 ] = [ 1 , 1 + u 1 ] , and [ ℓ 2 , r 2 ] = [ 1 + u 1 , 1 + u 1 + u 2 ] [\ell_2,r_2]=[1+u_1,1+u_1+u_2] [ ℓ 2 , r 2 ] = [ 1 + u 1 , 1 + u 1 + u 2 ] with the equalizing distribution, where u 1 u_1 u 1 is the unique root in ( 0 , 1 ) (0,1) ( 0 , 1 ) of Φ ( x ) = x 4 + x 3 − 2 x 2 − 3 x + 2 \Phi(x)=x^4+x^3-2x^2-3x+2 Φ ( x ) = x 4 + x 3 − 2 x 2 − 3 x + 2 and u 2 = u 1 2 ( 1 + u 1 ) u_2=u_1^2(1+u_1) u 2 = u 1 2 ( 1 + u 1 ) .
The equality case in Lemma 4 is the interval representation of the hard coverage instance from Theorem 1, which is illustrated in Figure 4 . Combining this lemma with the reductions in Lemmas 1, 2, and 3 proves Theorem 2.
Figure 4. Interval representation of the hard coverage instance in Figure 2 , with values normalized by k k k . The future prefixes ∅ \varnothing ∅ , { U 0 } \{U_0\} { U 0 } , and { U 0 , U 1 } \{U_0,U_1\} { U 0 , U 1 } give the intervals I 0 = [ 0 , 1 ] I_0=[0,1] I 0 = [ 0 , 1 ] , I 1 = [ 1 , 1 + u 1 ] I_1=[1,1+u_1] I 1 = [ 1 , 1 + u 1 ] , and I 2 = [ 1 + u 1 , 1 + u 1 + u 2 ] I_2=[1+u_1,1+u_1+u_2] I 2 = [ 1 + u 1 , 1 + u 1 + u 2 ] , respectively. Their lengths 1 1 1 , u 1 u_1 u 1 , u 2 u_2 u 2 are the normalized gains from selecting all k k k singleton sets in the first, second, and third groups, respectively.
The Tight Deterministic Bound
We first give the rows-to-columns obstruction that limits deterministic algorithms to 3 / 4 3/4 3/4 . We then introduce clairvoyant certificates, which let us match this bound up to an arbitrarily small loss. The supporting proofs appear in Appendix § 9 .
Impossibility for Deterministic Algorithms
Theorem 3. For 1 / k ≤ ϵ ≤ 1 1/k \le\epsilon\le1 1/ k ≤ ϵ ≤ 1 , no deterministic ϵ k \epsilon k ϵ k -consistent clairvoyant algorithm can achieve an approximation ratio better than 3 / 4 + O ( ϵ ) 3/4 + O(\epsilon) 3/4 + O ( ϵ ) for Maximum Coverage subject to a uniform cardinality constraint k k k .
Proof sketch. We suppress O ( ϵ + 1 / k ) O(\epsilon+ 1/k) O ( ϵ + 1/ k ) losses in this sketch; Appendix § 9 .§ 1 accounts for them explicitly. Consider a k × k k \times k k × k grid U c o r e U_{\mathrm{core}} U core (k 2 k^2 k 2 elements) and an auxiliary pool U a u x U_{\mathrm{aux}} U aux (Figure 5 ). First, k k k disjoint row sets A = { a 1 , … , a k } A = \{a_1,\ldots,a_k\} A = { a 1 , … , a k } arrive, covering U c o r e U_{\mathrm{core}} U core row by row. Next, column sets arrive in stages B 1 , … , B ℓ B_1,\ldots,B_\ell B 1 , … , B ℓ for some ℓ ≫ k \ell\gg k ℓ ≫ k : in stage j j j , the k k k disjoint sets in B j B_j B j cover U c o r e U_{\mathrm{core}} U core column by column, and each column b i , j b_{i,j} b i , j also covers j j j auxiliary elements in U a u x U_{\mathrm{aux}} U aux . Therefore, each column b i , j b_{i,j} b i , j covers k + j k+j k + j elements, and the collection B j B_j B j of k k k columns in stage j j j covers k 2 + k j k^2+kj k 2 + k j elements.
Figure 5. Left: Consistency forces the row fraction α t \alpha_t α t to pass within ϵ \epsilon ϵ of 1 / 2 1/2 1/2 at some step t ∗ t^* t ∗ . Right: The idealized halfway state, with k / 2 k/2 k /2 rows and k / 2 k/2 k /2 columns, covers 3 / 4 3/4 3/4 of U c o r e U_{\mathrm{core}} U core and 1 / 2 1/2 1/2 of U a u x U_{\mathrm{aux}} U aux , while the complete stage B j B_j B j covers both completely.
Consider any deterministic 3 / 4 3/4 3/4 -approximation algorithm A \mathcal{A} A . Let α t ∈ [ 0 , 1 ] \alpha_t \in[0,1] α t ∈ [ 0 , 1 ] be the fraction of sets in A A A that A \mathcal{A} A selects at time t t t (Figure 5 , left). Right after A A A arrives, OPT covers U c o r e U_{\mathrm{core}} U core (k 2 k^2 k 2 elements), so A \mathcal{A} A starts with α t ≥ 3 / 4 \alpha_t \ge3/4 α t ≥ 3/4 . At the end of a stage j ≫ k j \gg k j ≫ k , the auxiliary bonus j j j dominates the core size k k k , so O P T = B j \mathrm{OPT}=B_j OPT = B j covers k 2 + k j ≈ k j k^2+kj \approx kj k 2 + k j ≈ k j elements and forces ALG to switch mostly to columns (α t ≤ 1 / 4 + O ( k / j ) \alpha_t \le1/4+O(k/j) α t ≤ 1/4 + O ( k / j ) ). Since ALG is deterministic and changes at most ϵ k \epsilon k ϵ k sets per step, α t \alpha_t α t changes by at most ϵ \epsilon ϵ per step and must cross a halfway state α t ∗ ≈ 1 / 2 \alpha_{t^*}\approx1/2 α t ∗ ≈ 1/2 during some stage B j B_j B j .
At step t ∗ t^* t ∗ , we may upper-bound the value of ALG by granting it k / 2 k/2 k /2 rows from A A A and k / 2 k/2 k /2 distinct columns from B j B_j B j , up to the suppressed losses. The preceding completed stage provides a benchmark of value at least ( 1 − O ( 1 / k ) ) f ( B j ) (1-O(1/k))f(B_j) ( 1 − O ( 1/ k )) f ( B j ) (Figure 5 , right). On U c o r e U_{\mathrm{core}} U core , the k / 2 k/2 k /2 rows and k / 2 k/2 k /2 columns overlap on one k / 2 × k / 2 k/2 \times k/2 k /2 × k /2 quadrant and miss the opposite quadrant, covering 3 / 4 k 2 3/4k^2 3/4 k 2 of k 2 k^2 k 2 elements. On U a u x U_{\mathrm{aux}} U aux , only the k / 2 k/2 k /2 selected columns contribute, covering 1 / 2 k j 1/2kj 1/2 k j of k j kj k j elements. Thus the halfway state gets 3 / 4 3/4 3/4 of the complete-stage benchmark on U c o r e U_{\mathrm{core}} U core and 1 / 2 1/2 1/2 on U a u x U_{\mathrm{aux}} U aux :
f ( A L G t ∗ ) f ( O P T t ∗ ) ≈ 3 4 k 2 + 1 2 k j k 2 + k j ≤ 3 4 . \frac{f(\mathrm{ALG}_{t^*})}{f(\mathrm{OPT}_{t^*})} \approx\frac{\frac{3}{4}k^2+\frac{1}{2}kj}{k^2+kj} \le\frac{3}{4}. f ( OPT t ∗ ) f ( ALG t ∗ ) ≈ k 2 + k j 4 3 k 2 + 2 1 k j ≤ 4 3 .
Framework for Deterministic Algorithms: Clairvoyant Certificates
An advantage of a randomized algorithm over a deterministic one is that it can “hide” the transition between two solutions by performing it at a random time, so that any fixed time step is affected only with small probability. This is the approach taken in Section 2. In contrast, for a deterministic algorithm, every intermediate solution is compared with the current optimum. Indeed, in the instance used in Theorem 3 and illustrated in Figure 5 , a consistent algorithm has to switch gradually from rows to columns, and halfway through the switch its solution covers only 3/4 of the grid (which is strictly less than what is achievable by a randomized algorithm). Our main result in this part is that this simple example is essentially the only obstacle: a deterministic algorithm can always maintain a 3/4-approximation while being O ( 1 ) O(1) O ( 1 ) -consistent, up to an arbitrarily small loss ε \varepsilon ε .
Theorem 4 (Deterministic guarantee). For every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , there is a deterministic clairvoyant algorithm for monotone submodular maximization under a cardinality constraint k k k that is O ( ε − 3 log ( 1 / ε ) ) O(\varepsilon^{-3}\log(1/\varepsilon)) O ( ε − 3 log ( 1/ ε )) -consistent and satisfies
f ( A L G t ) ≥ ( 3 / 4 − ε ) f ( O P T t ) at every time t . f(\mathrm{ALG}_t) \ge(3/4-\varepsilon)f(\mathrm{OPT}_t) \qquad\text{at every time }t. f ( ALG t ) ≥ ( 3/4 − ε ) f ( OPT t ) at every time t .
Like its randomized counterpart (Theorem 2), the result is information-theoretic: the algorithm computes exact optima and finds the solution via exhaustive search. The heart of the proof, and the main technical contribution of this section, is a reduction theorem (Theorem 5). It shows that a deterministic consistent algorithm exists as soon as a finite object, a clairvoyant certificate , exists for every instance of a problem on a single window of the stream, a problem in which consistency plays no role. What remains is to construct certificates: Theorem 6 gives a guarantee of 1 / 2 1/\sqrt{2} 1/ 2 by a short argument, and Theorem 7 gives the tight guarantee 3 / 4 3/4 3/4 , with a Lean proof available on GitHub [3 ] . We first introduce the two notions needed to state the reduction: window instances and mixtures.
Window instances. The algorithm processes the stream in windows of O ( ε k ) O(\varepsilon k) O ( ε k ) consecutive arrivals. Between transitions, it holds a fixed core S S S of about κ = ( 1 − O ( ε ) ) k \kappa=(1-O(\varepsilon))k κ = ( 1 − O ( ε )) k elements that were present at the start of the window, and it outputs S S S together with a buffer of recent arrivals. This buffer includes the arrivals of the current window and retains those needed from the preceding window until the transition finishes. Fix a window, let V n o w V_{\mathrm{now}} V now be the set of elements present at its start, V f u t u r e = ( v 1 , … , v m ) V_{\mathrm{future}}=(v_1,\ldots,v_m) V future = ( v 1 , … , v m ) its arrivals in order, and R j = { v 1 , … , v j } R_j=\{v_1,\ldots,v_j\} R j = { v 1 , … , v j } , with R 0 = ∅ R_0=\varnothing R 0 = ∅ . The best core in hindsight after j j j arrivals defines the benchmark at stage j j j ,
f ( O j ∪ R j ) , O j ∈ arg max O ⊆ V n o w , ∣ O ∣ ≤ κ f ( O ∪ R j ) . (2) f(O_j \cup R_j), \qquad O_j \in\underset{O \subseteq V_{\mathrm{now}},\,|O|\leq\kappa}{\arg\max}\ f(O \cup R_j). \tag*{(2)} f ( O j ∪ R j ) , O j ∈ O ⊆ V now , ∣ O ∣ ≤ κ arg max f ( O ∪ R j ) . (2)
It is at least ( 1 − O ( ε ) ) f ( O P T t ) (1-O(\varepsilon))f(\mathrm{OPT}_t) ( 1 − O ( ε )) f ( OPT t ) at the time t t t of the j j j -th arrival, so a core that is α \alpha α -competitive against it is an ( α − O ( ε ) ) (\alpha-O(\varepsilon)) ( α − O ( ε )) -approximation: dropping k − κ k-\kappa k − κ elements from O P T t \mathrm{OPT}_t OPT t loses at most a ( k − κ ) / k (k-\kappa)/k ( k − κ ) / k fraction of its value, and what remains inside V n o w V_{\mathrm{now}} V now is a feasible core. The tuple ( f , V n o w , V f u t u r e , κ ) (f,V_{\mathrm{now}},V_{\mathrm{future}},\kappa) ( f , V now , V future , κ ) , together with a choice of the sets O 0 , … , O m O_0,\ldots,O_m O 0 , … , O m , which we call the candidates , is a window instance with stages 0 , … , m 0,\ldots,m 0 , … , m ; it is exactly an instance of the clairvoyant addition-robust problem that Section 2.3 studies for randomized algorithms. The candidates are known in advance, but a consistent algorithm cannot jump between them; the question is which core to hold.
Mixtures. For randomized algorithms, a distribution over the candidates answers this question (this is the clairvoyant addition-robustness of Section 2.3): outputting O i O_i O i with probability p i p_i p i yields expected value ∑ i p i f ( O i ∪ R j ) \sum_i p_i f(O_i \cup R_j) ∑ i p i f ( O i ∪ R j ) at stage j j j , and by the reduction of Lemma 1 such a distribution is all that is needed. In contrast, a deterministic algorithm cannot sample. It has to hold a single set that blends the candidates, and since f f f is submodular, the value of a blend is governed by the “overlaps” of the candidates, not by the average of their values. It is instructive to see what happens on the grid of Theorem 3, which the rows and the columns each cover completely. Outputting the rows with probability 1 / 2 1/2 1/2 or the columns with probability 1 / 2 1/2 1/2 covers the whole grid either way. If instead every row and every column is picked independently with probability 1 / 2 1/2 1/2 , each cell is covered with probability 3 / 4 3/4 3/4 , so only 3 / 4 3/4 3/4 of the grid is covered in expectation; this is the value of the multilinear extension at the fractional point that puts weight 1 / 2 1/2 1/2 on each of the two candidates. We will work with the simpler quantity (3) below, which gives a lower bound on the multilinear extension: it draws the row candidate and the column candidate independently, each with probability 1 / 2 1/2 1/2 , and merges them; with probability 1 / 4 1/4 1/4 nothing is drawn, so this again covers 3 / 4 3/4 3/4 of the grid in expectation.
The clairvoyant-certificate framework handles this difficulty in a powerful and modular way. It charges for the overlaps once, in the value (3) it assigns to a blend, and Theorem 5 then turns a randomized-looking guarantee into a deterministic consistent algorithm with the same guarantee. As in the randomized case, designing the algorithm thereby amounts to proving expectation bounds on one window; the rounding, the timing of the transitions, and the accounting for consistency are handled by the general reduction theorem.
Concretely, a mixture is a probability vector p ∈ Δ p \in\Delta p ∈ Δ over the candidates, where Δ \Delta Δ is the simplex of distributions on { 0 , … , m } \{0,\ldots,m\} { 0 , … , m } , and its value at stage j j j is
H j ( p ) = E [ f ( R j ∪ ⋃ i ∈ I ( p ) O i ) ] , (3) H_j(p)=\mathbb{E}\left[f\left(R_j\cup\bigcup_{i\in I(p)}O_i\right)\right], \tag*{(3)} H j ( p ) = E f R j ∪ i ∈ I ( p ) ⋃ O i , (3)
where I ( p ) I(p) I ( p ) contains each index i i i independently with probability p i p_i p i . By submodularity, H j ( p ) H_j(p) H j ( p ) is at most the randomized value ∑ i p i ⋅ f ( R j ∪ O i ) \sum_i p_i\cdot f(R_j\cup O_i) ∑ i p i ⋅ f ( R j ∪ O i ) ; Appendix B.2.1 proves this comparison and the lower bound on the multilinear extension. On the other hand, one set of about κ \kappa κ elements can simultaneously attain these guarantees at every stage, up to an ε \varepsilon ε loss; this is the rounding step of the reduction. An advantage of the above definition over the multilinear extension is that it is much less sensitive to small changes in the probabilities. In particular, changing the probability p i p_i p i assigned to O i O_i O i by ε \varepsilon ε changes the function value by at most ε f ( O i ) \varepsilon f(O_i) ε f ( O i ) . For the multilinear extension, in contrast, the effect can be much larger. To see this, consider the submodular function f f f that satisfies f ( S ) = 1 f(S)=1 f ( S ) = 1 for every nonempty set S S S and f ( ∅ ) = 0 f(\emptyset)=0 f ( ∅ ) = 0 . If O i O_i O i has cardinality k k k , then increasing p i p_i p i from 0 0 0 to ε \varepsilon ε increases the multilinear-extension value from 0 0 0 to
1 − ( 1 − ε ) k , 1-(1-\varepsilon)^k, 1 − ( 1 − ε ) k ,
which can be arbitrarily close to 1 1 1 even when ε \varepsilon ε is a small constant.
Clairvoyant certificates. A mixture that is α \alpha α -competitive against the benchmark (2) at every stage is not enough on its own. The algorithm reaches O 0 O_0 O 0 at the start of the window and then moves into the mixture. At the end of the window, it has to move on to O m O_m O m , from which the reduction connects to the next window. The intermediate mixtures along both moves have to be good as well. Each move is judged against one benchmark: the entry, made during the first few arrivals of the window, is evaluated against the benchmark at stage 0 0 0 , without credit for those arrivals; the exit, made after the last arrival, is evaluated against the benchmark at stage m m m . One benchmark per move suffices because the reduction moves only while the optimum is nearly flat, or while the recent arrivals alone are a 3 / 4 3/4 3/4 -approximation. Writing δ i ∈ Δ \delta_i\in\Delta δ i ∈ Δ for the vertex that puts all weight on O i O_i O i , we arrive at the following notion, illustrated in Figure 6 .
Figure 6. A clairvoyant certificate (Definition 3.1) in the simplex Δ \Delta Δ of mixtures; the top vertex stands for the intermediate candidates. The anchor p p p is persistent, the entry path from δ 0 \delta_0 δ 0 is safe at stage 0, the exit path to δ m \delta_m δ m is safe at stage m m m , and the number of segments governs the consistency.
Definition 3.1 (Clairvoyant certificate). An ( α , L ) (\alpha,L) ( α , L ) -certificate for a window instance consists of a mixture p ∈ Δ p \in\Delta p ∈ Δ , the anchor, and two continuous piecewise-affine paths γ − , γ + : [ 0 , 1 ] → Δ \gamma^{-},\gamma^{+}:[0,1]\to\Delta γ − , γ + : [ 0 , 1 ] → Δ with γ − ( 0 ) = δ 0 \gamma^{-}(0)=\delta_0 γ − ( 0 ) = δ 0 , γ − ( 1 ) = p = γ + ( 0 ) \gamma^{-}(1)=p=\gamma^{+}(0) γ − ( 1 ) = p = γ + ( 0 ) , and γ + ( 1 ) = δ m \gamma^{+}(1)=\delta_m γ + ( 1 ) = δ m , such that
H j ( p ) ≥ α f ( O j ∪ R j ) for all j = 0 , … , m , (persistence) H_j(p) \ge\alpha f(O_j \cup R_j) \qquad\text{for all } j=0,\ldots,m, \qquad\text{(persistence)} H j ( p ) ≥ α f ( O j ∪ R j ) for all j = 0 , … , m , (persistence) H 0 ( γ − ( s ) ) ≥ α f ( O 0 ) for all s ∈ [ 0 , 1 ] , (safe entry) H_0(\gamma^{-}(s)) \ge\alpha f(O_0) \qquad\text{for all } s \in[0,1], \qquad\text{(safe entry)} H 0 ( γ − ( s )) ≥ α f ( O 0 ) for all s ∈ [ 0 , 1 ] , (safe entry) H m ( γ + ( s ) ) ≥ α f ( O m ∪ R m ) for all s ∈ [ 0 , 1 ] , (safe exit) H_m(\gamma^{+}(s)) \ge\alpha f(O_m \cup R_m) \qquad\text{for all } s \in[0,1], \qquad\text{(safe exit)} H m ( γ + ( s )) ≥ α f ( O m ∪ R m ) for all s ∈ [ 0 , 1 ] , (safe exit) and such that the two paths consist of at most L L L segments in total.
The reduction theorem
We can now state the main technical result of this section.
Theorem 5 (Reduction from consistency to clairvoyant certificates). Let 0 < α ≤ 3 / 4 0 < \alpha\le3/4 0 < α ≤ 3/4 and suppose that every window instance with stages 0 , … , m 0,\ldots,m 0 , … , m admits an ( α , L ) (\alpha,L) ( α , L ) -certificate with L ≤ C ( m + 1 ) L \le C(m+1) L ≤ C ( m + 1 ) for a constant C C C . Then, for every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , there is a deterministic clairvoyant O ( ε − 3 log ( 1 / ε ) ) O(\varepsilon^{-3}\log(1/\varepsilon)) O ( ε − 3 log ( 1/ ε )) -consistent algorithm that satisfies
f ( A L G t ) ≥ ( α − ε ) f ( O P T t ) at every time t , f(\mathrm{ALG}_t) \ge(\alpha-\varepsilon)f(\mathrm{OPT}_t) \qquad\text{at every time } t, f ( ALG t ) ≥ ( α − ε ) f ( OPT t ) at every time t , where the constant in the consistency bound depends only on C C C .
The proof, given in Appendix § 9 .§ 4.3 , has two parts: a schedule, which decides when the transitions take place, and a rounding procedure, the main novelty, which turns a certificate into an integral anchor and two lists of operations. We describe the schedule first, then explain the rounding that supplies its transition lists.
Scheduling. The time structure is shown in Figure 7 . The stream is cut into blocks of Θ ( ε k ) \Theta(\varepsilon k) Θ ( ε k ) arrivals, and each block hosts one transition, placed using foresight in the first subinterval of Θ ( ε 2 k ) \Theta(\varepsilon^{2}k) Θ ( ε 2 k ) arrivals during which f ( O P T t ) f(\mathrm{OPT}_t) f ( OPT t ) grows by at most a factor of 1 + ε 1+\varepsilon 1 + ε ; this is why one benchmark per move suffices. If there is no such subinterval, the optimum has at least quadrupled over the block, and the arrivals of the block, which are in the output, are by themselves a 3 / 4 3/4 3/4 -approximation. We therefore choose the last subinterval of the block for the transition. A window runs from one transition to the next; in between, the core holds the rounded anchor and persistence provides the approximation. A transition executes the exit list of the old window, a connecting segment from the old O m O_m O m to the new O 0 O_0 O 0 , and the entry list of the new window; the connecting segment retains at least a 3 / 4 3/4 3/4 fraction of the common benchmark met by its endpoints. Only O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) stages of a window need to be checked, one for each increase of f ( R j ) f(R_j) f ( R j ) by ε f ( O 0 ) \varepsilon f(O_0) ε f ( O 0 ) , so L = O ( 1 / ε ) L=O(1/\varepsilon) L = O ( 1/ ε ) and the O ( L κ ) O(L\kappa) O ( L κ ) operations of a transition cost O ( ε − 3 ) O(\varepsilon^{-3}) O ( ε − 3 ) changes per arrival; the logarithm in the consistency bound of Theorem 5 covers very small k k k , for which one simply recomputes an optimum after every arrival. The factor 3 / 4 3/4 3/4 enters only through the connecting segment and the fallbacks to the arrivals, which is why the theorem is stated for α ≤ 3 / 4 \alpha\le3/4 α ≤ 3/4 .
Figure 7. The schedule of the reduction. Blocks of Θ ( ε k ) \Theta(\varepsilon k) Θ ( ε k ) arrivals are divided into ⌈ 4 / ε ⌉ \lceil4/\varepsilon\rceil ⌈ 4/ ε ⌉ subintervals of Θ ( ε 2 k ) \Theta(\varepsilon^{2}k) Θ ( ε 2 k ) arrivals. In each block, the transition (red) takes place in the first subinterval during which the optimum grows by at most a factor of 1 + ε 1+\varepsilon 1 + ε ; subintervals in which it grows faster (orange) are skipped. A window runs from one transition to the next; in between, the core holds the rounded anchor of the window, and during a transition, the algorithm performs O ( L / ε 2 ) O(L/\varepsilon^{2}) O ( L / ε 2 ) changes per arrival.
Rounding. A certificate gives expectation guarantees at the anchor for every stage and at every point of two continuous paths, whereas the algorithm needs one integral core and two lists of insertions and deletions, every prefix of which is good. The first step is a discretization: the anchor is tested at the O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) retained stages, and each of the L L L segments is sampled at O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) mesh points, between which H H H changes by at most ε f ( O 0 ) \varepsilon f(O_0) ε f ( O 0 ) . This leaves M = O ( L + 1 / ε ) = O ( ε − 2 ) M=O(L+1/\varepsilon)=O(\varepsilon^{-2}) M = O ( L + 1/ ε ) = O ( ε − 2 ) tests, a number that depends only on ε \varepsilon ε , not on k k k or the ground set; this is important for the upcoming union bound. The second step uses common thresholds for rounding. Let z ( p ) = ∑ i p i 1 O i z(p)=\sum_i p_i\mathbf{1}_{O_i} z ( p ) = ∑ i p i 1 O i be the fractional vector within the budget κ \kappa κ . Draw one uniform threshold U e U_e U e per element once and for all, and round every mixture p p p to the set of elements with U e ≤ z e ( p ) U_e\le z_e(p) U e ≤ z e ( p ) , so that the anchor and all mesh points are rounded with the same randomness. At each test, the rounded set is worth at least H j ( p ) H_j(p) H j ( p ) in expectation, since its expected value is the multilinear extension at z ( p ) z(p) z ( p ) . After the few elements of large marginal value have been forced in, a concentration bound for submodular functions makes the test fail with probability well below 1 / M 1/M 1/ M provided k k k exceeds a sufficiently large polynomial in 1 / ε 1/\varepsilon 1/ ε ; the sizes of all sampled sets are controlled in the same way. The expected number of threshold crossings is O ( L κ ) O(L\kappa) O ( L κ ) , and Markov’s inequality bounds the probability of exceeding a constant multiple of this number. Together with the union bound over the tests, this leaves a realization that satisfies every value, size, and operation bound; we fix it, and the anchor and both lists become deterministic. The third step is where the common thresholds pay off. Along a segment, every z e z_e z e is affine, so an element crosses its threshold at most once per segment. The resulting lists have O ( L κ ) O(L\kappa) O ( L κ ) operations regardless of the mesh. This operation bound is small enough to achieve the desired consistency. Between adjacent mesh points, the two rounded sets both contain the rounding of the coordinatewise smaller type vector, whose value is certified, so performing the deletions before the insertions keeps every intermediate set good, and a list can be paused after any operation.
Constructing certificates. It remains to construct certificates, which we do at two levels.
Theorem 6 (Certificates at 1 / 2 1/\sqrt{2} 1/ 2 ). Every window instance with stages 0 , … , m 0,\ldots,m 0 , … , m admits a ( 1 / 2 , 3 ) (1/\sqrt{2},3) ( 1/ 2 , 3 ) -certificate.
Together with Theorem 5, this certificate yields a deterministic ( 1 / 2 − ε ) (1/\sqrt{2}-\varepsilon) ( 1/ 2 − ε ) -approximation; Appendix § 9 .§ 4.2 proves the certificate theorem. Its anchor is the half-mixture p = 1 2 ( δ 0 + δ c ) p=\frac{1}{2}(\delta_0+\delta_c) p = 2 1 ( δ 0 + δ c ) , where we choose the stage c c c carefully to balance the value of the mixture before and after that stage. The choice makes the anchor competitive throughout the window.
The two paths complete the certificate by showing how to enter and leave the anchor without a large drop in value. The entry is the straight path from δ 0 \delta_0 δ 0 to p p p , and the exit goes from p p p through whichever of δ 0 \delta_0 δ 0 and δ c \delta_c δ c is more valuable at the final stage, and then to δ m \delta_m δ m . This leads to three segments in total and we show that they possess the required guarantees. Thus, together with the anchor they form a certificate with three segments.
One can show that half-mixtures cannot do better than 1 / 2 1/\sqrt{2} 1/ 2 , and the tight bound is more complex and uses anchors whose weights are tuned to the instance.
Theorem 7 (Certificates at 3 / 4 3/4 3/4 ). Every window instance with stages 0 , … , m 0,\ldots,m 0 , … , m admits a ( 3 / 4 , m + 3 ) (3/4,m+3) ( 3/4 , m + 3 ) -certificate.
Theorem 4 follows from Theorems 5 and 7 , since m + 3 ≤ 3 ( m + 1 ) m+3\leq3(m+1) m + 3 ≤ 3 ( m + 1 ) . The proof of Theorem 7 is a Lean certificate, formally checked by the Lean proof assistant; a clean, human-readable proof remains open. An AI-generated natural-language proof and the Lean certificate are available on GitHub [3 ] .
AI Disclosure
We acknowledge the use of several state-of-the-art LLM models (such as ChatGPT Astra, Claude Opus, and Gemini Argon) as follows.
For the information-theoretic bound for randomized algorithms (Thm. 1 and Thm. 2), we seeded the models with our earlier paper [20 ] and the adjusted LP formulation in (1). We spent significant effort in interpreting and refactoring the resulting proof, and making it as insightful as possible. In particular, the interpretation of the resulting optimization problem as an interval selection problem is based on our reading of the AI-generated proofs, as is the formalization of the connection through the adaptivity gap.
To obtain the information-theoretic bounds for deterministic algorithms (Thm. 3 and Thm. 4) we started from a human-generated impossibility of 3 / 4 3/4 3/4 along with a human-generated proof sketch that obtains a 0.57 0.57 0.57 approximation (see Balkanski et al. [ [4 ] for that sketch). Iterative prompting allowed us to improve the lower bound and eventually close the gap, showing a tight 3 / 4 3/4 3/4 approximation. The first AI-generated proof of the 3 / 4 3/4 3/4 guarantee was about 100 pages long and near-impossible to parse and understand. Giving this proof the human-understandable form of § 5 is our main achievement. To reach this point, we used an AI-assisted refinement approach. We first asked the model to generate a simpler proof that beats 1 − 1 / e 1-1/e 1 − 1/ e , which led to the 1 / 2 1/\sqrt{2} 1/ 2 proof. We subsequently asked the model to abstract the two proofs in a similar manner as the (clairvoyant) addition-robustness notion abstracts the proof for randomized algorithms. This led to a human-understandable proof using the concept of certificates, which formed the basis of the human-written proof outline of § 5.2 .
We have carefully checked the correctness of the certificates framework as well as the elementary construction that leads to the 1 / 2 1/\sqrt{2} 1/ 2 certificate (included in Appendix § 9 .§ 4 ). We could not find any meaningful insights in the improved 3 / 4 3/4 3/4 certificate, and therefore decided to delegate that proof to an external appendix and Lean proof (see [3 ] ).
Proofs for the Tight Randomized Bound
This appendix proves the results stated in § 4 . We first verify that ξ ⋆ \xi^\star ξ ⋆ is well defined in Appendix § 8 .§ 1 and complete the coverage impossibility proof in Appendix § 8 .§ 4 , including the finite-k k k error terms and the conversion to an unweighted instance.
The algorithmic proofs follow the reductions in Figure 3 . Appendix § 8 .§ 5 converts clairvoyant addition robustness into consistency, and Appendix § 8 .4 derives addition robustness from an interval-selection bound. We establish that bound by reducing general intervals to consecutive intervals in Appendix § 8 .5 and analyzing the latter in Appendix § 8 .6. Finally, Appendix § 8 .7 combines these ingredients to prove Theorem 2.
Properties of the Polynomial Ψ \Psi Ψ
We begin by checking that the constant used in § 4 is well defined.
Proposition 1. The polynomial Ψ ( ξ ) = 89 ξ 4 − 44 ξ 3 − 19 ξ 2 − 3 ξ + 1 \Psi(\xi) = 89\xi^{4} - 44\xi^{3} - 19\xi^{2} - 3\xi+ 1 Ψ ( ξ ) = 89 ξ 4 − 44 ξ 3 − 19 ξ 2 − 3 ξ + 1 has a unique root ξ ⋆ ≈ 0.7941970147 \xi^\star\approx0.7941970147 ξ ⋆ ≈ 0.7941970147 in ( 1 / 2 , 1 ) (1/2,1) ( 1/2 , 1 ) .
Proof. The polynomial Ψ \Psi Ψ is continuous and has opposite signs at 1 / 2 1/2 1/2 and 1 1 1 :
Ψ ( 1 2 ) = 89 16 − 44 8 − 19 4 − 3 2 + 1 = − 83 16 < 0 , \Psi\left(\frac{1}{2}\right)=\frac{89}{16}-\frac{44}{8}-\frac{19}{4}-\frac{3}{2}+1=-\frac{83}{16}<0, Ψ ( 2 1 ) = 16 89 − 8 44 − 4 19 − 2 3 + 1 = − 16 83 < 0 ,
Ψ ( 1 ) = 89 − 44 − 19 − 3 + 1 = 24 > 0. \Psi(1)=89-44-19-3+1=24>0. Ψ ( 1 ) = 89 − 44 − 19 − 3 + 1 = 24 > 0.
The intermediate value theorem therefore gives a root in ( 1 / 2 , 1 ) (1/2,1) ( 1/2 , 1 ) . To prove uniqueness, we show that Ψ \Psi Ψ is strictly convex on this interval. Its first three derivatives are
Ψ ′ ( ξ ) = 356 ξ 3 − 132 ξ 2 − 38 ξ − 3 , \Psi'(\xi)=356\xi^3-132\xi^2-38\xi-3, Ψ ′ ( ξ ) = 356 ξ 3 − 132 ξ 2 − 38 ξ − 3 ,
Ψ ′ ′ ( ξ ) = 1068 ξ 2 − 264 ξ − 38 , \Psi''(\xi)=1068\xi^2-264\xi-38, Ψ ′′ ( ξ ) = 1068 ξ 2 − 264 ξ − 38 ,
Ψ ′ ′ ′ ( ξ ) = 2136 ξ − 264. \Psi'''(\xi)=2136\xi-264. Ψ ′′′ ( ξ ) = 2136 ξ − 264.
For ξ ≥ 1 / 2 \xi\ge1/2 ξ ≥ 1/2 , we have Ψ ′ ′ ′ ( ξ ) ≥ 804 > 0 \Psi'''(\xi)\ge804>0 Ψ ′′′ ( ξ ) ≥ 804 > 0 , so Ψ ′ ′ \Psi'' Ψ ′′ is increasing on [ 1 / 2 , 1 ] [1/2,1] [ 1/2 , 1 ] . Since Ψ ′ ′ ( 1 2 ) = 267 − 132 − 38 = 97 > 0 \Psi''\left(\frac{1}{2}\right)=267-132-38=97>0 Ψ ′′ ( 2 1 ) = 267 − 132 − 38 = 97 > 0 , it follows that Ψ ′ ′ > 0 \Psi''>0 Ψ ′′ > 0 on [ 1 / 2 , 1 ] [1/2,1] [ 1/2 , 1 ] , so Ψ \Psi Ψ is strictly convex there. Suppose, for a contradiction, that Ψ \Psi Ψ has two roots ξ 1 < ξ 2 \xi_1<\xi_2 ξ 1 < ξ 2 in ( 1 / 2 , 1 ) (1/2,1) ( 1/2 , 1 ) . Write ξ 1 = λ ⋅ 1 / 2 + ( 1 − λ ) ξ 2 \xi_1=\lambda\cdot1/2+(1-\lambda)\xi_2 ξ 1 = λ ⋅ 1/2 + ( 1 − λ ) ξ 2 with λ ∈ ( 0 , 1 ) \lambda\in(0,1) λ ∈ ( 0 , 1 ) . By strict convexity,
Ψ ( ξ 1 ) < λ Ψ ( 1 2 ) + ( 1 − λ ) Ψ ( ξ 2 ) = λ Ψ ( 1 2 ) < 0 , \Psi(\xi_1)<\lambda\Psi\left(\frac{1}{2}\right)+(1-\lambda)\Psi(\xi_2)=\lambda\Psi\left(\frac{1}{2}\right)<0, Ψ ( ξ 1 ) < λ Ψ ( 2 1 ) + ( 1 − λ ) Ψ ( ξ 2 ) = λ Ψ ( 2 1 ) < 0 ,
contradicting Ψ ( ξ 1 ) = 0 \Psi(\xi_1)=0 Ψ ( ξ 1 ) = 0 . Hence the root is unique.
For the numerical value, direct evaluation at rational endpoints gives Ψ ( 0.7941970146 ) < 0 < Ψ ( 0.7941970148 ) \Psi(0.7941970146)<0<\Psi(0.7941970148) Ψ ( 0.7941970146 ) < 0 < Ψ ( 0.7941970148 ) , locating the unique root in this interval.
Impossibility for Randomized Algorithms
We give the full analysis of the construction in § 4.1 . The limiting linear program in the proof sketch determines the constant ξ ⋆ \xi^\star ξ ⋆ ; here we account for the recourse budget and the exact cardinality constraint, then remove the weights.
Theorem 1. For any ε ∈ [ 1 / k , 1 ] \varepsilon\in[1/k,1] ε ∈ [ 1/ k , 1 ] , no randomized ε k \varepsilon k ε k -consistent clairvoyant algorithm can achieve an approximation ratio better than ξ ⋆ + O ( ε ) ≈ 0.7942 + O ( ε ) \xi^\star+O(\varepsilon)\approx0.7942+O(\varepsilon) ξ ⋆ + O ( ε ) ≈ 0.7942 + O ( ε ) for Maximum Coverage subject to a cardinality constraint k k k .
Proof. For k = 1 k=1 k = 1 , the statement is trivial since ε = 1 \varepsilon=1 ε = 1 and no approximation ratio exceeds 1 1 1 . Fix k ≥ 2 k\ge2 k ≥ 2 and ε ∈ [ 1 / k , 1 ] \varepsilon\in[1/k,1] ε ∈ [ 1/ k , 1 ] . We first prove the bound for a weighted coverage instance.
Let u 1 u_1 u 1 be the unique root in ( 0 , 1 ) (0,1) ( 0 , 1 ) of Φ ( x ) = x 4 + x 3 − 2 x 2 − 3 x + 2 \Phi(x)=x^4+x^3-2x^2-3x+2 Φ ( x ) = x 4 + x 3 − 2 x 2 − 3 x + 2 , and set u 2 = u 1 2 ( 1 + u 1 ) u_2=u_1^2(1+u_1) u 2 = u 1 2 ( 1 + u 1 ) . The parameter analysis in the proof of Lemma 4 establishes 0 < u 2 < u 1 < 1 0<u_2<u_1<1 0 < u 2 < u 1 < 1 independently of the construction below. Numerically,
u 1 ≈ 0.550794645 , u 2 ≈ 0.470471923. u_1\approx0.550794645,\qquad u_2\approx0.470471923. u 1 ≈ 0.550794645 , u 2 ≈ 0.470471923.
The instance. Partition a universe U U U into three groups U 0 , U 1 , U 2 U_0,U_1,U_2 U 0 , U 1 , U 2 of k k k elements each, assigning weight u i u_i u i to every element of U i U_i U i , where u 0 = 1 u_0=1 u 0 = 1 . The stream consists of the 3 k 3k 3 k singleton subsets of U U U , in any order, followed by the large sets U 0 U_0 U 0 and U 1 U_1 U 1 . This is the instance in Figure 2 .
Relabel the last three time steps as 0 0 0 , 1 1 1 , and 2 2 2 : immediately before U 0 U_0 U 0 arrives, immediately after U 0 U_0 U 0 arrives, and immediately after U 1 U_1 U 1 arrives. Write o i o_i o i for the optimal value and a i a_i a i for the algorithm’s expected value at these time steps.
At time 0 0 0 , an optimal solution selects all k k k singletons from U 0 U_0 U 0 , so o 0 = k o_0=k o 0 = k . At time 1 1 1 , it selects U 0 U_0 U 0 and k − 1 k-1 k − 1 singletons from U 1 U_1 U 1 , giving o 1 = k + u 1 ( k − 1 ) o_1=k+u_1(k-1) o 1 = k + u 1 ( k − 1 ) . At time 2 2 2 , it selects both large sets and k − 2 k-2 k − 2 singletons from U 2 U_2 U 2 , giving o 2 = k ( 1 + u 1 + u 2 ) − 2 u 2 o_2=k(1+u_1+u_2)-2u_2 o 2 = k ( 1 + u 1 + u 2 ) − 2 u 2 .
Fix a randomized ε k \varepsilon k ε k -consistent algorithm, and let k i k_i k i be the expected number of singletons from U i U_i U i that it holds at time 0. Granting it the large sets as they arrive and using consistency to bound the additional singleton sets gives
a 0 = k 0 + u 1 k 1 + u 2 k 2 , a 1 ≤ k + u 1 ( k 1 + ε k ) + u 2 k 2 , a 2 ≤ k + u 1 k + u 2 ( k 2 + 2 ε k ) . \begin{aligned}
a_0 &= k_0 + u_1 k_1 + u_2 k_2,\\
a_1 &\le k + u_1(k_1+\varepsilon k) + u_2 k_2,\\
a_2 &\le k + u_1 k + u_2(k_2+2\varepsilon k).
\end{aligned} a 0 a 1 a 2 = k 0 + u 1 k 1 + u 2 k 2 , ≤ k + u 1 ( k 1 + ε k ) + u 2 k 2 , ≤ k + u 1 k + u 2 ( k 2 + 2 ε k ) .
The terms involving ε \varepsilon ε account for at most ε k \varepsilon k ε k newly selected singleton sets per update. At time 1, each new singleton outside U 0 U_0 U 0 has weight at most u 1 u_1 u 1 ; at time 2, only singletons in U 2 U_2 U 2 , each of weight u 2 u_2 u 2 , can contribute beyond the two large sets.
Bounding the approximation ratio. Any approximation ratio ρ \rho ρ must satisfy a i ≥ ρ o i a_i \ge\rho o_i a i ≥ ρ o i at all three time steps. Substituting the bounds above yields a linear-program relaxation in the expected counts k i k_i k i , which need not be integers. Normalize them as α i = k i / k \alpha_i=k_i/k α i = k i / k and replace both ε \varepsilon ε and 1 / k 1/k 1/ k by ε ^ = ε + 1 / k \hat{\varepsilon}=\varepsilon+1/k ε ^ = ε + 1/ k ; this only relaxes the constraints. It suffices to consider 0 ≤ ρ ≤ 1 0\le\rho\le1 0 ≤ ρ ≤ 1 , so the program is
Maximize ρ subject to α 0 + α 1 + α 2 ≤ 1 , α 0 + u 1 α 1 + u 2 α 2 ≥ ρ , 1 + u 1 ( α 1 + ε ^ ) + u 2 α 2 ≥ ρ ( 1 + u 1 − u 1 ε ^ ) , 1 + u 1 + u 2 ( α 2 + 2 ε ^ ) ≥ ρ ( 1 + u 1 + u 2 − 2 ε ^ u 2 ) , α i ≥ 0 for i = 0 , 1 , 2 , 0 ≤ ρ ≤ 1. \begin{aligned}
\text{Maximize}\quad&\rho\\
\text{subject to}\quad&\alpha_0+\alpha_1+\alpha_2\le1,\\
&\alpha_0+u_1\alpha_1+u_2\alpha_2\ge\rho,\\
&1+u_1(\alpha_1+\hat{\varepsilon})+u_2\alpha_2\ge\rho(1+u_1-u_1\hat{\varepsilon}),\\
&1+u_1+u_2(\alpha_2+2\hat{\varepsilon})\ge\rho(1+u_1+u_2-2\hat{\varepsilon}u_2),\\
&\alpha_i\ge0\quad\text{for }i=0,1,2,\qquad0\le\rho\le1.
\end{aligned} Maximize subject to ρ α 0 + α 1 + α 2 ≤ 1 , α 0 + u 1 α 1 + u 2 α 2 ≥ ρ , 1 + u 1 ( α 1 + ε ^ ) + u 2 α 2 ≥ ρ ( 1 + u 1 − u 1 ε ^ ) , 1 + u 1 + u 2 ( α 2 + 2 ε ^ ) ≥ ρ ( 1 + u 1 + u 2 − 2 ε ^ u 2 ) , α i ≥ 0 for i = 0 , 1 , 2 , 0 ≤ ρ ≤ 1.
We bound its optimal value by ξ ⋆ + O ( ε ^ ) = ξ ⋆ + O ( ε ) \xi^\star+O(\hat{\varepsilon})=\xi^\star+O(\varepsilon) ξ ⋆ + O ( ε ^ ) = ξ ⋆ + O ( ε ) . We may assume α 0 + α 1 + α 2 = 1 \alpha_0+\alpha_1+\alpha_2=1 α 0 + α 1 + α 2 = 1 , since increasing α 0 \alpha_0 α 0 to fill unused capacity only relaxes the first approximation constraint. Take a convex combination of the three approximation constraints with weights
μ 0 = u 2 , μ 1 = u 2 u 1 − u 2 , μ 2 = 1 − u 2 u 1 . \mu_0=u_2,\qquad\mu_1=\frac{u_2}{u_1}-u_2,\qquad\mu_2=1-\frac{u_2}{u_1}. μ 0 = u 2 , μ 1 = u 1 u 2 − u 2 , μ 2 = 1 − u 1 u 2 .
The resulting inequality is
1 + u 1 − u 2 + ( 1 + ρ ) ε ˉ ≥ ρ ( 1 + u 1 + u 2 − u 1 u 2 − u 2 2 u 1 ) , 1+u_1-u_2+(1+\rho)\bar{\varepsilon}\ge\rho\left(1+u_1+u_2-u_1u_2-\frac{u_2^2}{u_1}\right), 1 + u 1 − u 2 + ( 1 + ρ ) ε ˉ ≥ ρ ( 1 + u 1 + u 2 − u 1 u 2 − u 1 u 2 2 ) ,
where ε ˉ = ε ^ u 2 ( 3 − u 1 − 2 u 2 / u 1 ) ≈ 0.3485 ε ^ \bar{\varepsilon}=\hat{\varepsilon}u_2(3-u_1-2u_2/u_1)\approx0.3485\hat{\varepsilon} ε ˉ = ε ^ u 2 ( 3 − u 1 − 2 u 2 / u 1 ) ≈ 0.3485 ε ^ . Put D = 1 + u 1 + u 2 − u 1 u 2 − u 2 2 / u 1 > 0 D=1+u_1+u_2-u_1u_2-u_2^2/u_1>0 D = 1 + u 1 + u 2 − u 1 u 2 − u 2 2 / u 1 > 0 ; this is a convex combination of the positive limiting benchmark values. Using ρ ≤ 1 \rho\le1 ρ ≤ 1 gives the uniform bound
ρ ≤ 1 + u 1 − u 2 D + 2 ε ˉ D = 1 + u 1 − u 2 D + O ( ε ) , \rho\le\frac{1+u_1-u_2}{D}+\frac{2\bar{\varepsilon}}{D}
=\frac{1+u_1-u_2}{D}+O(\varepsilon), ρ ≤ D 1 + u 1 − u 2 + D 2 ε ˉ = D 1 + u 1 − u 2 + O ( ε ) ,
where we use 1 / k ≤ ε 1/k\le\varepsilon 1/ k ≤ ε to obtain ε ^ ≤ 2 ε \hat{\varepsilon}\le2\varepsilon ε ^ ≤ 2 ε . By our choice of u 1 u_1 u 1 and u 2 u_2 u 2 ,
( 1 + u 1 + u 2 − u 1 u 2 − u 2 2 u 1 ) − ( 1 + u 1 − u 2 ) ( 1 + u 1 u 2 ) = u 2 Φ ( u 1 ) = 0 , \left(1+u_1+u_2-u_1u_2-\frac{u_2^2}{u_1}\right)-(1+u_1-u_2)(1+u_1u_2)=u_2\Phi(u_1)=0, ( 1 + u 1 + u 2 − u 1 u 2 − u 1 u 2 2 ) − ( 1 + u 1 − u 2 ) ( 1 + u 1 u 2 ) = u 2 Φ ( u 1 ) = 0 ,
so that ρ ≤ 1 1 + u 1 u 2 + O ( ε ) = ξ ⋆ + O ( ε ) \rho\le\frac{1}{1+u_1u_2}+O(\varepsilon)=\xi^\star+O(\varepsilon) ρ ≤ 1 + u 1 u 2 1 + O ( ε ) = ξ ⋆ + O ( ε ) . Indeed, substituting u 2 = u 1 2 ( 1 + u 1 ) u_2=u_1^2(1+u_1) u 2 = u 1 2 ( 1 + u 1 ) and using the equation for u 1 u_1 u 1 shows that 1 / ( 1 + u 1 u 2 ) 1/(1+u_1u_2) 1/ ( 1 + u 1 u 2 ) lies in ( 1 / 2 , 1 ) (1/2,1) ( 1/2 , 1 ) and satisfies Ψ ( ξ ) = 89 ξ 4 − 44 ξ 3 − 19 ξ 2 − 3 ξ + 1 = 0 \Psi(\xi)=89\xi^4-44\xi^3-19\xi^2-3\xi+1=0 Ψ ( ξ ) = 89 ξ 4 − 44 ξ 3 − 19 ξ 2 − 3 ξ + 1 = 0 .
Removing the weights. To obtain an unweighted coverage instance, choose rational weights 0 < u ~ 2 < u ~ 1 < 1 0 < \tilde{u}_2 < \tilde{u}_1 < 1 0 < u ~ 2 < u ~ 1 < 1 with ∣ u ~ i − u i ∣ < ε |\tilde{u}_i-u_i| < \varepsilon ∣ u ~ i − u i ∣ < ε for i = 1 , 2 i=1,2 i = 1 , 2 . Such weights exist for every real ε > 0 \varepsilon> 0 ε > 0 by density of the rationals; they need not satisfy u ~ 2 = u ~ 1 2 ( 1 + u ~ 1 ) \tilde{u}_2 = \tilde{u}_1^2(1+\tilde{u}_1) u ~ 2 = u ~ 1 2 ( 1 + u ~ 1 ) . This changes the coverage of any solution, and hence each optimal value, by at most 2 ε k 2\varepsilon k 2 ε k , while all three optimal values remain at least k k k . The weighted bound applies to every feasible sequence of solutions, including one chosen for the perturbed instance. Each of the three expected approximation ratios changes by at most 4 ε 4\varepsilon 4 ε , so the bound changes by only O ( ε ) O(\varepsilon) O ( ε ) . Multiply all weights by a common denominator and replace each weighted universe element by the corresponding number of unit-weight copies, with the same incidences to the stream sets. This preserves all approximation ratios and the cardinality and consistency constraints.
Remark 1. For any fixed consistency bound C C C and any δ > 0 \delta> 0 δ > 0 , choosing k k k sufficiently large yields an unweighted coverage instance on which no randomized C C C -consistent clairvoyant algorithm can maintain an approximation ratio better than ξ ⋆ + δ \xi^\star+\delta ξ ⋆ + δ . Thus the limiting impossibility constant matches the guarantee in Theorem 2.
From Clairvoyant Addition-Robustness to Consistency
We prove Lemma 1 from § 4.3 by adapting the checkpoint construction of Dütting et al. [ [20 ] . Algorithm 1 retains recent arrivals while gradually replacing a sampled core. In the algorithm, AdditionRobust samples from the α \alpha α -addition-robust distribution supplied by the lemma’s hypothesis. The proof verifies feasibility, bounds both insertions and deletions at every update, and establishes the expected approximation guarantee at each fixed time.
Algorithm 1 Randomized Clairvoyant Algorithm
Require: Stream $(x_1,\ldots,x_n)$, submodular function $f$, budget $k$, parameter $\gamma \in (0,1/8)$
1: if $k < 8\gamma$ then
2: Maintain an exact optimum after every arrival
3: return
4: $\ell \leftarrow \lfloor\gamma k\rfloor$, $\kappa \leftarrow k-2\ell$, $h \leftarrow \lceil 1/\gamma\rceil$
5: Partition the stream into blocks $B_1,\ldots,B_q$ of length $\ell$, padding the last block with zero-marginal dummy arrivals if needed
6: $\tau_j \leftarrow j\ell$ for $j=0,\ldots,q$; $A_0 \leftarrow \varnothing$
7: During $B_1$, retain all arriving elements
8: for $j=1,\ldots,q-1$ do
9: At boundary $\tau_j$, sample $A_j \leftarrow \operatorname{AdditionRobust}(X_{\tau_j},(x_{\tau_j+1},\ldots,x_n),f,\kappa)$
10: $C \leftarrow A_{j-1}\cup B_j$
11: Pair elements of $C\setminus A_j$ with elements of $A_j\setminus C$
12: Schedule these exchanges, followed by the remaining deletions or insertions
13: Partition $B_{j+1}$ into $h$ contiguous subblocks of nearly equal length
14: Choose a subblock $H$ uniformly at random, independently of checkpoint samples
15: for each arrival $x_t$ in $B_{j+1}$ do
16: if $x_t \in H$ then
17: Execute the next scheduled operations on $C$, evenly distributed over $H$
18: $\mathrm{ALG}_t \leftarrow C \cup (B_{j+1}\cap X_t)$
19: Discard outputs after the actual end of the stream
Lemma 1. Suppose that, for every instance of the clairvoyant addition-robust problem, an algorithm returns an α \alpha α -addition-robust distribution, where 0 ≤ α ≤ 1 0 \le\alpha\le1 0 ≤ α ≤ 1 . For every γ ∈ ( 0 , 1 / 8 ) \gamma\in(0,1/8) γ ∈ ( 0 , 1/8 ) , this yields a randomized clairvoyant O ( γ − 2 ) O(\gamma^{-2}) O ( γ − 2 ) -consistent algorithm that achieves an ( α − 3 γ ) (\alpha- 3\gamma) ( α − 3 γ ) -approximation.
Proof. For each future prefix R R R , an optimum T T T of size at most κ \kappa κ in V n o w ∪ R V_{\mathrm{now}} \cup R V now ∪ R satisfies T ⊆ ( T ∩ V n o w ) ∪ R T \subseteq(T \cap V_{\mathrm{now}}) \cup R T ⊆ ( T ∩ V now ) ∪ R . Hence
max O ⊆ V n o w ∣ O ∣ ≤ κ f ( O ∪ R ) ≥ max T ⊆ V n o w ∪ R ∣ T ∣ ≤ κ f ( T ) . \max_{\substack{O \subseteq V_{\mathrm{now}}\\ |O| \leq\kappa}} f(O \cup R) \geq\max_{\substack{T \subseteq V_{\mathrm{now}} \cup R\\ |T| \leq\kappa}} f(T). O ⊆ V now ∣ O ∣ ≤ κ max f ( O ∪ R ) ≥ T ⊆ V now ∪ R ∣ T ∣ ≤ κ max f ( T ) .
Thus the addition-robust guarantee also bounds the dynamic optimum at each prefix, as needed below.
If k < 8 γ − 2 k < 8\gamma^{-2} k < 8 γ − 2 , recompute an exact optimum after every arrival. Its symmetric difference with the previous solution has size at most 2 k = O ( γ − 2 ) 2k = O(\gamma^{-2}) 2 k = O ( γ − 2 ) . Assume henceforth k ≥ 8 γ − 2 k \geq8\gamma^{-2} k ≥ 8 γ − 2 and set
ℓ = ⌊ γ k ⌋ , κ = k − 2 ℓ , h = ⌈ 1 / γ ⌉ . \ell= \lfloor\gamma k \rfloor,\qquad\kappa= k - 2\ell,\qquad h = \lceil1/\gamma\rceil. ℓ = ⌊ γ k ⌋ , κ = k − 2 ℓ , h = ⌈ 1/ γ ⌉ .
Split the stream into blocks B 1 , B 2 , … B_1, B_2, \ldots B 1 , B 2 , … of ℓ \ell ℓ arrivals, with boundaries τ j = j ℓ \tau_j = j\ell τ j = j ℓ . For scheduling only, an incomplete final block may be completed by zero-marginal dummy arrivals; outputs after the actual end of the stream are discarded. At each boundary τ j \tau_j τ j , sample a checkpoint solution A j ⊆ X τ j A_j \subseteq X_{\tau_j} A j ⊆ X τ j of size at most κ \kappa κ using the clairvoyant routine with the remaining stream. Set A 0 = ∅ A_0 = \varnothing A 0 = ∅ . The first block is handled by retaining all its arrivals.
Feasibility and recourse. During block B j + 1 B_{j+1} B j + 1 , transition from the old core A j − 1 ∪ B j A_{j-1} \cup B_j A j − 1 ∪ B j to the new core A j A_j A j . Including B j B_j B j in the old core ensures that its obsolete elements are deleted as part of this transition, rather than all at once at a block boundary. Both cores have size at most κ + ℓ = k − ℓ \kappa+ \ell= k - \ell κ + ℓ = k − ℓ . Throughout the transition, also retain the current prefix of B j + 1 B_{j+1} B j + 1 . To change cores, pair elements to be removed with elements to be inserted, make the resulting exchanges, and then perform any remaining deletions or insertions. There are at most k k k such operations; each changes at most two elements, and every intermediate core has size at most that of the larger endpoint core. The maintained solution therefore always has size at most k k k .
Partition B j + 1 B_{j+1} B j + 1 into h h h contiguous subblocks whose lengths differ by at most one. Independently of all checkpoint samples, choose one subblock uniformly at random and spread the transition operations over its updates. The minimum subblock length d d d satisfies
d = ⌊ ℓ / h ⌋ ≥ γ 2 k 8 . d = \lfloor\ell/h \rfloor\geq\frac{\gamma^2 k}{8}. d = ⌊ ℓ / h ⌋ ≥ 8 γ 2 k .
Here we use ℓ ≥ γ k / 2 \ell\geq\gamma k/2 ℓ ≥ γ k /2 , h ≤ 2 / γ h \leq2/\gamma h ≤ 2/ γ , and ℓ / h ≥ 2 \ell/h \geq2 ℓ / h ≥ 2 . Each update needs at most 2 ⌈ k / d ⌉ + 1 = O ( γ − 2 ) 2\lceil k/d \rceil+ 1 = O(\gamma^{-2}) 2 ⌈ k / d ⌉ + 1 = O ( γ − 2 ) changes, including the new arrival. After the transition the solution is A j A_j A j plus the current block prefix; at the next boundary this is exactly the next old core. Thus there is no additional boundary cost.
Value at a fixed time. Fix an arrival time t t t with x t ∈ B j + 1 x_t \in B_{j+1} x t ∈ B j + 1 . Its subblock is selected for transition with probability 1 / h ≤ γ 1/h \leq\gamma 1/ h ≤ γ . Before the selected subblock, the maintained set is A j − 1 ∪ ( X t ∖ X τ j − 1 ) A_{j-1} \cup(X_t \setminus X_{\tau_{j-1}}) A j − 1 ∪ ( X t ∖ X τ j − 1 ) ; after it, the set is A j ∪ ( X t ∖ X τ j ) A_j \cup(X_t \setminus X_{\tau_j}) A j ∪ ( X t ∖ X τ j ) . Each added set is a prefix of the future sequence supplied to the corresponding checkpoint routine. The events determining which case occurs are independent of the checkpoint samples. Writing OPT t ( κ ) \operatorname{OPT}^{(\kappa)}_t OPT t ( κ ) for the best solution of size at most κ \kappa κ in X t X_t X t , we obtain
E [ f ( ALG t ) ] ≥ ( 1 − 1 / h ) α f ( OPT t ( κ ) ) . (4) \mathbb{E}[f(\operatorname{ALG}_t)] \geq(1 - 1/h)\alpha f(\operatorname{OPT}^{(\kappa)}_t). \tag*{(4)} E [ f ( ALG t )] ≥ ( 1 − 1/ h ) α f ( OPT t ( κ ) ) . (4)
This also covers the first old core A 0 = ∅ A_0 = \varnothing A 0 = ∅ , since its union with the arrivals contains every available element. To compare the reduced-budget optimum with O P T t \mathrm{OPT}_t OPT t , suppose first that s = ∣ O P T t ∣ ≥ κ s = |\mathrm{OPT}_t| \ge\kappa s = ∣ OPT t ∣ ≥ κ . By submodularity and nonnegativity, a uniformly sampled κ \kappa κ -subset of O P T t \mathrm{OPT}_t OPT t has expected value at least ( κ / s ) f ( O P T t ) (\kappa/s)f(\mathrm{OPT}_t) ( κ / s ) f ( OPT t ) , where κ / s ≥ κ / k \kappa/s \ge\kappa/k κ / s ≥ κ / k . If O P T t \mathrm{OPT}_t OPT t has fewer than κ \kappa κ elements, retain it in full. Hence
f ( O P T t ( κ ) ) ≥ κ k f ( O P T t ) ≥ ( 1 − 2 γ ) f ( O P T t ) . f(\mathrm{OPT}_t^{(\kappa)}) \ge\frac{\kappa}{k}f(\mathrm{OPT}_t) \ge(1-2\gamma)f(\mathrm{OPT}_t). f ( OPT t ( κ ) ) ≥ k κ f ( OPT t ) ≥ ( 1 − 2 γ ) f ( OPT t ) .
Combining the last two displays gives an approximation ratio of at least ( 1 − γ ) ( 1 − 2 γ ) α ≥ α − 3 γ (1-\gamma)(1-2\gamma)\alpha\ge\alpha- 3\gamma ( 1 − γ ) ( 1 − 2 γ ) α ≥ α − 3 γ .
From Interval Selection to Clairvoyant Addition-Robustness
Having established the checkpoint reduction, we turn to the addition-robust distribution it requires. We use the prefix optimizers O i O_i O i , prefixes R j R_j R j , and LP value ρ ∗ \rho^* ρ ∗ from § 4.3 . Let Δ \Delta Δ be the simplex of distributions on { 0 , … , m } \{0,\ldots,m\} { 0 , … , m } .
If κ = 0 \kappa= 0 κ = 0 , returning ∅ \varnothing ∅ achieves the benchmark f ( R j ) f(R_j) f ( R j ) exactly for every prefix. If κ ≥ 1 \kappa\ge1 κ ≥ 1 and f ( O 0 ) = 0 f(O_0) = 0 f ( O 0 ) = 0 , every present element has zero singleton value. Monotonicity and submodularity then imply f ( O ∪ R j ) = f ( R j ) f(O \cup R_j) = f(R_j) f ( O ∪ R j ) = f ( R j ) for every O ⊆ V n o w O \subseteq V_{\mathrm{now}} O ⊆ V now and every j j j , so returning O 0 O_0 O 0 also achieves the benchmark exactly.
For the remainder of this subsection, assume κ ≥ 1 \kappa\ge1 κ ≥ 1 and f ( O 0 ) > 0 f(O_0) > 0 f ( O 0 ) > 0 . Define the normalized payoffs
w i , j = f ( O i ∪ R j ) f ( O j ∪ R j ) . w_{i,j} = \frac{f(O_i \cup R_j)}{f(O_j \cup R_j)}. w i , j = f ( O j ∪ R j ) f ( O i ∪ R j ) .
which are well defined under these assumptions. We first justify the minimax formulation used in the main text.
Lemma 5. Under the standing assumptions κ ≥ 1 \kappa\ge1 κ ≥ 1 and f ( O 0 ) > 0 f(O_0) > 0 f ( O 0 ) > 0 , finite minimax duality gives
ρ ∗ = max α ∈ Δ min j = 0 , … , m ∑ i = 0 m α i w i , j = min β ∈ Δ max i = 0 , … , m ∑ j = 0 m β j w i , j . \rho^* = \max_{\alpha\in\Delta}\min_{j=0,\ldots,m}\sum_{i=0}^{m}\alpha_i w_{i,j} = \min_{\beta\in\Delta}\max_{i=0,\ldots,m}\sum_{j=0}^{m}\beta_j w_{i,j}. ρ ∗ = α ∈ Δ max j = 0 , … , m min i = 0 ∑ m α i w i , j = β ∈ Δ min i = 0 , … , m max j = 0 ∑ m β j w i , j . Proof. A linear function on a simplex attains its maximum and minimum at vertices. Applying this observation before and after finite minimax duality gives
max α ∈ Δ min j = 0 , … , m ∑ i α i w i , j = max α ∈ Δ min β ∈ Δ ∑ i = 0 m ∑ j = 0 m α i β j w i , j = min β ∈ Δ max α ∈ Δ ∑ i = 0 m ∑ j = 0 m α i β j w i , j = min β ∈ Δ max i ∑ j = 0 m β j w i , j . \begin{aligned}
\max_{\alpha\in\Delta}\min_{j=0,\ldots,m}\sum_i \alpha_i w_{i,j}
&= \max_{\alpha\in\Delta}\min_{\beta\in\Delta}\sum_{i=0}^{m}\sum_{j=0}^{m}\alpha_i\beta_j w_{i,j} \\
&= \min_{\beta\in\Delta}\max_{\alpha\in\Delta}\sum_{i=0}^{m}\sum_{j=0}^{m}\alpha_i\beta_j w_{i,j} \\
&= \min_{\beta\in\Delta}\max_i\sum_{j=0}^{m}\beta_j w_{i,j}.
\end{aligned} α ∈ Δ max j = 0 , … , m min i ∑ α i w i , j = α ∈ Δ max β ∈ Δ min i = 0 ∑ m j = 0 ∑ m α i β j w i , j = β ∈ Δ min α ∈ Δ max i = 0 ∑ m j = 0 ∑ m α i β j w i , j = β ∈ Δ min i max j = 0 ∑ m β j w i , j .
We now represent each prefix optimizer by an interval. The interval payoffs lower-bound the corresponding submodular values, and reweighting the adversary’s distribution lets us apply an adaptivity-gap bound to the normalized payoffs in Lemma 5.
Lemma 2. Let α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] . If Γ ( ℓ , r , p ) ≥ α \Gamma(\ell,r,p) \ge\alpha Γ ( ℓ , r , p ) ≥ α for every interval-selection instance, then every instance of clairvoyant addition-robust submodular maximization admits an α \alpha α -addition-robust distribution.
Proof. It suffices to consider the nontrivial case described above. Associate with each O i O_i O i the interval
[ ℓ i , r i ] = [ f ( R i ) , f ( O i ∪ R i ) ] . [\ell_i,r_i] = [f(R_i), f(O_i \cup R_i)]. [ ℓ i , r i ] = [ f ( R i ) , f ( O i ∪ R i )] . We first claim that, for every i , j i,j i , j ,
f ( O i ∪ R j ) ≥ v ( i , j ) . (5) f(O_i \cup R_j) \ge v(i,j). \tag*{(5)} f ( O i ∪ R j ) ≥ v ( i , j ) . (5) If j ≤ i j \le i j ≤ i , diminishing returns and R j ⊆ R i R_j \subseteq R_i R j ⊆ R i give
f ( O i ∪ R j ) − f ( R j ) ≥ f ( O i ∪ R i ) − f ( R i ) = r i − ℓ i . f(O_i \cup R_j) - f(R_j) \ge f(O_i \cup R_i) - f(R_i) = r_i - \ell_i. f ( O i ∪ R j ) − f ( R j ) ≥ f ( O i ∪ R i ) − f ( R i ) = r i − ℓ i . Since ℓ j ≤ ℓ i \ell_j \le\ell_i ℓ j ≤ ℓ i , the right-hand side becomes v ( i , j ) v(i,j) v ( i , j ) after adding f ( R j ) = ℓ j f(R_j) = \ell_j f ( R j ) = ℓ j . If j ≥ i j \ge i j ≥ i , monotonicity gives
f ( O i ∪ R j ) ≥ max { f ( R j ) , f ( O i ∪ R i ) } = max { ℓ j , r i } = v ( i , j ) . f(O_i \cup R_j) \ge\max\{f(R_j), f(O_i \cup R_i)\} = \max\{\ell_j,r_i\} = v(i,j). f ( O i ∪ R j ) ≥ max { f ( R j ) , f ( O i ∪ R i )} = max { ℓ j , r i } = v ( i , j ) . Fix any β ∈ Δ \beta\in\Delta β ∈ Δ and define
Z = ∑ j = 0 m β j r j , p j = β j / r j Z ( j = 0 , … , m ) . Z = \sum_{j=0}^{m} \frac{\beta_j}{r_j}, \qquad p_j = \frac{\beta_j/r_j}{Z} \qquad(j=0,\ldots,m). Z = j = 0 ∑ m r j β j , p j = Z β j / r j ( j = 0 , … , m ) . Then p p p is a probability distribution on the intervals [ ℓ j , r j ] [\ell_j,r_j] [ ℓ j , r j ] , and β j = Z p j r j \beta_j = Zp_jr_j β j = Z p j r j . This reweighting absorbs the denominators in w i , j w_{i,j} w i , j . By (5) and the assumed bound Γ ( ℓ , r , p ) ≥ α \Gamma(\ell,r,p) \ge\alpha Γ ( ℓ , r , p ) ≥ α ,
max i ∑ j = 0 m β j f ( O i ∪ R j ) r j = Z max i E j ∼ p [ f ( O i ∪ R j ) ] ≥ Z max i E j ∼ p [ v ( i , j ) ] ≥ Z α E j ∼ p [ max h v ( h , j ) ] ≥ Z α E j ∼ p [ v ( j , j ) ] = Z α E j ∼ p [ r j ] = α . \begin{aligned}
\max_i \sum_{j=0}^{m} \beta_j \frac{f(O_i \cup R_j)}{r_j}
&= Z \max_i \mathbb{E}_{j\sim p}[f(O_i \cup R_j)] \\
&\ge Z \max_i \mathbb{E}_{j\sim p}[v(i,j)] \\
&\ge Z\alpha\mathbb{E}_{j\sim p}\left[\max_h v(h,j)\right] \\
&\ge Z\alpha\mathbb{E}_{j\sim p}[v(j,j)] \\
&= Z\alpha\mathbb{E}_{j\sim p}[r_j] = \alpha.
\end{aligned} i max j = 0 ∑ m β j r j f ( O i ∪ R j ) = Z i max E j ∼ p [ f ( O i ∪ R j )] ≥ Z i max E j ∼ p [ v ( i , j )] ≥ Z α E j ∼ p [ h max v ( h , j ) ] ≥ Z α E j ∼ p [ v ( j , j )] = Z α E j ∼ p [ r j ] = α . This holds for every β ∈ Δ \beta\in\Delta β ∈ Δ . Lemma 5 therefore gives ρ ⋆ ≥ α \rho^\star\ge\alpha ρ ⋆ ≥ α , proving the lossless reduction. □ \square □
From Structured to General Interval Selection {#sec:A.5} Lemma 2 reduces the algorithmic guarantee to a uniform interval-selection bound. We next prove Lemma 3, which allows us to restrict attention to the structured family in Section 2.5. The proof replaces an arbitrary instance by shadow intervals, normalizes their expected surviving lengths, and expresses the required inequality as an average of inequalities for consecutive intervals under equalizing distributions.
We first derive the equalizing distribution for nonincreasing consecutive intervals. For every fixed interval i i i ,
E j ∼ p [ v ( i , j ) ] = E j ∼ p [ ℓ j ] + ( r i − ℓ i ) ∑ j = 0 i p j . \mathbb{E}_{j\sim p}[v(i,j)] = \mathbb{E}_{j\sim p}[\ell_j] + (r_i-\ell_i)\sum_{j=0}^{i}p_j. E j ∼ p [ v ( i , j )] = E j ∼ p [ ℓ j ] + ( r i − ℓ i ) j = 0 ∑ i p j .
Since ∑ j = 0 N p j = 1 \sum_{j=0}^{N}p_j=1 ∑ j = 0 N p j = 1 , these values are equal for all i i i if and only if
∑ j = 0 i p j = r N − ℓ N r i − ℓ i ( i = 0 , … , N ) . (6) \sum_{j=0}^{i}p_j=\frac{r_N-\ell_N}{r_i-\ell_i}\qquad(i=0,\ldots,N). \tag*{(6)} j = 0 ∑ i p j = r i − ℓ i r N − ℓ N ( i = 0 , … , N ) . (6)
The positive, nonincreasing interval lengths make these cumulative probabilities nondecreasing and ensure that they end at 1, so they define a unique probability distribution. Every fixed interval then has expected value E j ∼ p [ ℓ j ] + ( r N − ℓ N ) \mathop{\mathbb{E}}_{j\sim p}[\ell_j]+(r_N-\ell_N) E j ∼ p [ ℓ j ] + ( r N − ℓ N ) .
Lemma 3. Let α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] . If Γ ( ℓ , r , p ) ≥ α \Gamma(\ell,r,p)\ge\alpha Γ ( ℓ , r , p ) ≥ α for every instance of nonincreasing consecutive intervals with the equalizing distribution, then Γ ( ℓ , r , p ) ≥ α \Gamma(\ell,r,p)\ge\alpha Γ ( ℓ , r , p ) ≥ α for every interval-selection instance.
Proof. The case α = 0 \alpha=0 α = 0 is immediate. Assume α > 0 \alpha>0 α > 0 and put q α = ( 1 − α ) / α q_\alpha=(1-\alpha)/\alpha q α = ( 1 − α ) / α .
Shadow intervals. Write I i = [ ℓ i , r i ] I_i=[\ell_i,r_i] I i = [ ℓ i , r i ] . For each realization j j j with p j > 0 p_j>0 p j > 0 , set
d j = max i ∣ I i ∩ [ ℓ j , ∞ ) ∣ , I ^ j = [ ℓ j , ℓ j + d j ] , d_j=\max_i\lvert I_i\cap[\ell_j,\infty)\rvert,\qquad\widehat{I}_j=[\ell_j,\ell_j+d_j], d j = i max ∣ I i ∩ [ ℓ j , ∞ )∣ , I j = [ ℓ j , ℓ j + d j ] ,
and choose i ( j ) i(j) i ( j ) attaining the maximum. We call I ^ j \widehat{I}_j I j the shadow interval for realization j j j . If d j > 0 d_j>0 d j > 0 , the interval I i ( j ) ∩ [ ℓ j , ∞ ) I_{i(j)}\cap[\ell_j,\infty) I i ( j ) ∩ [ ℓ j , ∞ ) has length d j d_j d j and begins at or to the right of ℓ j \ell_j ℓ j . It is therefore a rightward translate of I ^ j \widehat{I}_j I j , so
∣ I i ( j ) ∩ [ x , ∞ ) ∣ ≥ ∣ I ^ j ∩ [ x , ∞ ) ∣ for every x ≥ 0. (7) \lvert I_{i(j)}\cap[x,\infty)\rvert\ge\lvert\widehat{I}_j\cap[x,\infty)\rvert\qquad\text{for every }x\ge0. \tag*{(7)} ∣ I i ( j ) ∩ [ x , ∞ )∣ ≥ ∣ I j ∩ [ x , ∞ )∣ for every x ≥ 0. (7)
For d j = 0 d_j=0 d j = 0 , the same inequality is immediate. Consequently the best fixed original interval is at least as good as the best fixed shadow interval. Equation (7) also shows that the adaptive value of the shadow instance cannot exceed that of the original instance. On the other hand, shadow interval I ^ j \widehat{I}_j I j attains the original hindsight value at realization j j j , so the two adaptive values are equal, namely
∑ j p j ( ℓ j + d j ) , \sum_j p_j(\ell_j+d_j), j ∑ p j ( ℓ j + d j ) ,
the expected diagonal value of the shadow intervals. Discard zero-probability realizations and relabel the shadow intervals. It now suffices to prove the following diagonal bound for every interval family with p i > 0 p_i>0 p i > 0 :
α E j ∼ p [ r j ] ≤ E j ∼ p [ ℓ j ] + max i E j ∼ p ∣ I i ∩ [ ℓ j , ∞ ) ∣ . (8) \alpha\mathop{\mathbb{E}}_{j\sim p}[r_j]\le\mathop{\mathbb{E}}_{j\sim p}[\ell_j]+\max_i\mathop{\mathbb{E}}_{j\sim p}\lvert I_i\cap[\ell_j,\infty)\rvert. \tag*{(8)} α E j ∼ p [ r j ] ≤ E j ∼ p [ ℓ j ] + i max E j ∼ p ∣ I i ∩ [ ℓ j , ∞ )∣ . (8)
Normalizing the fixed value. Let
B = E j ∼ p [ ℓ j ] , C = E j ∼ p [ r j − ℓ j ] , M = max i E j ∼ p ∣ I i ∩ [ ℓ j , ∞ ) ∣ . B=\mathop{\mathbb{E}}_{j\sim p}[\ell_j],\qquad C=\mathop{\mathbb{E}}_{j\sim p}[r_j-\ell_j],\qquad M=\max_i\mathop{\mathbb{E}}_{j\sim p}\lvert I_i\cap[\ell_j,\infty)\rvert. B = E j ∼ p [ ℓ j ] , C = E j ∼ p [ r j − ℓ j ] , M = i max E j ∼ p ∣ I i ∩ [ ℓ j , ∞ )∣ .
Thus (7) is B + M ≥ α ( B + C ) B+M\ge\alpha(B+C) B + M ≥ α ( B + C ) . Subtracting min i ℓ i \min_i\ell_i min i ℓ i from every endpoint leaves M M M and C C C unchanged. Restoring this translation adds ( 1 − α ) min i ℓ i ≥ 0 (1-\alpha)\min_i\ell_i\ge0 ( 1 − α ) min i ℓ i ≥ 0 to the slack, so we assume min i ℓ i = 0 \min_i\ell_i=0 min i ℓ i = 0 .
Define the distribution function of the random left endpoint by
W ( x ) = Pr j ∼ p [ ℓ j ≤ x ] . W(x)=\Pr_{j\sim p}[\ell_j\le x]. W ( x ) = j ∼ p Pr [ ℓ j ≤ x ] .
Fubini’s theorem gives
M = max i ∫ ℓ i r i W ( x ) d x . (9) M=\max_i\int_{\ell_i}^{r_i}W(x)\,\mathrm{d}x. \tag*{(9)} M = i max ∫ ℓ i r i W ( x ) d x . (9)
If M = 0 M = 0 M = 0 , then p i ( r i − ℓ i ) ≤ ∫ ℓ i r i W ( x ) d x = 0 p_i(r_i-\ell_i) \le\int_{\ell_i}^{r_i} W(x)\,dx = 0 p i ( r i − ℓ i ) ≤ ∫ ℓ i r i W ( x ) d x = 0 for every i i i , so C = 0 C = 0 C = 0 and the claim follows. Assume M > 0 M > 0 M > 0 . By homogeneity, divide all endpoints by M M M and henceforth suppose M = 1 M = 1 M = 1 .
Extend each interval to the right until
∫ ℓ i r i W ( x ) d x = 1 for every i . (10) \int_{\ell_i}^{r_i} W(x)\,dx = 1 \qquad\text{for every } i. \tag*{(10)} ∫ ℓ i r i W ( x ) d x = 1 for every i . (10)
Such extensions exist because W ( x ) ≥ W ( 0 ) > 0 W(x) \ge W(0) > 0 W ( x ) ≥ W ( 0 ) > 0 . They increase C C C while keeping B B B and M = 1 M = 1 M = 1 fixed, so it is enough to prove the stronger inequality for the extended instance.
A change of coordinates. The saturation step gives every interval the same area under W W W . We use this area as a new coordinate, in which every interval has length 1. Set
H ( x ) = ∫ 0 x W ( t ) d t , X = H − 1 , g ( y ) = 1 W ( X ( y ) ) . H(x) = \int_0^x W(t)\,dt,\qquad X = H^{-1},\qquad g(y) = \frac{1}{W(X(y))}. H ( x ) = ∫ 0 x W ( t ) d t , X = H − 1 , g ( y ) = W ( X ( y )) 1 .
Then g g g is nonincreasing, g ≥ 1 g \ge1 g ≥ 1 , and g g g is eventually equal to 1; moreover, X ′ ( y ) = g ( y ) X'(y) = g(y) X ′ ( y ) = g ( y ) almost everywhere. The tail-integral formula and the substitution y = H ( x ) y = H(x) y = H ( x ) yield
B = ∫ 0 ∞ ( 1 − W ( x ) ) d x = ∫ 0 ∞ ( g ( y ) − 1 ) d y . (11) B = \int_0^\infty(1-W(x))\,dx = \int_0^\infty(g(y)-1)\,dy. \tag*{(11)} B = ∫ 0 ∞ ( 1 − W ( x )) d x = ∫ 0 ∞ ( g ( y ) − 1 ) d y . (11)
If J ∼ p J \sim p J ∼ p and S = H ( ℓ J ) S = H(\ell_J) S = H ( ℓ J ) , then (10) implies
r J − ℓ J = X ( S + 1 ) − X ( S ) = ∫ S S + 1 g ( y ) d y . r_J-\ell_J = X(S+1)-X(S) = \int_S^{S+1} g(y)\,dy. r J − ℓ J = X ( S + 1 ) − X ( S ) = ∫ S S + 1 g ( y ) d y .
For y ≥ 0 y \ge0 y ≥ 0 ,
Pr [ S ≤ y ] = Pr [ ℓ J ≤ X ( y ) ] = W ( X ( y ) ) = 1 g ( y ) . \Pr[S \le y] = \Pr[\ell_J \le X(y)] = W(X(y)) = \frac{1}{g(y)}. Pr [ S ≤ y ] = Pr [ ℓ J ≤ X ( y )] = W ( X ( y )) = g ( y ) 1 .
To average these lengths, integrate g ( y ) Pr [ S ≤ y ≤ S + 1 ] g(y)\Pr[S \le y \le S+1] g ( y ) Pr [ S ≤ y ≤ S + 1 ] over y ≥ 0 y \ge0 y ≥ 0 . The contribution from [ 0 , 1 ) [0,1) [ 0 , 1 ) is 1; shifting the remaining integral by 1 gives, with values at jump points irrelevant,
C = 1 + ∫ 0 ∞ ( 1 − g ( y + 1 ) g ( y ) ) d y . (12) C = 1 + \int_0^\infty\left(1-\frac{g(y+1)}{g(y)}\right)\,dy. \tag*{(12)} C = 1 + ∫ 0 ∞ ( 1 − g ( y ) g ( y + 1 ) ) d y . (12)
Averaging consecutive instances. The two integral formulas now connect the arbitrary instance to the structured family. Choose an integer N N N such that g ( y ) = 1 g(y) = 1 g ( y ) = 1 for y ≥ N y \ge N y ≥ N . For every s ∈ [ 0 , 1 ) s \in[0,1) s ∈ [ 0 , 1 ) , form consecutive intervals of lengths g ( s ) , g ( s + 1 ) , … , g ( s + N ) = 1 g(s),g(s+1),\ldots,g(s+N)=1 g ( s ) , g ( s + 1 ) , … , g ( s + N ) = 1 , starting at zero, and equip them with their equalizing distribution. Using the cumulative probabilities in (6) , their best fixed expected value is 1 + ∑ j = 0 N − 1 ( g ( s + j ) − 1 ) 1+\sum_{j=0}^{N-1}(g(s+j)-1) 1 + ∑ j = 0 N − 1 ( g ( s + j ) − 1 ) , and their additional expected value from adaptation is ∑ j = 0 N − 1 ( 1 − g ( s + j + 1 ) / g ( s + j ) ) \sum_{j=0}^{N-1}(1-g(s+j+1)/g(s+j)) ∑ j = 0 N − 1 ( 1 − g ( s + j + 1 ) / g ( s + j )) . Rearranging the assumed bound Γ ( ℓ , r , p ) ≥ α \Gamma(\ell,r,p) \ge\alpha Γ ( ℓ , r , p ) ≥ α for these instances gives
∑ j = 0 N − 1 ( 1 − g ( s + j + 1 ) g ( s + j ) ) ≤ q α ( 1 + ∑ j = 0 N − 1 ( g ( s + j ) − 1 ) ) . \sum_{j=0}^{N-1}\left(1-\frac{g(s+j+1)}{g(s+j)}\right)
\le q_\alpha\left(1+\sum_{j=0}^{N-1}(g(s+j)-1)\right). j = 0 ∑ N − 1 ( 1 − g ( s + j ) g ( s + j + 1 ) ) ≤ q α ( 1 + j = 0 ∑ N − 1 ( g ( s + j ) − 1 ) ) .
Integrating over s ∈ [ 0 , 1 ) s \in[0,1) s ∈ [ 0 , 1 ) and using (11) and (12) gives
C − 1 ≤ q α ( 1 + B ) . C-1 \le q_\alpha(1+B). C − 1 ≤ q α ( 1 + B ) .
Since α = 1 / ( 1 + q α ) \alpha= 1/(1+q_\alpha) α = 1/ ( 1 + q α ) ,
α ( B + C ) ≤ B + 1 = B + M . \alpha(B+C) \le B+1 = B+M. α ( B + C ) ≤ B + 1 = B + M .
Undoing the extensions, scaling, and translation proves the diagonal bound (8) . The shadow-interval comparison then gives Γ ( ℓ , r , p ) ≥ α \Gamma(\ell,r,p) \ge\alpha Γ ( ℓ , r , p ) ≥ α for the original instance, as required.
The Adaptivity Gap for Structured Interval Selection
By Lemma 3, a sharp bound for consecutive intervals with the equalizing distribution suffices for all interval instances. We prove Lemma 4 by expressing this bound as an inequality in the interval lengths. Optimizing a chain of three intervals identifies the parameters u 1 , u 2 u_1,u_2 u 1 , u 2 used in the coverage construction; we then show that longer chains cannot give a smaller adaptivity gap.
Lemma 4. For every instance ( ℓ , r , p ) (\ell,r,p) ( ℓ , r , p ) of nonincreasing consecutive intervals with the equalizing distribution, Γ ( ℓ , r , p ) ≥ ξ ⋆ \Gamma(\ell,r,p) \ge\xi^\star Γ ( ℓ , r , p ) ≥ ξ ⋆ . Equality holds for the three-interval instance [ ℓ 0 , r 0 ] = [ 0 , 1 ] [\ell_0,r_0]=[0,1] [ ℓ 0 , r 0 ] = [ 0 , 1 ] , [ ℓ 1 , r 1 ] = [ 1 , 1 + u 1 ] [\ell_1,r_1]=[1,1+u_1] [ ℓ 1 , r 1 ] = [ 1 , 1 + u 1 ] , and [ ℓ 2 , r 2 ] = [ 1 + u 1 , 1 + u 1 + u 2 ] [\ell_2,r_2]=[1+u_1,1+u_1+u_2] [ ℓ 2 , r 2 ] = [ 1 + u 1 , 1 + u 1 + u 2 ] with the equalizing distribution, where u 1 u_1 u 1 is the unique root in ( 0 , 1 ) (0,1) ( 0 , 1 ) of Φ ( x ) = x 4 + x 3 − 2 x 2 − 3 x + 2 \Phi(x)=x^4+x^3-2x^2-3x+2 Φ ( x ) = x 4 + x 3 − 2 x 2 − 3 x + 2 and u 2 = u 1 2 ( 1 + u 1 ) u_2=u_1^2(1+u_1) u 2 = u 1 2 ( 1 + u 1 ) .
Proof. Put q = ( 1 − ξ ⋆ ) / ξ ⋆ q=(1-\xi^\star)/\xi^\star q = ( 1 − ξ ⋆ ) / ξ ⋆ . Equivalently, q q q is the unique root in ( 0 , 1 ) (0,1) ( 0 , 1 ) of
Q ( q ) = q 4 + q 3 − 22 q 2 − 87 q + 24 = 0. (13) Q(q)=q^4+q^3-22q^2-87q+24=0. \tag*{(13)} Q ( q ) = q 4 + q 3 − 22 q 2 − 87 q + 24 = 0. (13)
This characterization follows from Q ( t ) = ( 1 + t ) 4 Ψ ( 1 / ( 1 + t ) ) Q(t)=(1+t)^4\Psi(1/(1+t)) Q ( t ) = ( 1 + t ) 4 Ψ ( 1/ ( 1 + t )) , Q ( 0 ) > 0 > Q ( 1 ) Q(0)>0>Q(1) Q ( 0 ) > 0 > Q ( 1 ) , and Q ′ ( t ) < 0 Q'(t)<0 Q ′ ( t ) < 0 on ( 0 , 1 ) (0,1) ( 0 , 1 ) . Evaluation at two rational points also gives
259 1000 < q < 13 50 . (14) \frac{259}{1000}<q<\frac{13}{50}. \tag*{(14)} 1000 259 < q < 50 13 . (14)
By scaling all endpoints, assume r N − ℓ N = 1 r_N-\ell_N=1 r N − ℓ N = 1 . Set d j = r j − ℓ j d_j=r_j-\ell_j d j = r j − ℓ j for j = 0 , … , N j=0,\ldots,N j = 0 , … , N . Then d 0 ≥ ⋯ ≥ d N = 1 d_0\ge\cdots\ge d_N=1 d 0 ≥ ⋯ ≥ d N = 1 , and (6) gives ∑ i = 0 j p i = 1 / d j \sum_{i=0}^{j}p_i=1/d_j ∑ i = 0 j p i = 1/ d j . For each fixed interval i i i ,
E j ∼ p ∣ [ ℓ i , r i ] ∩ [ ℓ j , ∞ ) ∣ = d i ∑ j = 0 i p j = 1. \mathbb{E}_{j\sim p}\lvert[\ell_i,r_i]\cap[\ell_j,\infty)\rvert=d_i\sum_{j=0}^{i}p_j=1. E j ∼ p ∣[ ℓ i , r i ] ∩ [ ℓ j , ∞ )∣ = d i j = 0 ∑ i p j = 1.
For realization j j j , interval j j j is a best interval in hindsight: earlier intervals have no surviving length, and later intervals have length at most d j d_j d j . Hence the best fixed expected value is B + 1 B+1 B + 1 and the adaptive expected value is B + C B+C B + C , where summation by parts gives
B = ∑ j = 0 N p j ℓ j = ∑ j = 0 N − 1 ( d j − 1 ) , C = ∑ j = 0 N p j d j = 1 + ∑ j = 0 N − 1 ( 1 − d j + 1 d j ) . B=\sum_{j=0}^{N}p_j\ell_j=\sum_{j=0}^{N-1}(d_j-1),\qquad C=\sum_{j=0}^{N}p_jd_j=1+\sum_{j=0}^{N-1}\left(1-\frac{d_{j+1}}{d_j}\right). B = j = 0 ∑ N p j ℓ j = j = 0 ∑ N − 1 ( d j − 1 ) , C = j = 0 ∑ N p j d j = 1 + j = 0 ∑ N − 1 ( 1 − d j d j + 1 ) .
Conversely, every finite chain d 0 ≥ ⋯ ≥ d N = 1 d_0\ge\cdots\ge d_N=1 d 0 ≥ ⋯ ≥ d N = 1 defines such an interval instance. Thus the claimed bound is equivalent to the numerical inequality
∑ j = 0 N − 1 ( 1 − d j + 1 d j ) ≤ q ( 1 + ∑ j = 0 N − 1 ( d j − 1 ) ) . (15) \sum_{j=0}^{N-1}\left(1-\frac{d_{j+1}}{d_j}\right)\le q\left(1+\sum_{j=0}^{N-1}(d_j-1)\right). \tag*{(15)} j = 0 ∑ N − 1 ( 1 − d j d j + 1 ) ≤ q ( 1 + j = 0 ∑ N − 1 ( d j − 1 ) ) . (15)
Define
φ ( x , y ) = 1 − y / x − q ( x − 1 ) ( x ≥ y ≥ 1 ) . \varphi(x,y)=1-y/x-q(x-1)\qquad(x\ge y\ge1). φ ( x , y ) = 1 − y / x − q ( x − 1 ) ( x ≥ y ≥ 1 ) .
The required inequality is equivalent to ∑ j = 0 N − 1 φ ( d j , d j + 1 ) ≤ q \sum_{j=0}^{N-1}\varphi(d_j,d_{j+1})\le q ∑ j = 0 N − 1 φ ( d j , d j + 1 ) ≤ q .
Two-edge chains: three intervals. We first optimize over chains x → y → 1 x\to y\to1 x → y → 1 , which correspond to three consecutive intervals. The smallest coefficient for which (15) holds for all such chains is the maximum of
R ( x , y ) = 2 − y / x − 1 / y x + y − 1 , x ≥ y ≥ 1. R(x,y)=\frac{2-y/x-1/y}{x+y-1},\qquad x\ge y\ge1. R ( x , y ) = x + y − 1 2 − y / x − 1/ y , x ≥ y ≥ 1.
On the boundary y = 1 y = 1 y = 1 , R ( x , 1 ) = ( x − 1 ) / x 2 ≤ 1 / 4 R(x,1) = (x - 1)/x^2 \le1/4 R ( x , 1 ) = ( x − 1 ) / x 2 ≤ 1/4 ; on y = x y = x y = x ,
R ( x , x ) = 1 − 1 / x 2 x − 1 ≤ x − 1 x 2 ≤ 1 4 . R(x,x) = \frac{1 - 1/x}{2x - 1} \le\frac{x - 1}{x^2} \le\frac{1}{4}. R ( x , x ) = 2 x − 1 1 − 1/ x ≤ x 2 x − 1 ≤ 4 1 .
Also R ( x , y ) ≤ 2 / x R(x,y) \le2/x R ( x , y ) ≤ 2/ x , whereas R ( 2 , 6 / 5 ) = 17 / 66 > 1 / 4 R(2,6/5) = 17/66 > 1/4 R ( 2 , 6/5 ) = 17/66 > 1/4 . Hence its maximum q 0 q_0 q 0 is attained at an interior point x > y > 1 x > y > 1 x > y > 1 . The first-order conditions give
q 0 = y x 2 = 1 y 2 − 1 x . q_0 = \frac{y}{x^2} = \frac{1}{y^2} - \frac{1}{x}. q 0 = x 2 y = y 2 1 − x 1 .
These conditions and R ( x , y ) = q 0 R(x,y) = q_0 R ( x , y ) = q 0 imply
Φ ( y / x ) = 0 , 1 x = ( y x ) 2 ( 1 + y x ) . \Phi(y/x) = 0, \qquad\frac{1}{x} = \left(\frac{y}{x}\right)^2 \left(1 + \frac{y}{x}\right). Φ ( y / x ) = 0 , x 1 = ( x y ) 2 ( 1 + x y ) .
The polynomial Φ \Phi Φ has exactly one root in ( 0 , 1 ) (0,1) ( 0 , 1 ) because Φ ( 0 ) = 2 \Phi(0) = 2 Φ ( 0 ) = 2 , Φ ( 1 ) = − 1 \Phi(1) = -1 Φ ( 1 ) = − 1 , and Φ ′ ( t ) = ( t 2 − 1 ) ( 4 t + 3 ) < 0 \Phi'(t) = (t^2 - 1)(4t + 3) < 0 Φ ′ ( t ) = ( t 2 − 1 ) ( 4 t + 3 ) < 0 for t ∈ ( 0 , 1 ) t \in(0,1) t ∈ ( 0 , 1 ) . Since 0 < y / x < 1 0 < y/x < 1 0 < y / x < 1 , uniqueness gives y / x = u 1 y/x = u_1 y / x = u 1 , and the definition of u 2 u_2 u 2 gives 1 / x = u 2 1/x = u_2 1/ x = u 2 . Consequently, q 0 = u 1 u 2 = 2 u 1 2 + 3 u 1 − 2 q_0 = u_1u_2 = 2u_1^2 + 3u_1 - 2 q 0 = u 1 u 2 = 2 u 1 2 + 3 u 1 − 2 . The identity
Q ( 2 t 2 + 3 t − 2 ) = Φ ( t ) ( 16 t 4 + 80 t 3 + 112 t 2 + 60 t + 59 ) Q(2t^2 + 3t - 2) = \Phi(t)(16t^4 + 80t^3 + 112t^2 + 60t + 59) Q ( 2 t 2 + 3 t − 2 ) = Φ ( t ) ( 16 t 4 + 80 t 3 + 112 t 2 + 60 t + 59 )
evaluated at t = u 1 t = u_1 t = u 1 shows that Q ( q 0 ) = 0 Q(q_0) = 0 Q ( q 0 ) = 0 . Since q 0 = u 1 u 2 ∈ ( 0 , 1 ) q_0 = u_1u_2 \in(0,1) q 0 = u 1 u 2 ∈ ( 0 , 1 ) , uniqueness of the root of Q Q Q gives q 0 = q q_0 = q q 0 = q . Thus
φ ( x , y ) + φ ( y , 1 ) ≤ q ( x ≥ y ≥ 1 ) , (16) \varphi(x,y) + \varphi(y,1) \le q \qquad(x \ge y \ge1), \tag*{(16)} φ ( x , y ) + φ ( y , 1 ) ≤ q ( x ≥ y ≥ 1 ) , (16)
with equality at x = 1 / u 2 x = 1/u_2 x = 1/ u 2 , y = u 1 / u 2 y = u_1/u_2 y = u 1 / u 2 . The interior maximizer also implies 0 < u 2 < u 1 < 1 0 < u_2 < u_1 < 1 0 < u 2 < u 1 < 1 . A one-edge chain is covered by y = 1 y = 1 y = 1 .
Controlling chains of arbitrary length. We next reduce longer chains to the case just analyzed. If an edge d j → d j + 1 d_j \to d_{j+1} d j → d j + 1 has nonpositive φ \varphi φ -value, delete its starting vertex. Deleting the first vertex removes a nonpositive term. Otherwise the preceding edge changes from d j − 1 → d j d_{j-1} \to d_j d j − 1 → d j to d j − 1 → d j + 1 d_{j-1} \to d_{j+1} d j − 1 → d j + 1 , increasing its value by ( d j − d j + 1 ) / d j − 1 ≥ 0 (d_j - d_{j+1})/d_{j-1} \ge0 ( d j − d j + 1 ) / d j − 1 ≥ 0 . These deletions cannot decrease the total φ \varphi φ -value. We may therefore restrict attention to chains whose edges all have positive value. A chain with no edges has value zero, and chains with one or two edges satisfy (15). Assume henceforth that the remaining chain has at least three edges.
A positive edge x → y x \to y x → y satisfies
y < h ( x ) : = ( 1 + q ) x − q x 2 ≤ T : = ( 1 + q ) 2 4 q . y < h(x) := (1 + q)x - qx^2 \le T := \frac{(1 + q)^2}{4q}. y < h ( x ) := ( 1 + q ) x − q x 2 ≤ T := 4 q ( 1 + q ) 2 .
The bounds in (13) imply T < 31 / 20 T < 31/20 T < 31/20 and that h h h is increasing on [ 1 , 31 / 20 ] [1,31/20] [ 1 , 31/20 ] . Hence
d 1 < T , d 2 < h ( d 1 ) < h ( 31 / 20 ) = 31 20 − 341 q 400 < 4 3 . d_1 < T,\qquad d_2 < h(d_1) < h(31/20) = \frac{31}{20} - \frac{341q}{400} < \frac{4}{3}. d 1 < T , d 2 < h ( d 1 ) < h ( 31/20 ) = 20 31 − 400 341 q < 3 4 .
Set L = 1 / ( 1 − q ) > 4 / 3 L = 1/(1 - q) > 4/3 L = 1/ ( 1 − q ) > 4/3 . Whenever $1 \le z \le y \le x \le L$,
φ ( x , y ) + φ ( y , z ) − φ ( x , z ) = ( y − z ) ( 1 y − 1 x ) − q ( y − 1 ) ≤ ( y − 1 ) ( 1 − 1 x − q ) ≤ 0. (17) \begin{aligned}
\varphi(x,y) + \varphi(y,z) - \varphi(x,z)
&= (y-z)\left(\frac{1}{y} - \frac{1}{x}\right) - q(y-1) \\
&\le(y-1)\left(1 - \frac{1}{x} - q\right) \le0. \tag*{(17)}
\end{aligned} φ ( x , y ) + φ ( y , z ) − φ ( x , z ) = ( y − z ) ( y 1 − x 1 ) − q ( y − 1 ) ≤ ( y − 1 ) ( 1 − x 1 − q ) ≤ 0. (17)
Thus the tail starting at d 2 d_2 d 2 can be collapsed to a single edge ending at 1. It remains to bound three-edge chains x → y → z → 1 x \to y \to z \to1 x → y → z → 1 . If y ≤ L y \le L y ≤ L , another application of (17) reduces to two edges. Suppose y ≥ L y \ge L y ≥ L . The arithmetic–geometric mean inequality gives
φ ( x , y ) + φ ( y , z ) + φ ( z , 1 ) = 3 + 3 q − q y − ( q x + y x ) − ( ( q + 1 y ) z + 1 z ) ≤ F ( y ) : = 3 + 3 q − q y − 2 q y − 2 q + 1 / y . \varphi(x,y)+\varphi(y,z)+\varphi(z,1)=3+3q-qy-\left(qx+\frac{y}{x}\right)-\left(\left(q+\frac{1}{y}\right)z+\frac{1}{z}\right)
\le F(y):=3+3q-qy-2\sqrt{qy}-2\sqrt{q+1/y}. φ ( x , y ) + φ ( y , z ) + φ ( z , 1 ) = 3 + 3 q − q y − ( q x + x y ) − ( ( q + y 1 ) z + z 1 ) ≤ F ( y ) := 3 + 3 q − q y − 2 q y − 2 q + 1/ y .
For y ≥ L > 4 / 3 y \ge L > 4/3 y ≥ L > 4/3 ,
F ′ ( y ) = − q − q / y + 1 y 2 q + 1 / y ≤ − q − q / y + y − 3 / 2 < 0. F'(y)=-q-\sqrt{q/y}+\frac{1}{y^2\sqrt{q+1/y}}\le-q-\sqrt{q/y}+y^{-3/2}<0. F ′ ( y ) = − q − q / y + y 2 q + 1/ y 1 ≤ − q − q / y + y − 3/2 < 0.
Indeed, q > 1 / 4 q>1/4 q > 1/4 implies
q y 3 / 2 + q y > 1 4 ( 4 3 ) 3 / 2 + 1 2 ⋅ 4 3 = 2 3 3 + 2 3 > 1. qy^{3/2}+\sqrt{qy}>\frac{1}{4}\left(\frac{4}{3}\right)^{3/2}+\frac{1}{2}\cdot\frac{4}{3}=\frac{2}{3\sqrt{3}}+\frac{2}{3}>1. q y 3/2 + q y > 4 1 ( 3 4 ) 3/2 + 2 1 ⋅ 3 4 = 3 3 2 + 3 2 > 1.
Since q + 1 / L = 1 q+1/L=1 q + 1/ L = 1 and q < 1 / 2 q<1/2 q < 1/2 , the point ( x , y , z ) = ( L / q , L , 1 ) (x,y,z)=(\sqrt{L/q},L,1) ( x , y , z ) = ( L / q , L , 1 ) is admissible and attains equality in both arithmetic–geometric mean inequalities. Therefore
F ( y ) ≤ F ( L ) = φ ( L / q , L ) + φ ( L , 1 ) ≤ q F(y)\le F(L)=\varphi(\sqrt{L/q},L)+\varphi(L,1)\le q F ( y ) ≤ F ( L ) = φ ( L / q , L ) + φ ( L , 1 ) ≤ q
by (16) . This proves the inequality for all finite chains. Equality holds for
d 0 = 1 / u 2 , d 1 = u 1 / u 2 , d 2 = 1. (18) d_0=1/u_2,\qquad d_1=u_1/u_2,\qquad d_2=1. \tag*{(18)} d 0 = 1/ u 2 , d 1 = u 1 / u 2 , d 2 = 1. (18)
The corresponding consecutive intervals, after scaling all endpoints by u 2 u_2 u 2 , are precisely those in Lemma 4, with the stated probabilities. The equalizing probabilities are also the weights μ 0 , μ 1 , μ 2 \mu_0,\mu_1,\mu_2 μ 0 , μ 1 , μ 2 used in the impossibility proof in Appendix A.2. This proves both the bound and its equality case.
Combining the Reductions: The Randomized Approximation Guarantee
All ingredients of the roadmap in Figure 3 are now in place. The interval-selection bound supplies the addition-robust routine assumed by the checkpoint reduction. We finish by choosing its accuracy parameter to obtain the guarantee stated in Theorem 2.
Theorem 2. For every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , there is a randomized clairvoyant algorithm for monotone submodular maximization under a cardinality constraint k k k that is O ( 1 / ε 2 ) O(1/\varepsilon^2) O ( 1/ ε 2 ) -consistent and achieves a ( ξ ⋆ − ε ) (\xi^\star-\varepsilon) ( ξ ⋆ − ε ) -approximation.
Proof. By Lemma 4, the adaptivity gap is at least ξ ⋆ \xi^\star ξ ⋆ for every instance of nonincreasing consecutive intervals with the equalizing distribution. Lemma 3 extends this bound to every interval-selection instance. Applying Lemma 2 with α = ξ ⋆ \alpha=\xi^\star α = ξ ⋆ therefore yields, for every clairvoyant addition-robustness instance, a ξ ⋆ \xi^\star ξ ⋆ -addition-robust distribution. Use an optimal solution to LP (1) to sample from this distribution, and apply Lemma 1 with γ = min { ε / 3 , 1 / 16 } \gamma=\min\{\varepsilon/3,1/16\} γ = min { ε /3 , 1/16 } . The resulting randomized clairvoyant algorithm achieves an approximation ratio of at least ξ ⋆ − 3 γ ≥ ξ ⋆ − ε \xi^\star-3\gamma\ge\xi^\star-\varepsilon ξ ⋆ − 3 γ ≥ ξ ⋆ − ε and is O ( γ − 2 ) = O ( ε − 2 ) O(\gamma^{-2})=O(\varepsilon^{-2}) O ( γ − 2 ) = O ( ε − 2 ) -consistent.
Proofs for the Tight Deterministic Bound
This appendix supplies the details deferred from § 5 . Appendix B.1 makes the rows-to-columns argument of § 5.1 precise, including the losses from bounded recourse and partially arrived stages. Appendix B.2 follows the certificate framework in § 5.2 : Appendix B.2.1 proves the mixture comparisons, Appendix B.2.2 gives the elementary certificate construction, and Appendices B.2.3 and B.2.4 prove the reduction to consistent algorithms. The three-quarter certificate proof is supplied separately, as indicated after Theorem 7.
Impossibility for Deterministic Algorithms
In this section, we present an impossibility result holding for deterministic algorithms. In particular, we construct a coverage function and a stream of elements such that any ε k \varepsilon k ε k -consistent algorithm cannot achieve more than a 3 / 4 + O ( ε ) 3/4 + O(\varepsilon) 3/4 + O ( ε ) approximation of the optimum. More formally, we have the following result, which is proved in the rest of the section.
Theorem 3. For 1 / k ≤ ε ≤ 1 1/k \le\varepsilon\le1 1/ k ≤ ε ≤ 1 , no deterministic ε k \varepsilon k ε k -consistent clairvoyant algorithm can achieve an approximation ratio better than 3 / 4 + O ( ε ) 3/4 + O(\varepsilon) 3/4 + O ( ε ) for Maximum Coverage subject to a uniform cardinality constraint k k k .
Instance Construction
Consider the universe set U U U composed by two disjoint sets: the “core” U c o r e U_{\mathrm{core}} U core and the “auxiliary” part U a u x U_{\mathrm{aux}} U aux . More precisely, the set U U U is composed by
U c o r e = { 1 , 2 , … , k 2 } U_{\mathrm{core}} = \{1, 2, \ldots, k^2\} U core = { 1 , 2 , … , k 2 } consists of exactly k 2 k^2 k 2 items, which form a k × k k \times k k × k grid.
U a u x = { u i , j ∣ i ∈ { 1 , … , k } , j ∈ { 1 , … , m } } U_{\mathrm{aux}} = \{u_{i,j} \mid i \in\{1, \ldots, k\},\ j \in\{1, \ldots, m\}\} U aux = { u i , j ∣ i ∈ { 1 , … , k } , j ∈ { 1 , … , m }} consists of k m km k m distinct, newly introduced unique items.
The total size of the universe is thus ∣ U ∣ = k 2 + k m |U| = k^2 + km ∣ U ∣ = k 2 + k m . We introduce the U \mathcal{U} U family of subsets of U U U which are used in the stream. There are two types of subsets: A A A and B B B .
Construction of A A A . The elements in A A A , indexed by ℓ ∈ { 1 , … , k } \ell\in\{1, \ldots, k\} ℓ ∈ { 1 , … , k } covers U c o r e U_{\mathrm{core}} U core “by rows”: for each ℓ \ell ℓ , the element a ℓ a_\ell a ℓ covers the ℓ \ell ℓ -th block of k k k items: a ℓ = { ( ℓ − 1 ) k + 1 , ( ℓ − 1 ) k + 2 , … , ℓ k } a_\ell= \{(\ell- 1)k + 1,(\ell- 1)k + 2, \ldots, \ell k\} a ℓ = {( ℓ − 1 ) k + 1 , ( ℓ − 1 ) k + 2 , … , ℓ k } .
By this construction, the sets a ℓ a_\ell a ℓ are pairwise disjoint and perfectly cover U c o r e U_{\mathrm{core}} U core . Selecting all k k k elements from A A A yields a coverage of f ( A ) = k 2 f(A) = k^2 f ( A ) = k 2 . Note that a ℓ ∩ U a u x = ∅ a_\ell\cap U_{\mathrm{aux}} = \varnothing a ℓ ∩ U aux = ∅ for all ℓ ∈ { 1 , … , k } \ell\in\{1, \ldots, k\} ℓ ∈ { 1 , … , k } .
Construction of B B B . Family B B B is further partitioned into m m m distinct sequences B 1 , B 2 , … , B m B_1, B_2, \ldots, B_m B 1 , B 2 , … , B m , and the sets in a given column are nested across these sequences. More precisely, B j B_j B j is composed by elements b i , j b_{i,j} b i , j , one for each column index i ∈ { 1 , … , k } i \in\{1, \ldots, k\} i ∈ { 1 , … , k } . In particular, the generic element b i , j b_{i,j} b i , j covers all the elements in the i t h i^{\mathrm{th}} i th column of U c o r e U_{\mathrm{core}} U core plus the elements in U a u x U_{\mathrm{aux}} U aux of the type { u i , 1 , … , u i , j } \{u_{i,1}, \ldots, u_{i,j}\} { u i , 1 , … , u i , j } . By design, we then have that the total cardinality of an extended set grows linearly with j j j : ∣ b i , j ∣ = k + j |b_{i,j}| = k + j ∣ b i , j ∣ = k + j .
Note, any algorithmic strategy that attempts to mix elements from A A A and elements from B B B inevitably incurs heavy redundantly-covered items within the core grid. Meanwhile, the unique extension elements u i , j u_{i,j} u i , j allow an adversary to finely tune the optimal values of the unpicked b b b -chains. For a visualization, we refer to Figure 8 .
Figure 8. Construction of the hard instance for deterministic consistent algorithms.
Streaming Arrival Sequence. The elements in A A A and B B B are presented to the algorithm into m + 1 m+1 m + 1 chronological phases. The stream Σ \Sigma Σ begins by presenting the entire collection A A A , revealing the core elements a 1 , a 2 , … , a k a_1, a_2, \ldots, a_k a 1 , a 2 , … , a k . Following A A A , the nested elements of collection B B B arrive in m m m distinct stages, ordered by their sequence depth j j j . Specifically, for each stage j j j from 1 1 1 to m m m , the stream sequentially presents the k k k elements ⟨ b 1 , j , b 2 , j , … , b k , j ⟩ \langle b_{1,j}, b_{2,j}, \ldots, b_{k,j}\rangle ⟨ b 1 , j , b 2 , j , … , b k , j ⟩ associated with that depth. Formally, letting B j = ⟨ b 1 , j , … , b k , j ⟩ B_j = \langle b_{1,j}, \ldots, b_{k,j}\rangle B j = ⟨ b 1 , j , … , b k , j ⟩ , the complete adversarial sequence is defined by the concatenation of these phases:
Σ = A ∘ B 1 ∘ B 2 ∘ ⋯ ∘ B m \Sigma= A \circ B_1 \circ B_2 \circ\cdots\circ B_m Σ = A ∘ B 1 ∘ B 2 ∘ ⋯ ∘ B m
The stream is fixed and may be known to the algorithm in advance; the argument below only relies on how slowly a consistent solution can change.
Algorithms behavior on stream Σ \Sigma Σ
Fix any deterministic (and possibly clairvoyant) algorithm for the problem. To maintain a tight competitive ratio any algorithm is forced into a stringent set of mutually exclusive choices regarding the retention of early elements. Denote with n t ( A L G ) = n t n_t(\mathrm{ALG}) = n_t n t ( ALG ) = n t the number of elements in A A A that the algorithm maintains in its solution at the end of round t t t (i.e., after the computation following the insertion of the t t h t^{\mathrm{th}} t th element of the stream). Since the algorithm and the stream are deterministic, the n t n_t n t form a deterministic sequence. We have the following lemma.
Lemma 6. Let ALG be any deterministic algorithm for the Maximum Coverage Problem subject to a uniform cardinality constraint k k k which maintains a 3 / 4 3/4 3/4 approximation to the dynamic optimum, then:
n k ( A L G ) ≥ 3 4 k n_k(\mathrm{ALG}) \ge\frac{3}{4}k n k ( ALG ) ≥ 4 3 k .
There exists a t > k t > k t > k such that n t ( A L G ) ≤ 1 3 k n_t(\mathrm{ALG}) \le\frac{1}{3}k n t ( ALG ) ≤ 3 1 k , provided that m ≥ k m \ge k m ≥ k .
Proof. The proof of the first property is immediate: the dynamic optimum after the k t h k^{\mathrm{th}} k th insertion covers all U c o r e U_{\mathrm{core}} U core , which contains k 2 k^2 k 2 elements, while the elements covered by the algorithm is exactly n k ⋅ k n_k \cdot k n k ⋅ k (as each element in A A A covers exactly a distinct row of k k k elements in U c o r e U_{\mathrm{core}} U core ).
Consider now a generic time step t t t of the form k × ( j + 1 ) k \times(j + 1) k × ( j + 1 ) , for j ≥ 1 j \ge1 j ≥ 1 , i.e., the end of stage j j j . In that moment the optimal solution consists of the last k k k elements inserted, i.e., in B j B_j B j , which cover k 2 + k × j k^2 + k \times j k 2 + k × j universe elements: these sets are disjoint, and no set inserted so far has more than k + j k + j k + j universe elements. Conversely, the value of the algorithm is
f ( A L G t ) ≤ k ⋅ n t ( A L G ) + ( k − n t ( A L G ) ) ⋅ ( j + k ) − n t ( A L G ) ( k − n t ( A L G ) ) = n t 2 + ( k − n t ) ( j + k ) \begin{aligned}
f(\mathrm{ALG}_t) \le k \cdot n_t(\mathrm{ALG}) + (k - n_t(\mathrm{ALG})) \cdot(j + k) - n_t(\mathrm{ALG})(k - n_t(\mathrm{ALG})) \\
&= n_t^2 + (k - n_t)(j + k)
\end{aligned} f ( ALG t ) ≤ k ⋅ n t ( ALG ) + ( k − n t ( ALG )) ⋅ ( j + k ) − n t ( ALG ) ( k − n t ( ALG )) = n t 2 + ( k − n t ) ( j + k )
Indeed, each one of the n t n_t n t elements in A A A maintained by the algorithm covers exactly k k k elements, and the solution has at most ( k − n t ) (k - n_t) ( k − n t ) elements from B B B . For an upper bound, these can be replaced by exactly k − n t k - n_t k − n t elements of B j B_j B j from distinct columns, whether or not all of them have arrived: an element from an earlier stage is contained in the element of B j B_j B j in its column, repeated columns are dominated by the latest set in that column, and unused slots can be filled with other columns. Each of these replacements covers j j j elements in U a u x U_{\mathrm{aux}} U aux and k k k elements in U c o r e U_{\mathrm{core}} U core , and there are exactly n t ⋅ ( k − n t ) n_t \cdot(k - n_t) n t ⋅ ( k − n t ) elements in U c o r e U_{\mathrm{core}} U core which are covered by exactly one element from A A A and one from B B B . This bound holds at every time step of stage j j j , not only at its end.
Putting everything together, we have:
3 4 ≤ f ( A L G t ) f ( O P T t ) ≤ n t 2 + ( k − n t ) ( j + k ) k 2 + k × j \frac{3}{4} \le\frac{f(\mathrm{ALG}_t)}{f(\mathrm{OPT}_t)} \le\frac{n_t^2 + (k - n_t)(j + k)}{k^2 + k \times j} 4 3 ≤ f ( OPT t ) f ( ALG t ) ≤ k 2 + k × j n t 2 + ( k − n t ) ( j + k )
For simplicity, set j = k j=k j = k , and let α t \alpha_t α t denote the fraction n t / k n_t/k n t / k . The above inequality becomes:
4 α t 2 − 8 α t + 2 ≥ 0. 4\alpha_t^2-8\alpha_t+2\ge0. 4 α t 2 − 8 α t + 2 ≥ 0.
The fraction α t \alpha_t α t is at most one, thus solving the inequality we get that α t \alpha_t α t is at most 1 − 2 / 2 ≤ 1 / 3 1-\sqrt{2}/2\le1/3 1 − 2 /2 ≤ 1/3 . This concludes the proof. □
Remark 2. Note, the constant 1 / 3 1/3 1/3 in the statement of the lemma is not important in itself. We only want to argue, via an intermediate point value argument, that the solution maintained by the algorithm contains approximately half of the elements in A A A .
We have all the ingredients to prove the main theorem of the section.
Proof of Theorem 3. Consider the instance constructed so far with m = k m=k m = k and any deterministic algorithm which is ε k \varepsilon k ε k consistent. We may assume that ε < 1 / 4 \varepsilon<1/4 ε < 1/4 , as otherwise the claim follows from the trivial upper bound of 1 1 1 on the approximation ratio. We may also assume that the algorithm maintains a 3 / 4 3/4 3/4 approximation at all times, as otherwise the claim already holds. Consistency gives ∣ n t − n t − 1 ∣ ≤ ∣ A L G t △ A L G t − 1 ∣ ≤ ε k |n_t-n_{t-1}|\le|\mathrm{ALG}_t\triangle\mathrm{ALG}_{t-1}|\le\varepsilon k ∣ n t − n t − 1 ∣ ≤ ∣ ALG t △ ALG t − 1 ∣ ≤ ε k . By an intermediate point argument and Lemma 6 there exists some time step t ≥ k t\ge k t ≥ k such that n t / k ∈ [ 1 / 2 , 1 / 2 ( 1 + 2 ε ) ] n_t/k\in[1/2,1/2(1+2\varepsilon)] n t / k ∈ [ 1/2 , 1/2 ( 1 + 2 ε )] , and t > k t>k t > k since n k ≥ 3 / 4 k > ( 1 / 2 + ε ) k n_k\ge3/4k>(1/2+\varepsilon)k n k ≥ 3/4 k > ( 1/2 + ε ) k . Such time step t t t will correspond to a batch B j B_j B j , for some j ≥ 1 j\ge1 j ≥ 1 , where the optimal solution is at least k × ( k + j − 1 ) k\times(k+j-1) k × ( k + j − 1 ) , as all of B j − 1 B_{j-1} B j − 1 (or all of A A A , if j = 1 j=1 j = 1 ) has already arrived. Conversely, by the argument in the proof of Lemma 6, the solution maintained by the algorithm has value at most:
f ( A L G t ) ≤ n t k + ( k − n t ) ( k + j ) − n t ⋅ ( k − n t ) ≤ k 2 + k j − n t j − n t k + n t 2 ≤ k 2 + k j − k j / 2 − k 2 / 2 + ( k + 2 ε k ) 2 / 4 ≤ 3 4 ( k + 2 ε k ) 2 + 1 2 k j \begin{aligned}
f(\mathrm{ALG}_t) \le n_t k + (k-n_t)(k+j)-n_t\cdot(k-n_t) \\
&\le k^2+kj-n_tj-n_tk+n_t^2 \\
&\le k^2+kj-kj/2-k^2/2+(k+2\varepsilon k)^2/4 \\
&\le\frac{3}{4}(k+2\varepsilon k)^2+\frac{1}{2}kj
\end{aligned} f ( ALG t ) ≤ n t k + ( k − n t ) ( k + j ) − n t ⋅ ( k − n t ) ≤ k 2 + k j − n t j − n t k + n t 2 ≤ k 2 + k j − k j /2 − k 2 /2 + ( k + 2 ε k ) 2 /4 ≤ 4 3 ( k + 2 ε k ) 2 + 2 1 k j
Therefore we get that
f ( A L G t ) f ( O P T t ) ≤ 3 4 ( k + 2 ε k ) 2 + 1 2 k j k × ( k + j − 1 ) ≤ 3 4 ( 1 + 2 ε ) 2 k + j k + j − 1 ≤ 3 / 4 + O ( ε + 1 / k ) ≤ 3 / 4 + O ( ε ) , \frac{f(\mathrm{ALG}_t)}{f(\mathrm{OPT}_t)}
\le\frac{\frac{3}{4}(k+2\varepsilon k)^2+\frac{1}{2}kj}{k\times(k+j-1)}
\le\frac{3}{4}(1+2\varepsilon)^2\frac{k+j}{k+j-1}
\le3/4+O(\varepsilon+1/k)\le3/4+O(\varepsilon), f ( OPT t ) f ( ALG t ) ≤ k × ( k + j − 1 ) 4 3 ( k + 2 ε k ) 2 + 2 1 k j ≤ 4 3 ( 1 + 2 ε ) 2 k + j − 1 k + j ≤ 3/4 + O ( ε + 1/ k ) ≤ 3/4 + O ( ε ) ,
where the third inequality uses j ≥ 1 j\ge1 j ≥ 1 , and the last inequality follows from the assumption of the Theorem 3.
Deterministic Clairvoyant Algorithms
Recall the window instances, mixtures, and certificates from § 5.2 . We normalize f ( ∅ ) = 0 f(\varnothing)=0 f ( ∅ ) = 0 throughout the proof; restoring a nonnegative baseline only improves the guarantees.
Window bounds and mixture comparisons
Window bounds. Fix a window instance with stages 0 , … , m 0,\ldots,m 0 , … , m , core budget κ ≥ 1 \kappa\ge1 κ ≥ 1 , and candidates O 0 , … , O m O_0,\ldots,O_m O 0 , … , O m , with the initial and terminal choices prescribed. We may keep only selected prefixes as stages, so consecutive buffers can differ by several arrivals. Set
λ j = f ( R j ) , P j = f ( O j ∪ R j ) , g j = P j − λ j , V = P 0 . (19) \lambda_j=f(R_j),\qquad P_j=f(O_j\cup R_j),\qquad g_j=P_j-\lambda_j,\qquad V=P_0. \tag*{(19)} λ j = f ( R j ) , P j = f ( O j ∪ R j ) , g j = P j − λ j , V = P 0 . (19)
Recall that P j P_j P j is the benchmark (2) at stage j j j , that is, the value attainable by the entire buffer and an optimal old core. Different labels may denote the same physical set.
Lemma B.1 (Window bounds). The values λ j \lambda_j λ j and P j P_j P j are nondecreasing in j j j , the residual g j g_j g j is nonincreasing in j j j , and for all stages s ≤ j s\le j s ≤ j ,
0 ≤ g j ≤ V ≤ P j , 0 ≤ P j − P s ≤ λ j − λ s . (20) 0\le g_j\le V\le P_j,\qquad0\le P_j-P_s\le\lambda_j-\lambda_s. \tag*{(20)} 0 ≤ g j ≤ V ≤ P j , 0 ≤ P j − P s ≤ λ j − λ s . (20) Proof. Monotonicity makes λ j \lambda_j λ j nondecreasing. Fix s ≤ j s\le j s ≤ j . Since R s ⊆ R j R_s\subseteq R_j R s ⊆ R j and O j ∩ R j = ∅ O_j\cap R_j=\varnothing O j ∩ R j = ∅ , submodularity applied to R s ∪ O j R_s\cup O_j R s ∪ O j and R j R_j R j gives
f ( R s ∪ O j ) + f ( R j ) ≥ f ( R j ∪ O j ) + f ( R s ) . f(R_s\cup O_j)+f(R_j)\ge f(R_j\cup O_j)+f(R_s). f ( R s ∪ O j ) + f ( R j ) ≥ f ( R j ∪ O j ) + f ( R s ) . Crucially, the feasible family of old cores is fixed across stages, so O j O_j O j is also feasible in the maximization (2) at stage s s s . Consequently,
P j − P s ≤ f ( R j ∪ O j ) − f ( R s ∪ O j ) P_j-P_s\le f(R_j\cup O_j)-f(R_s\cup O_j) P j − P s ≤ f ( R j ∪ O j ) − f ( R s ∪ O j ) ≤ f ( R j ) − f ( R s ) = λ j − λ s . \le f(R_j)-f(R_s)=\lambda_j-\lambda_s. ≤ f ( R j ) − f ( R s ) = λ j − λ s . Monotonicity also gives P j ≥ P s P_j\ge P_s P j ≥ P s , and hence
0 ≤ P j − P s ≤ λ j − λ s . 0\le P_j-P_s\le\lambda_j-\lambda_s. 0 ≤ P j − P s ≤ λ j − λ s .
Rearranging the upper bound shows that
g j = P j − λ j ≤ P s − λ s = g s . g_j = P_j - \lambda_j \le P_s - \lambda_s = g_s. g j = P j − λ j ≤ P s − λ s = g s .
Finally, g j ≥ 0 g_j \ge0 g j ≥ 0 because the empty core is feasible, g 0 = P 0 = V g_0 = P_0 = V g 0 = P 0 = V because R 0 = ∅ R_0 = \varnothing R 0 = ∅ and f ( ∅ ) = 0 f(\varnothing) = 0 f ( ∅ ) = 0 , and P j ≥ P 0 = V P_j \ge P_0 = V P j ≥ P 0 = V by monotonicity. Therefore,
0 ≤ g j ≤ V ≤ P j . 0 \le g_j \le V \le P_j. 0 ≤ g j ≤ V ≤ P j .
If V = 0 V = 0 V = 0 , every old set has value zero and P j = λ j P_j = \lambda_j P j = λ j ; the buffer alone suffices. Below we assume V > 0 V > 0 V > 0 .
Type and physical mixtures. The physical fractional solutions lie in the cardinality polytope
P κ = { z ∈ [ 0 , 1 ] V n o w : ∑ e ∈ V n o w z e ≤ κ } . \mathcal{P}_{\kappa} = \left\{z \in[0,1]^{V^{\mathrm{now}}} : \sum_{e \in V^{\mathrm{now}}} z_e \le\kappa\right\}. P κ = { z ∈ [ 0 , 1 ] V now : e ∈ V now ∑ z e ≤ κ } .
For a buffer Q Q Q , define the multilinear extension
F Q ( z ) = E [ f ( Q ∪ S ( z ) ) ] , F_Q(z) = \mathbb{E}\left[f(Q \cup S(z))\right], F Q ( z ) = E [ f ( Q ∪ S ( z )) ] ,
where S ( z ) ⊆ V n o w S(z) \subseteq V^{\mathrm{now}} S ( z ) ⊆ V now includes each physical element e e e independently with probability z e z_e z e . An integral core A A A is represented by its indicator vector 1 A \mathbf{1}_A 1 A , for which F Q ( 1 A ) = f ( Q ∪ A ) F_Q(\mathbf{1}_A) = f(Q \cup A) F Q ( 1 A ) = f ( Q ∪ A ) .
We restrict attention to convex combinations of the candidates O 0 , … , O m O_0,\ldots,O_m O 0 , … , O m , treating their labels as types . Recall that a mixture is a point p ∈ Δ p \in\Delta p ∈ Δ . It determines the physical fractional vector
z ( p ) = ∑ i = 0 m p i 1 O i , z e ( p ) = ∑ i : e ∈ O i p i . (21) z(p) = \sum_{i=0}^{m} p_i\mathbf{1}_{O_i}, \qquad z_e(p) = \sum_{i:e\in O_i} p_i. \tag*{(21)} z ( p ) = i = 0 ∑ m p i 1 O i , z e ( p ) = i : e ∈ O i ∑ p i . (21)
This vector is feasible because 0 ≤ z e ( p ) ≤ 1 0 \le z_e(p) \le1 0 ≤ z e ( p ) ≤ 1 and
∑ e ∈ V n o w z e ( p ) = ∑ i = 0 m p i ∣ O i ∣ ≤ κ . \sum_{e\in V^{\mathrm{now}}} z_e(p) = \sum_{i=0}^{m} p_i|O_i| \le\kappa. e ∈ V now ∑ z e ( p ) = i = 0 ∑ m p i ∣ O i ∣ ≤ κ .
Thus the type simplex parametrizes conv { 1 O 0 , … , 1 O m } ⊆ P κ \operatorname{conv}\{\mathbf{1}_{O_0},\ldots,\mathbf{1}_{O_m}\} \subseteq\mathcal{P}_{\kappa} conv { 1 O 0 , … , 1 O m } ⊆ P κ . The pure type δ i \delta_i δ i maps to the core O i O_i O i , and every affine segment in type space maps to an affine segment of feasible physical vectors. In particular, a polygonal path in Δ \Delta Δ gives a feasible fractional path with at most the same number of segments.
Feasibility alone, however, does not ensure that a path maintains enough value: the high-value regions of F Q F_Q F Q need not be convex. To certify value along our paths, we use the objective H j H_j H j of (3) . Recall that I ( p ) ⊆ { 0 , … , m } I(p) \subseteq\{0,\ldots,m\} I ( p ) ⊆ { 0 , … , m } is the random subset obtained by including each type i i i independently with probability p i p_i p i . For a fixed buffer Q Q Q , write H Q ( p ) H_Q(p) H Q ( p ) for the same objective with R j R_j R j replaced by Q Q Q ; thus H R j = H j H_{R_j} = H_j H R j = H j . Even though ∑ i p i = 1 \sum_i p_i = 1 ∑ i p i = 1 , the random set I ( p ) I(p) I ( p ) may contain zero, one, or several types. Consequently, the sampled union need not satisfy the cardinality constraint, and H j ( p ) H_j(p) H j ( p ) is generally different from the linear average ∑ i p i f ( R j ∪ O i ) \sum_i p_i f(R_j \cup O_i) ∑ i p i f ( R j ∪ O i ) . The independent samples defining H j H_j H j and F Q F_Q F Q are analytical devices; their deterministic realization is handled later.
The advantage of H j H_j H j is that it depends only on values of unions of the candidates, giving explicit formulas when few types are involved. Submodularity makes it a valid lower bound on the physical fractional objective and, as stated in § 5.2 , at most the linear average. The same formula defines H Q ( p ) H_Q(p) H Q ( p ) on the whole type cube [ 0 , 1 ] m + 1 [0,1]^{m+1} [ 0 , 1 ] m + 1 , not only on the simplex Δ \Delta Δ ; we need this because the rounding in Appendix B.2.3 also evaluates H Q H_Q H Q at vectors of mass below one.
Lemma B.2 (Mixture comparisons). Fix a buffer Q Q Q . For every p ∈ [ 0 , 1 ] m + 1 p \in[0,1]^{m+1} p ∈ [ 0 , 1 ] m + 1 with ∑ i p i ≤ 1 \sum_i p_i \le1 ∑ i p i ≤ 1 ,
F Q ( z ( p ) ) ≥ H Q ( p ) , (22) F_Q(z(p)) \ge H_Q(p), \tag*{(22)} F Q ( z ( p )) ≥ H Q ( p ) , (22) and for every mixture p ∈ Δ p \in\Delta p ∈ Δ ,
H Q ( p ) ≤ ∑ i p i f ( Q ∪ O i ) . (23) H_Q(p) \le\sum_i p_i f(Q \cup O_i). \tag*{(23)} H Q ( p ) ≤ i ∑ p i f ( Q ∪ O i ) . (23)
Proof. For (22), subadditivity after contracting Q Q Q gives
f ( Q ∪ ⋃ i ∈ I O i ) − f ( Q ) ≤ ∑ i ∈ I ( f ( Q ∪ O i ) − f ( Q ) ) . f\left(Q \cup\bigcup_{i \in I} O_i\right) - f(Q) \le\sum_{i \in I}\left(f(Q \cup O_i) - f(Q)\right). f ( Q ∪ i ∈ I ⋃ O i ) − f ( Q ) ≤ i ∈ I ∑ ( f ( Q ∪ O i ) − f ( Q ) ) .
Taking expectations and using ∑ i p i = 1 \sum_i p_i = 1 ∑ i p i = 1 proves the claim.
To prove (21), define, on the full type cube u ∈ [ 0 , 1 ] m + 1 u \in[0,1]^{m+1} u ∈ [ 0 , 1 ] m + 1 ,
Φ ( u ) = F Q ( min { 1 , ∑ i = 0 m u i 1 O i } ) . \Phi(u) = F_Q\left(\min\left\{1,\sum_{i=0}^{m}u_i\mathbf{1}_{O_i}\right\}\right). Φ ( u ) = F Q ( min { 1 , i = 0 ∑ m u i 1 O i } ) .
where the minimum is coordinatewise. The multilinear extension of a monotone submodular function has nonnegative first derivatives and nonpositive mixed second derivatives, and hence is concave along every nonnegative direction. Fixing all but one coordinate of u u u , between successive capping points, the physical vector moves in a nonnegative direction, so Φ \Phi Φ is concave there. At a capping point, the derivative loses only nonnegative contributions. Therefore Φ \Phi Φ is concave in each type coordinate separately.
Apply the chord inequality successively in all type coordinates. If B i B_i B i are independent Bernoulli variables with means p i p_i p i , this gives
Φ ( p ) ≥ E [ Φ ( B ) ] . \Phi(p) \ge\mathbb{E}[\Phi(B)]. Φ ( p ) ≥ E [ Φ ( B )] .
At a Boolean vector B B B , the capped physical vector is exactly the indicator of ⋃ i : B i = 1 O i \bigcup_{i:B_i=1} O_i ⋃ i : B i = 1 O i , so the right-hand side is H Q ( p ) H_Q(p) H Q ( p ) . Since ∑ i p i ≤ 1 \sum_i p_i \le1 ∑ i p i ≤ 1 , no capping is needed at p p p , and Φ ( p ) = F Q ( z ( p ) ) \Phi(p) = F_Q(z(p)) Φ ( p ) = F Q ( z ( p )) . This proves (21). □ \square □
At a pure type, these quantities agree:
F Q ( z ( δ i ) ) = H Q ( δ i ) = f ( Q ∪ O i ) . F_Q(z(\delta_i)) = H_Q(\delta_i) = f(Q \cup O_i). F Q ( z ( δ i )) = H Q ( δ i ) = f ( Q ∪ O i ) .
We can therefore construct fractional paths by working entirely in the type simplex: every value guarantee proved for H j H_j H j transfers to the corresponding physical vector.
Two-type interpolation. Before giving the reduction and the elementary certificate construction, we record a local estimate for mixtures supported on two types. It serves two purposes: protecting the bridges, that is, the connecting segments that join certificates for consecutive windows, and bounding the value of the half-mixture anchor in the elementary construction.
Fix a buffer Q Q Q and two cores A , B A,B A , B . For s ∈ [ 0 , 1 ] s \in[0,1] s ∈ [ 0 , 1 ] , let H Q ( A , B ; s ) H_Q(A,B;s) H Q ( A , B ; s ) denote the type objective obtained by selecting A A A with probability 1 − s 1-s 1 − s and B B B with probability s s s , independently. Thus s = 0 s=0 s = 0 represents the pure core A A A , s = 1 s=1 s = 1 represents the pure core B B B , and varying s s s traverses the edge between their type vectors.
Write
λ = f ( Q ) , a = f ( Q ∪ A ) − λ , b = f ( Q ∪ B ) − λ , \lambda= f(Q), \qquad a = f(Q \cup A) - \lambda, \qquad b = f(Q \cup B) - \lambda, λ = f ( Q ) , a = f ( Q ∪ A ) − λ , b = f ( Q ∪ B ) − λ ,
and define their residual overlap by
o = f ( Q ∪ A ) + f ( Q ∪ B ) − f ( Q ∪ A ∪ B ) − λ . o = f(Q \cup A) + f(Q \cup B) - f(Q \cup A \cup B) - \lambda. o = f ( Q ∪ A ) + f ( Q ∪ B ) − f ( Q ∪ A ∪ B ) − λ .
Equivalently, f ( Q ∪ A ∪ B ) = λ + a + b − o f(Q \cup A \cup B) = \lambda+ a + b - o f ( Q ∪ A ∪ B ) = λ + a + b − o : the term o o o measures how much the sum of the two residual values overcounts their combined contribution. Submodularity gives o ≥ 0 o \ge0 o ≥ 0 , and monotonicity gives o ≤ min ( a , b ) o \le\min(a,b) o ≤ min ( a , b ) .
Lemma B.3 (Two-type interpolation). For every s ∈ [ 0 , 1 ] s \in[0,1] s ∈ [ 0 , 1 ] ,
H Q ( A , B ; s ) = λ + ( 1 − s ) a + s b − s ( 1 − s ) o . (24) H_Q(A,B;s) = \lambda+ (1-s)a + sb - s(1-s)o. \tag*{(24)} H Q ( A , B ; s ) = λ + ( 1 − s ) a + s b − s ( 1 − s ) o . (24) Consequently, at the midpoint,
H Q ( A , B ; 1 / 2 ) ≥ λ + 1 2 ( a + b ) − 1 4 min ( a , b ) . (25) H_Q(A,B;1/2) \ge\lambda+ \frac{1}{2}(a+b) - \frac{1}{4}\min(a,b). \tag*{(25)} H Q ( A , B ; 1/2 ) ≥ λ + 2 1 ( a + b ) − 4 1 min ( a , b ) . (25) Moreover, if both cores have value at least W W W under the same fixed buffer Q Q Q , that is,
f ( Q ∪ A ) ≥ W , f ( Q ∪ B ) ≥ W , f(Q \cup A) \ge W,\qquad f(Q \cup B) \ge W, f ( Q ∪ A ) ≥ W , f ( Q ∪ B ) ≥ W , then every point along the edge has value at least 3 W / 4 3W/4 3 W /4 .
Proof. The events that neither type, only A A A , only B B B , or both types are selected have probabilities s ( 1 − s ) s(1-s) s ( 1 − s ) , ( 1 − s ) 2 (1-s)^2 ( 1 − s ) 2 , s 2 s^2 s 2 , and s ( 1 − s ) s(1-s) s ( 1 − s ) , respectively. Averaging their values gives (23). Setting s = 1 / 2 s=1/2 s = 1/2 and using o ≤ min ( a , b ) o \le\min(a,b) o ≤ min ( a , b ) gives (24).
For the last claim, put v = min ( a , b ) v=\min(a,b) v = min ( a , b ) . Since o ≤ v o \le v o ≤ v and s ( 1 − s ) ≤ 1 / 4 s(1-s) \le1/4 s ( 1 − s ) ≤ 1/4 ,
H Q ( A , B ; s ) ≥ λ + ( 1 − s ( 1 − s ) ) v ≥ λ + 3 4 v = 3 4 min { f ( Q ∪ A ) , f ( Q ∪ B ) } + 1 4 λ ≥ 3 4 W . \begin{aligned}
H_Q(A,B;s) &\ge\lambda+ (1-s(1-s))v \\
&\ge\lambda+ \frac{3}{4}v \\
&= \frac{3}{4}\min\{f(Q \cup A),f(Q \cup B)\} + \frac{1}{4}\lambda\\
&\ge\frac{3}{4}W.
\end{aligned} H Q ( A , B ; s ) ≥ λ + ( 1 − s ( 1 − s )) v ≥ λ + 4 3 v = 4 3 min { f ( Q ∪ A ) , f ( Q ∪ B )} + 4 1 λ ≥ 4 3 W .
Formula (23) expresses the value along the edge as the linear interpolation of the endpoint values, less an overlap penalty. Inequality (24) bounds the value of a half-mixture anchor using only the buffer value and the two endpoint residuals. Applying such a bound at each buffer stage will help establish persistence.
The factor 3 / 4 3/4 3/4 is sharp for this interpolation: when λ = 0 \lambda=0 λ = 0 and a = b = o = W a=b=o=W a = b = o = W , the midpoint has value exactly 3 W / 4 3W/4 3 W /4 .
The last claim of the lemma provides a safe bridge between two cores that meet a common benchmark under one objective. In the reduction, we use it to join certificates for consecutive windows. By (21), both the anchor and path estimates also hold for the corresponding physical fractional vectors. The remaining geometric task is to choose an anchor and paths that satisfy the certificate requirements across the entire window.
An elementary certificate at level 1 / 2 1/\sqrt{2} 1/ 2
We prove Theorem 6 through a more general prefix–suffix tradeoff. Recall that the anchor is the half-mixture p = 1 2 ( δ 0 + δ c ) p=\frac{1}{2}(\delta_0+\delta_c) p = 2 1 ( δ 0 + δ c ) . The partner O c O_c O c is an optimizer at a carefully chosen future stage. The selection rule balances the constraints before and after that stage; the same estimates also certify the entry and exit paths.
Fix A = O 0 A = O_0 A = O 0 and define
r j = f ( R j ∪ A ) − λ j , K j = 2 g j − r j . (26) r_j = f(R_j \cup A) - \lambda_j,\qquad K_j = 2g_j - r_j. \tag*{(26)} r j = f ( R j ∪ A ) − λ j , K j = 2 g j − r j . (26)
Here g j g_j g j is the remaining optimum and g j − r j g_j-r_j g j − r j is the initial core’s deficit; K j K_j K j is their sum. We have 0 ≤ r j ≤ g j 0 \le r_j \le g_j 0 ≤ r j ≤ g j , and
K j ≤ P j . (27) K_j \le P_j. \tag*{(27)} K j ≤ P j . (27)
To see this, note that Lemma B.1 and monotonicity give g j ≤ V ≤ f ( R j ∪ A ) = λ j + r j g_j \le V \le f(R_j \cup A) = \lambda_j + r_j g j ≤ V ≤ f ( R j ∪ A ) = λ j + r j ; therefore 2 g j − r j ≤ λ j + g j = P j 2g_j-r_j \le\lambda_j+g_j=P_j 2 g j − r j ≤ λ j + g j = P j .
Theorem B.4 (Prefix–suffix tradeoff). For 1 / 2 < β ≤ 3 / 4 1/2 < \beta\le3/4 1/2 < β ≤ 3/4 , set
γ = 4 β − 2 , D = max 0 ≤ j ≤ m { 2 K j − 4 ( 1 − β ) P j } , c = max { j : K j ≥ D } . (28) \gamma= 4\beta- 2,\qquad D = \max_{0\le j\le m}\{2K_j - 4(1-\beta)P_j\},\qquad c = \max\{j:K_j \ge D\}. \tag*{(28)} γ = 4 β − 2 , D = 0 ≤ j ≤ m max { 2 K j − 4 ( 1 − β ) P j } , c = max { j : K j ≥ D } . (28) The index c c c exists. The half-mixture of O 0 O_0 O 0 and O c O_c O c has value at least β P j \beta P_j β P j for j ≤ c j \le c j ≤ c and at least P j / ( 2 β ) P_j/(2\beta) P j / ( 2 β ) for j > c j > c j > c . It admits an entry path of one segment and an exit path of at most two segments at common level
α ( β ) = min { β , 1 / ( 2 β ) } . (29) \alpha(\beta) = \min\{\beta,1/(2\beta)\}. \tag*{(29)} α ( β ) = min { β , 1/ ( 2 β )} . (29) The envelope in (27) records the contribution needed from the partner to protect the prefix. Choosing the last eligible partner turns every later failure of eligibility into a suffix guarantee. We establish the two inequalities behind this argument before proving the theorem.
Lemma B.5 (Prefix bound). If B = O c B=O_c B = O c is the candidate at stage c c c , then at every stage j ≤ c j \le c j ≤ c ,
H R j ( A , B ; 1 / 2 ) ≥ λ j + 1 2 r j + 1 4 K c . (30) H_{R_j}(A,B;1/2) \ge\lambda_j + \frac{1}{2}r_j + \frac{1}{4}K_c. \tag*{(30)} H R j ( A , B ; 1/2 ) ≥ λ j + 2 1 r j + 4 1 K c . (30)
Proof. Diminishing returns gives
f ( R j ∪ B ) − λ j ≥ g c f(R_j \cup B) - \lambda_j \ge g_c f ( R j ∪ B ) − λ j ≥ g c
and
f ( R j ∪ A ∪ B ) − f ( R j ∪ A ) ≥ f ( R c ∪ A ∪ B ) − f ( R c ∪ A ) ≥ ( f ( R c ∪ B ) − f ( R c ) ) − ( f ( R c ∪ A ) − f ( R c ) ) ≥ g c − r c . \begin{aligned}
f(R_j \cup A \cup B) - f(R_j \cup A)
&\ge f(R_c \cup A \cup B) - f(R_c \cup A)\\
&\ge\bigl(f(R_c \cup B)-f(R_c)\bigr)-\bigl(f(R_c \cup A)-f(R_c)\bigr)\\
&\ge g_c-r_c.
\end{aligned} f ( R j ∪ A ∪ B ) − f ( R j ∪ A ) ≥ f ( R c ∪ A ∪ B ) − f ( R c ∪ A ) ≥ ( f ( R c ∪ B ) − f ( R c ) ) − ( f ( R c ∪ A ) − f ( R c ) ) ≥ g c − r c .
The sum of the values of the four equally likely type outcomes is therefore at least
λ j + ( λ j + r j ) + ( λ j + g c ) + ( λ j + r j + g c − r c ) = 4 λ j + 2 r j + K c . \lambda_j + (\lambda_j+r_j) + (\lambda_j+g_c) + (\lambda_j+r_j+g_c-r_c)
= 4\lambda_j + 2r_j + K_c. λ j + ( λ j + r j ) + ( λ j + g c ) + ( λ j + r j + g c − r c ) = 4 λ j + 2 r j + K c .
Divide by four.
Lemma B.6 (Suffix bound). Let λ , g , u , z ≥ 0 \lambda,g,u,z \ge0 λ , g , u , z ≥ 0 and 0 ≤ γ ≤ 2 0 \le\gamma\le2 0 ≤ γ ≤ 2 . If 2 g − u ≤ γ ( λ + z ) 2g-u \le\gamma(\lambda+z) 2 g − u ≤ γ ( λ + z ) , then
λ + 1 2 ( u + z ) − 1 4 min ( u , z ) ≥ 2 2 + γ ( λ + g ) . (31) \lambda+ \frac{1}{2}(u+z) - \frac{1}{4}\min(u,z) \ge\frac{2}{2+\gamma}(\lambda+g). \tag*{(31)} λ + 2 1 ( u + z ) − 4 1 min ( u , z ) ≥ 2 + γ 2 ( λ + g ) . (31)
Proof. The premise gives 2 ( λ + g ) ≤ ( 2 + γ ) λ + u + γ z 2(\lambda+g) \le(2+\gamma)\lambda+u+\gamma z 2 ( λ + g ) ≤ ( 2 + γ ) λ + u + γ z . Put w = min ( u , z ) w=\min(u,z) w = min ( u , z ) . Since the coefficients of u , z u,z u , z below are nonnegative, we get:
( 2 + γ ) [ 1 2 ( u + z ) − 1 4 w ] − u − γ z = γ 2 u + ( 1 − γ 2 ) z − 2 + γ 4 w ≥ ( γ 2 + 1 − γ 2 − 2 + γ 4 ) w = 2 − γ 4 w ≥ 0. \begin{aligned}
(2+\gamma)\left[\frac{1}{2}(u+z)-\frac{1}{4}w\right]-u-\gamma z
&=\frac{\gamma}{2}u+\left(1-\frac{\gamma}{2}\right)z-\frac{2+\gamma}{4}w\\
&\ge\left(\frac{\gamma}{2}+1-\frac{\gamma}{2}-\frac{2+\gamma}{4}\right)w
=\frac{2-\gamma}{4}w\ge0.
\end{aligned} ( 2 + γ ) [ 2 1 ( u + z ) − 4 1 w ] − u − γ z = 2 γ u + ( 1 − 2 γ ) z − 4 2 + γ w ≥ ( 2 γ + 1 − 2 γ − 4 2 + γ ) w = 4 2 − γ w ≥ 0.
Adding ( 2 + γ ) λ (2+\gamma)\lambda ( 2 + γ ) λ and dividing by ( 2 + γ ) (2+\gamma) ( 2 + γ ) proves the claim as follows.
( 2 + γ ) [ 1 2 ( u + z ) − 1 4 w ] − u − γ z ≥ 0 ⟹ ( 2 + γ ) [ λ + 1 2 ( u + z ) − 1 4 w ] − u − γ z ≥ ( 2 + γ ) λ ⟹ ( 2 + γ ) [ λ + 1 2 ( u + z ) − 1 4 w ] ≥ ( 2 + γ ) λ + u + γ z ≥ 2 ( λ + g ) ⟹ λ + 1 2 ( u + z ) − 1 4 w ≥ 2 2 + γ ( λ + g ) \begin{aligned}
(2+\gamma)\left[\frac{1}{2}(u+z)-\frac{1}{4}w\right]-u-\gamma z &\ge0 \Longrightarrow\\
(2+\gamma)\left[\lambda+\frac{1}{2}(u+z)-\frac{1}{4}w\right]-u-\gamma z &\ge(2+\gamma)\lambda\Longrightarrow\\
(2+\gamma)\left[\lambda+\frac{1}{2}(u+z)-\frac{1}{4}w\right] &\ge(2+\gamma)\lambda+u+\gamma z\ge2(\lambda+g) \Longrightarrow\\
\lambda+\frac{1}{2}(u+z)-\frac{1}{4}w &\ge\frac{2}{2+\gamma}(\lambda+g)
\end{aligned} ( 2 + γ ) [ 2 1 ( u + z ) − 4 1 w ] − u − γ z ( 2 + γ ) [ λ + 2 1 ( u + z ) − 4 1 w ] − u − γ z ( 2 + γ ) [ λ + 2 1 ( u + z ) − 4 1 w ] λ + 2 1 ( u + z ) − 4 1 w ≥ 0 ⟹ ≥ ( 2 + γ ) λ ⟹ ≥ ( 2 + γ ) λ + u + γ z ≥ 2 ( λ + g ) ⟹ ≥ 2 + γ 2 ( λ + g )
The prefix bound explains the envelope in Theorem B.4 , particularly why we define variable D D D and index c c c in this way. To obtain level β \beta β at stage j j j , we should show:
λ j + 1 2 r j + 1 4 K c ≥ β P j ⟺ K c ≥ 4 β P j − 4 λ j − 2 r j \lambda_j+\frac{1}{2}r_j+\frac{1}{4}K_c\ge\beta P_j\Longleftrightarrow K_c\ge4\beta P_j-4\lambda_j-2r_j λ j + 2 1 r j + 4 1 K c ≥ β P j ⟺ K c ≥ 4 β P j − 4 λ j − 2 r j
We rewrite this requirement as follows:
K c ≥ 4 β P j − 4 λ j − 2 r j = 4 P j − 4 λ j − 2 r j − 4 ( 1 − β ) P j = 4 g j − 2 r j − 4 ( 1 − β ) P j = 2 K j − 4 ( 1 − β ) P j \begin{aligned}
K_c &\ge4\beta P_j-4\lambda_j-2r_j\\
&=4P_j-4\lambda_j-2r_j-4(1-\beta)P_j\\
&=4g_j-2r_j-4(1-\beta)P_j\\
&=2K_j-4(1-\beta)P_j
\end{aligned} K c ≥ 4 β P j − 4 λ j − 2 r j = 4 P j − 4 λ j − 2 r j − 4 ( 1 − β ) P j = 4 g j − 2 r j − 4 ( 1 − β ) P j = 2 K j − 4 ( 1 − β ) P j
Therefore to obtain level β \beta β at stage j j j , it is sufficient that K c ≥ 2 K j − 4 ( 1 − β ) P j K_c\ge2K_j-4(1-\beta)P_j K c ≥ 2 K j − 4 ( 1 − β ) P j .
To obtain level β \beta β at stage j j j , it is sufficient that
K c ≥ 4 β P j − 4 λ j − 2 r j = 2 K j − 4 ( 1 − β ) P j . K_c\ge4\beta P_j-4\lambda_j-2r_j=2K_j-4(1-\beta)P_j. K c ≥ 4 β P j − 4 λ j − 2 r j = 2 K j − 4 ( 1 − β ) P j .
Taking the maximum of the right side gives a single requirement on the partner. In Theorem B.4 , we choose index c c c as the last partner that meets this requirement. This will ensure level β \beta β is obtained up to index c c c . The maximality in definition of c c c will turn every later failure of eligibility into the premise of Lemma B.6 (Suffix bound lemma).
Proof of Theorem B.4 . Existence of the partner and its benchmark credit. At stage zero K 0 = P 0 = V K_0=P_0=V K 0 = P 0 = V , so D ≥ γ V > 0 D\ge\gamma V>0 D ≥ γ V > 0 . If index h h h attains the maximum value of expression that defines D D D in (28) , then (27) gives
D = 2 K h − 4 ( 1 − β ) P h ≤ ( 4 β − 2 ) K h = γ K h ≤ K h , D=2K_h-4(1-\beta)P_h\le(4\beta-2)K_h=\gamma K_h\le K_h, D = 2 K h − 4 ( 1 − β ) P h ≤ ( 4 β − 2 ) K h = γ K h ≤ K h ,
D ≤ ( 4 β − 2 ) P h = γ P h . D\le(4\beta-2)P_h=\gamma P_h. D ≤ ( 4 β − 2 ) P h = γ P h .
Here 0 < γ ≤ 1 0<\gamma\le1 0 < γ ≤ 1 because β ≤ 3 / 4 \beta\le3/4 β ≤ 3/4 . The first inequality, D ≤ K h D\le K_h D ≤ K h , implies that index h h h is an eligible choice. In other words, h ∈ { j : K j ≥ D } h\in\{j:K_j\ge D\} h ∈ { j : K j ≥ D } . This ensures the set of eligible candidates is non-empty, and therefore index c c c is well-defined (it exists). Since h h h is eligible, c ≥ h c\ge h c ≥ h , and Lemma B.1 gives
P c ≥ P h ≥ D / γ . (32) P_c\ge P_h\ge D/\gamma. \tag*{(32)} P c ≥ P h ≥ D / γ . (32)
Let B = O c B=O_c B = O c .
Persistence on the prefix. For j ≤ c j\le c j ≤ c , Lemma B.5 and the definition of D D D yield
4 ( H R j ( A , B ; 1 / 2 ) − β P j ) ≥ K c − [ 2 K j − 4 ( 1 − β ) P j ] ≥ K c − D ≥ 0. \begin{aligned}
4(HR_j(A,B;1/2)-\beta P_j)&\ge K_c-\left[2K_j-4(1-\beta)P_j\right]\\
&\ge K_c-D\ge0.
\end{aligned} 4 ( H R j ( A , B ; 1/2 ) − β P j ) ≥ K c − [ 2 K j − 4 ( 1 − β ) P j ] ≥ K c − D ≥ 0.
Persistence on the suffix. For j > c j>c j > c , put u = r j u=r_j u = r j and z = f ( R j ∪ B ) − λ j z=f(R_j\cup B)-\lambda_j z = f ( R j ∪ B ) − λ j . Last eligibility, i.e. K j < D K_j<D K j < D , and (32) imply
2 g j − u = K j < D ≤ γ P c ≤ γ ( λ j + z ) . (33) 2g_j-u=K_j<D\leq\gamma P_c\leq\gamma(\lambda_j+z). \tag*{(33)} 2 g j − u = K j < D ≤ γ P c ≤ γ ( λ j + z ) . (33)
The last inequality uses monotonicity of f f f , namely f ( R j ∪ B ) ≥ f ( R c ∪ B ) f(R_j\cup B)\geq f(R_c\cup B) f ( R j ∪ B ) ≥ f ( R c ∪ B ) , and the optimality of B B B at c c c . Lemma B.6, together with (25) , gives
H R j ( A , B ; 1 / 2 ) ≥ L j : = λ j + 1 2 ( u + z ) − 1 4 min ( u , z ) ≥ 2 2 + γ P j = P j 2 β . (34) H_{R_j}(A,B;1/2)\geq L_j:=\lambda_j+\frac{1}{2}(u+z)-\frac{1}{4}\min(u,z)\geq\frac{2}{2+\gamma}P_j=\frac{P_j}{2\beta}. \tag*{(34)} H R j ( A , B ; 1/2 ) ≥ L j := λ j + 2 1 ( u + z ) − 4 1 min ( u , z ) ≥ 2 + γ 2 P j = 2 β P j . (34)
Safe entry. Use the single edge from A A A to its midpoint with B B B . Initially f ( B ) ≤ f ( A ) = V f(B)\leq f(A)=V f ( B ) ≤ f ( A ) = V , and differentiation of (24) gives
d d s H ∅ ( A , B ; s ) = f ( B ) − V − ( 1 − 2 s ) o ≤ 0 ( 0 ≤ s ≤ 1 / 2 ) . \frac{d}{ds}H_{\varnothing}(A,B;s)=f(B)-V-(1-2s)o\leq0\qquad(0\leq s\leq1/2). d s d H ∅ ( A , B ; s ) = f ( B ) − V − ( 1 − 2 s ) o ≤ 0 ( 0 ≤ s ≤ 1/2 ) .
Since the derivative is non-positive throughout the entry, from s : 0 → 1 / 2 s:0\to1/2 s : 0 → 1/2 , the entire entry is at least its final value, which is at least β V \beta V β V by the prefix calculation (Lemma B.5).
Safe exit. We start by lower bounding the value at the starting point of the exit path. We would like to show H m ( p ) ≥ α P m H_m(p)\geq\alpha P_m H m ( p ) ≥ α P m , where α = α ( β ) \alpha=\alpha(\beta) α = α ( β ) . At the terminal stage write u = r m u=r_m u = r m , z = f ( R m ∪ B ) − λ m z=f(R_m\cup B)-\lambda_m z = f ( R m ∪ B ) − λ m . If c < m c<m c < m , (34) gives L m ≥ P m / ( 2 β ) L_m\geq P_m/(2\beta) L m ≥ P m / ( 2 β ) . If c = m c=m c = m , then z = g m ≥ u z=g_m\geq u z = g m ≥ u , so
L m = λ m + 1 4 r m + 1 2 g m = λ m + 1 2 r m + 1 4 K m ≥ β P m L_m=\lambda_m+\frac{1}{4}r_m+\frac{1}{2}g_m=\lambda_m+\frac{1}{2}r_m+\frac{1}{4}K_m\geq\beta P_m L m = λ m + 4 1 r m + 2 1 g m = λ m + 2 1 r m + 4 1 K m ≥ β P m
by the same prefix calculation. We note that since c = m c=m c = m , the above inequality is equivalent to showing K c ≥ 2 K c − 4 ( 1 − β ) P c K_c\geq2K_c-4(1-\beta)P_c K c ≥ 2 K c − 4 ( 1 − β ) P c , which is achieved by definition of c c c and D D D in this case. Hence L m ≥ α P m L_m\geq\alpha P_m L m ≥ α P m in both cases.
From the midpoint move toward whichever of A , B A,B A , B has larger terminal residual v = max ( u , z ) v=\max(u,z) v = max ( u , z ) . The value is nondecreasing on that half edge because throughout the movement toward the larger endpoint, the derivative of the value for is the nonnegative endpoint difference plus ( 2 s − 1 ) o (2s-1)o ( 2 s − 1 ) o . Note that ( 2 s − 1 ) o (2s-1)o ( 2 s − 1 ) o is also non-negative since s ∈ [ 1 / 2 , 1 ] s\in[1/2,1] s ∈ [ 1/2 , 1 ] . So far, we are maintaining the lower bound value of α P m \alpha P_m α P m in our exit path. Next move from that endpoint (whichever of A , B A,B A , B has larger terminal residual v = max ( u , z ) v=\max(u,z) v = max ( u , z ) ) to the prescribed terminal optimizer O m O_m O m , whose residual is g m ≥ v g_m\geq v g m ≥ v . The second edge has value at least
λ m + [ 1 − s ( 1 − s ) ] v ≥ λ m + 3 4 v ≥ λ m + 1 2 ( u + z ) − 1 4 min ( u , z ) = L m ≥ α P m . \lambda_m+[1-s(1-s)]v\geq\lambda_m+\frac{3}{4}v\geq\lambda_m+\frac{1}{2}(u+z)-\frac{1}{4}\min(u,z)=L_m\geq\alpha P_m. λ m + [ 1 − s ( 1 − s )] v ≥ λ m + 4 3 v ≥ λ m + 2 1 ( u + z ) − 4 1 min ( u , z ) = L m ≥ α P m .
Both exit segments therefore satisfy the required terminal guarantee.
If c = 0 c=0 c = 0 , perform the calculation using a second label for the same core O 0 O_0 O 0 . Merge the two labels afterwards. For duplicate types with probabilities a , b a,b a , b , separate selection includes their common set with probability a + b − a b a+b-ab a + b − ab , whereas the merged label includes it with probability a + b a+b a + b . Monotonicity shows that merging can only increase every value. It maps affine paths to affine paths and turns the anchor into δ 0 \delta_0 δ 0 , so all the conclusions hold on the original simplex.
Finally, β \beta β increases and 1 / ( 2 β ) 1/(2\beta) 1/ ( 2 β ) decreases. Their balance is β 2 = 1 / 2 \beta^2=1/2 β 2 = 1/2 , giving 1 / ( 2 β ) = β = 1 / 2 1/(2\beta)=\beta=1/\sqrt{2} 1/ ( 2 β ) = β = 1/ 2 . The physical lift (22) preserves the anchor and its paths. □
Taking β = 1 / 2 \beta=1/\sqrt{2} β = 1/ 2 proves Theorem 6, with one entry segment and at most two exit segments. The limiting ratio 1 / 2 ≈ 0.707107 1/\sqrt{2}\approx0.707107 1/ 2 ≈ 0.707107 exceeds 1 − 1 / e ≈ 0.632121 1-1/e\approx0.632121 1 − 1/ e ≈ 0.632121 . Its source is the balance between prefix and suffix persistence. The transition analysis preserves that balance: the suffix calculation gives the stronger reserve L m L_m L m needed for the exit, and the entry is monotone toward the anchor. The rational choice β = 7 / 10 \beta=7/10 β = 7/10 gives prefix level 7 / 10 7/10 7/10 and suffix level 5 / 7 5/7 5/7 , hence a 0.7 − ϵ 0.7-\epsilon 0.7 − ϵ guarantee by the same proof.
Simultaneous deterministic rounding
We now prove Theorem 5; the proof continues in Appendix B.2.4. We first prove the simultaneous rounding statement. Fix a certificate at level α ≤ 3 / 4 \alpha\le3/4 α ≤ 3/4 with L L L segments. All its cores are subsets of the same set V n o w V_{\mathrm{now}} V now , have size at most κ \kappa κ , and have value at most V V V . Fix 0 < η < 1 / 100 0 < \eta< 1/100 0 < η < 1/100 .
Reducing number of stages to m = O ( 1 / η ) m = O(1/\eta) m = O ( 1/ η ) . We first show that we can always reduce the number of stages j = 0 , 1 , ⋯ , m j = 0,1,\cdots,m j = 0 , 1 , ⋯ , m to O ( 1 / η ) O(1/\eta) O ( 1/ η ) by losing at most O ( η ) O(\eta) O ( η ) in the approximation guarantee. We simply keep a subset of stages j ∈ { 0 , 1 , ⋯ , m } j \in\{0,1,\cdots,m\} j ∈ { 0 , 1 , ⋯ , m } as follows. We always keep the first and last stages j = 0 j=0 j = 0 and j = m j=m j = m . We keep track of the value of the buffer set R j R_j R j . For every non-negative integer i i i , we assign stage j j j to bin i i i if the value f ( R j ) f(R_j) f ( R j ) is in range [ i η V , ( i + 1 ) η V ) [i\eta V,(i+1)\eta V) [ i η V , ( i + 1 ) η V ) . From each bin with i η ≤ 3 i\eta\le3 i η ≤ 3 , we keep the first stage in it. Note that for larger value bins, the buffer set already provides a value of at least 3 V 3V 3 V , while P j ≤ λ j + V P_j \le\lambda_j + V P j ≤ λ j + V by Lemma B.1. In those stages, the approximation factor of 3 / 4 3/4 3/4 is guaranteed independent of what sets we choose for the certificate. Since the value of buffer set does not change by more than η V \eta V η V in each bin, neither does the benchmark P j P_j P j by Lemma B.1, so retaining only one stage suffices to have the same approximation guarantee with an extra loss of η \eta η . This reduction ensures that we can always work with only m = O ( 1 / η ) m = O(1/\eta) m = O ( 1/ η ) stages.
Finite tests and continuity. Every type marginal under every buffer is at most f ( O i ) ≤ V f(O_i) \le V f ( O i ) ≤ V . Consequently, on the type cube [ 0 , 1 ] m + 1 [0,1]^{m+1} [ 0 , 1 ] m + 1 ,
∣ H Q ( p ) − H Q ( q ) ∣ ≤ V ∥ p − q ∥ 1 . (35) \lvert H_Q(p)-H_Q(q)\rvert\le V\lVert p-q\rVert_1. \tag*{(35)} ∣ H Q ( p ) − H Q ( q )∣ ≤ V ∥ p − q ∥ 1 . (35)
Indeed, changing one type probability changes the expectation at a rate equal to that type’s expected marginal contribution, which lies in [ 0 , V ] [0,V] [ 0 , V ] .
If needed, approximate the original path vertices and anchor by rational simplex points within η \eta η in ℓ 1 \ell_1 ℓ 1 , retaining the same shared anchor and keeping pure endpoints fixed. For each path vertex, one can always find a simplex point with ℓ 1 \ell_1 ℓ 1 distance at most η \eta η to the vertex and also its coordinates are all rational. Linear interpolation stays within η \eta η of each original segment. To ensure segments are not too long, sub-divide each segment into sub-segments of length at most η \eta η in ℓ 1 \ell_1 ℓ 1 distance. This is doable while keeping coordinates rational, and it will increase the number of segments/vertices by a factor of 1 / η 1/\eta 1/ η . Include value tests at all sampled points, all retained anchor stages, and the additional safety points described below; include cardinality tests at the sampled points. The total number M M M of tests is
M = O ( ( L + 1 ) / η ) . (36) M = O((L+1)/\eta). \tag*{(36)} M = O (( L + 1 ) / η ) . (36)
We may increase M M M to be at least two. Each value comparison is to its corresponding ideal point; the error does not accumulate along the path. A value test at a rounded set simply checks that the realized value of the set does not decrease from its expected value by more than O ( η ) O(\eta) O ( η ) fraction. The cardinality test checks its size does not increase by more than this fraction.
Force the elements with large marginal value. Let U U U be the union of the cores used in the certificate. Set
θ = η 2 4 log ( 8 M ) , h = ⌈ 1 / θ ⌉ . \theta= \frac{\eta^2}{4\log(8M)}, \qquad h = \lceil1/\theta\rceil. θ = 4 log ( 8 M ) η 2 , h = ⌈ 1/ θ ⌉ .
Assume κ ≥ h \kappa\ge h κ ≥ h . Starting with D = ∅ D=\varnothing D = ∅ , greedily add an element of U U U while its marginal under f f f exceeds θ V \theta V θ V . The procedure selects fewer than h h h elements: otherwise its first h ≤ κ h \le\kappa h ≤ κ elements would have value greater than h θ V ≥ V h\theta V \ge V h θ V ≥ V . Thus
∣ D ∣ < h = O ( η − 2 log M ) . (37) \lvert D\rvert< h = O(\eta^{-2}\log M). \tag*{(37)} ∣ D ∣ < h = O ( η − 2 log M ) . (37)
After contracting D D D and any future buffer, every remaining singleton marginal is at most θ V \theta V θ V . Here the contraction means adding set D D D and the buffer to all sets during the entire window j = 0 , … , m j=0,\ldots,m j = 0 , … , m .
Use one threshold per element. Draw independent uniforms U e U_e U e for e ∈ U ∖ D e \in U \setminus D e ∈ U ∖ D , shared by all sampled points, both paths, and the anchor. For a type vector p p p of mass at most one, set
T ( p ) = D ∪ { e ∈ U ∖ D : U e ≤ z e ( p ) } . T(p)=D\cup\{e\in U\setminus D:U_e\le z_e(p)\}. T ( p ) = D ∪ { e ∈ U ∖ D : U e ≤ z e ( p )} .
Forcing D D D can only improve the expected value. Hence Lemma B.2 gives E [ f ( Q ∪ T ( p ) ) ] ≥ H Q ( p ) \mathbb{E}[f(Q\cup T(p))]\ge H_Q(p) E [ f ( Q ∪ T ( p ))] ≥ H Q ( p ) . We use two standard concentration bounds.
Lemma B.7 (Concentration). Let G G G be a nonnegative monotone submodular set function whose marginal values are at most c > 0 c>0 c > 0 , let S S S be a random set containing each element independently, and put μ = E [ G ( S ) ] \mu=\mathbb{E}[G(S)] μ = E [ G ( S )] . Then, for 0 < a < μ 0<a<\mu 0 < a < μ ,
P { G ( S ) ≤ μ − a } ≤ exp ( − a 2 2 c μ ) . (38) \mathbb{P}\{G(S)\le\mu-a\}\le\exp\left(-\frac{a^2}{2c\mu}\right). \tag*{(38)} P { G ( S ) ≤ μ − a } ≤ exp ( − 2 c μ a 2 ) . (38) If X X X is a sum of independent Bernoulli variables with mean at most κ \kappa κ , then, for 0 < η ≤ 1 0<\eta\le1 0 < η ≤ 1 ,
P { X > ( 1 + η ) κ } ≤ e − η 2 κ / 3 . (39) \mathbb{P}\{X>(1+\eta)\kappa\}\le e^{-\eta^2\kappa/3}. \tag*{(39)} P { X > ( 1 + η ) κ } ≤ e − η 2 κ /3 . (39)
Proof. The first bound is Vondrak [ [41 ] , applied to G / c G/c G / c with δ = a / μ \delta=a/\mu δ = a / μ . The second is the standard multiplicative Chernoff bound, applied with the upper bound κ \kappa κ on the mean. □
To bound the deviation independently of ∣ U ∣ |U| ∣ U ∣ , put G Q ( S ) = f ( Q ∪ D ∪ S ) − f ( Q ∪ D ) G_Q(S)=f(Q\cup D\cup S)-f(Q\cup D) G Q ( S ) = f ( Q ∪ D ∪ S ) − f ( Q ∪ D ) . Submodularity gives G Q ( S ) ≤ f ( S ) G_Q(S)\le f(S) G Q ( S ) ≤ f ( S ) . Partitioning S S S into sets of size at most κ \kappa κ and using subadditivity yields
G Q ( S ) ≤ f ( S ) ≤ ⌈ ∣ S ∣ κ ⌉ V ≤ ( 1 + ∣ S ∣ κ ) V . G_Q(S)\le f(S)\le\left\lceil\frac{|S|}{\kappa}\right\rceil V\le\left(1+\frac{|S|}{\kappa}\right)V. G Q ( S ) ≤ f ( S ) ≤ ⌈ κ ∣ S ∣ ⌉ V ≤ ( 1 + κ ∣ S ∣ ) V .
The random part of T ( p ) T(p) T ( p ) has expected size at most κ \kappa κ , so E [ G Q ] ≤ 2 V \mathbb{E}[G_Q]\le2V E [ G Q ] ≤ 2 V . After contracting D D D , the marginal values of G Q G_Q G Q are at most θ V \theta V θ V , and the random part of T ( p ) T(p) T ( p ) contains each element independently. Since H Q ( p ) ≤ E [ f ( Q ∪ T ( p ) ) ] = f ( Q ∪ D ) + E [ G Q ] H_Q(p)\le\mathbb{E}[f(Q\cup T(p))]=f(Q\cup D)+\mathbb{E}[G_Q] H Q ( p ) ≤ E [ f ( Q ∪ T ( p ))] = f ( Q ∪ D ) + E [ G Q ] , applying (37) with c = θ V c=\theta V c = θ V and a = η V a=\eta V a = η V gives
P { f ( Q ∪ T ( p ) ) < H Q ( p ) − η V } ≤ exp { − η 2 / ( 4 θ ) } = 1 8 M . (40) \mathbb{P}\{f(Q\cup T(p))<H_Q(p)-\eta V\}\le\exp\{-\eta^2/(4\theta)\}=\frac{1}{8M}. \tag*{(40)} P { f ( Q ∪ T ( p )) < H Q ( p ) − η V } ≤ exp { − η 2 / ( 4 θ )} = 8 M 1 . (40)
If the residual mean is at most η V \eta V η V , the corresponding downward deviation is impossible, so the same assertion holds. The size of the random part of T ( p ) T(p) T ( p ) is a sum of independent Bernoulli variables, so (38) gives
P { ∣ T ( p ) ∖ D ∣ > ( 1 + η ) κ } ≤ e − η 2 κ / 3 ≤ 1 8 M , (41) \mathbb{P}\{|T(p)\setminus D|>(1+\eta)\kappa\}\le e^{-\eta^2\kappa/3}\le\frac{1}{8M}, \tag*{(41)} P { ∣ T ( p ) ∖ D ∣ > ( 1 + η ) κ } ≤ e − η 2 κ /3 ≤ 8 M 1 , (41)
using κ ≥ h ≥ 4 η − 2 log ( 8 M ) \kappa\ge h\ge4\eta^{-2}\log(8M) κ ≥ h ≥ 4 η − 2 log ( 8 M ) . Note that for smaller values of κ \kappa κ (and hence k k k ), the consistency objective is achieved trivially since the change from any solution to the next is 2 k 2k 2 k -consistent.
On an original segment with endpoints p , q p,q p , q , each physical probability varies affinely. The expected number of membership changes is
∑ e ∉ D ∣ z e ( p ) − z e ( q ) ∣ ≤ ∑ i ∣ p i − q i ∣ ∣ O i ∣ ≤ κ ∥ p − q ∥ 1 ≤ 2 κ . \sum_{e\notin D}|z_e(p)-z_e(q)|\le\sum_i|p_i-q_i||O_i|\le\kappa\|p-q\|_1\le2\kappa. e ∈ / D ∑ ∣ z e ( p ) − z e ( q ) ∣ ≤ i ∑ ∣ p i − q i ∣∣ O i ∣ ≤ κ ∥ p − q ∥ 1 ≤ 2 κ .
Thus the expected number on both paths is at most 2 L κ 2L\kappa 2 L κ . Markov’s inequality shows that it exceeds 8 L κ 8L\kappa 8 L κ with probability at most 1 / 4 1/4 1/4 . Together with all the value and cardinality tests, the union bound has probability below one. Fix one successful threshold assignment deterministically. With rational sampled probabilities there are finitely many threshold cells, so exhaustive search suffices. Rational certificates with the allowed slack can likewise be found by enumerating rational path vertices and checking a sufficiently fine mesh using (35) . No efficiency bound is claimed.
Protect every intermediate set. For adjacent subdivisions p p p , q q q , put v i = min ( p i , q i ) v_i = \min(p_i,q_i) v i = min ( p i , q i ) . This is a type vector of mass at most one, and ∥ p − v ∥ 1 ≤ η \lVert p-v\rVert_1 \le\eta ∥ p − v ∥ 1 ≤ η . Include the value test for T ( v ) T(v) T ( v ) under the objective used on that path. Since z e ( v ) ≤ min ( z e ( p ) , z e ( q ) ) z_e(v) \le\min(z_e(p),z_e(q)) z e ( v ) ≤ min ( z e ( p ) , z e ( q )) , common thresholds ensure
T ( v ) ⊆ T ( p ) ∩ T ( q ) . T(v) \subseteq T(p) \cap T(q). T ( v ) ⊆ T ( p ) ∩ T ( q ) .
Delete T ( p ) ∖ T ( q ) T(p) \setminus T(q) T ( p ) ∖ T ( q ) , then insert T ( q ) ∖ T ( p ) T(q) \setminus T(p) T ( q ) ∖ T ( p ) . Every intermediate set contains T ( v ) T(v) T ( v ) and has size at most the larger endpoint size. The Lipschitz loss to v v v , the rationalization loss, and the concentration loss are together O ( η ) V O(\eta)V O ( η ) V .
At a pure type δ i \delta_i δ i , T ( δ i ) = O i ∪ D T(\delta_i) = O_i \cup D T ( δ i ) = O i ∪ D . Add D D D at the initial pure endpoint and remove it at the terminal pure endpoint; these extra operations preserve the endpoint value. We obtain a single rounded anchor with coupled entry and exit, such that
core size ≤ ( 1 + η ) κ + h , (42) \text{core size} \le(1+\eta)\kappa+ h, \tag*{(42)} core size ≤ ( 1 + η ) κ + h , (42)
total operations ≤ 8 L κ + 2 h . (43) \text{total operations} \le8L\kappa+ 2h. \tag*{(43)} total operations ≤ 8 L κ + 2 h . (43)
The anchor is ( α − O ( η ) ) (\alpha- O(\eta)) ( α − O ( η )) -good at every buffer stage, and every entry and exit intermediate set loses at most O ( η ) V O(\eta)V O ( η ) V from its required value. A one-edge bridge between pure cores is rounded by the same argument, using its own forced set and thresholds. The estimates remain valid when the fixed buffer overlaps a core: its elements then have zero marginal value after contraction. The pure endpoints allow these forced sets to be removed before the next is added.
The protected schedule and the recourse calculation
We complete the proof of Theorem 5. Write X t X_t X t for the arrived prefix and
OPT t ( r ) = max { f ( A ) : A ⊆ X t , ∣ A ∣ ≤ r } , \operatorname{OPT}_t(r) = \max\{f(A) : A \subseteq X_t,\ |A| \le r\}, OPT t ( r ) = max { f ( A ) : A ⊆ X t , ∣ A ∣ ≤ r } ,
so that OPT t ( k ) = f ( OPT t ) \operatorname{OPT}_t(k) = f(\operatorname{OPT}_t) OPT t ( k ) = f ( OPT t ) . First, for 1 ≤ r ≤ k 1 \le r \le k 1 ≤ r ≤ k ,
OPT t ( r ) ≥ r k OPT t ( k ) . (44) \operatorname{OPT}_t(r) \ge\frac{r}{k}\operatorname{OPT}_t(k). \tag*{(44)} OPT t ( r ) ≥ k r OPT t ( k ) . (44)
Indeed, for a normalized monotone submodular function and a set S S S , diminishing returns and telescoping imply
∑ e ∈ S [ f ( S ) − f ( S ∖ { e } ) ] ≤ f ( S ) . \sum_{e \in S}\left[f(S)-f(S\setminus\{e\})\right] \le f(S). e ∈ S ∑ [ f ( S ) − f ( S ∖ { e }) ] ≤ f ( S ) .
Some deletion therefore keeps at least ( ∣ S ∣ − 1 ) / ∣ S ∣ (|S|-1)/|S| ( ∣ S ∣ − 1 ) /∣ S ∣ of the value. Repeated deletion from an optimal set of size at most k k k proves (43).
Parameters and transition intervals. Fix sufficiently small η > 0 \eta> 0 η > 0 and put
κ = ⌊ ( 1 − 10 η ) k ⌋ , b = ⌊ η k ⌋ , J = ⌈ 4 / η ⌉ , ℓ = ⌊ b / J ⌋ . \kappa= \lfloor(1-10\eta)k\rfloor,\qquad b = \lfloor\eta k\rfloor,\qquad J = \lceil4/\eta\rceil,\qquad\ell= \lfloor b/J\rfloor. κ = ⌊( 1 − 10 η ) k ⌋ , b = ⌊ η k ⌋ , J = ⌈ 4/ η ⌉ , ℓ = ⌊ b / J ⌋ .
For now assume k ≥ K η = c η − 3 log ( e / η ) k \ge K_{\eta} = c\eta^{-3}\log(e/\eta) k ≥ K η = c η − 3 log ( e / η ) for a sufficiently large constant c c c . Then κ ≥ 1 \kappa\ge1 κ ≥ 1 and ℓ = Θ ( η 2 k ) \ell= \Theta(\eta^{2}k) ℓ = Θ ( η 2 k ) . Keep the rolling buffer
R t = X t ∖ X max { 0 , t − 4 b } , R_t = X_t \setminus X_{\max\{0,t-4b\}}, R t = X t ∖ X m a x { 0 , t − 4 b } ,
which uses at most 4 b 4b 4 b slots and changes by at most two elements per update.
For each block starting at b i = i b b_i = ib b i = ib , i ≥ 1 i \ge1 i ≥ 1 , inspect the J J J successive intervals [ b i + j ℓ , b i + ( j + 1 ) ℓ ] [b_i+j\ell,b_i+(j+1)\ell] [ b i + j ℓ , b i + ( j + 1 ) ℓ ] , 0 ≤ j < J 0 \le j < J 0 ≤ j < J . Choose the first interval [ u , u + ℓ ] [u,u+\ell] [ u , u + ℓ ] for which
OPT u + ℓ ( k ) ≤ ( 1 + η ) OPT u ( k ) . (45) \operatorname{OPT}_{u+\ell}(k) \le(1+\eta)\operatorname{OPT}_{u}(k). \tag*{(45)} OPT u + ℓ ( k ) ≤ ( 1 + η ) OPT u ( k ) . (45)
If none exists, choose the last interval. Let τ i \tau_i τ i be the chosen start. The intervals lie within their blocks and do not overlap in their interiors.
When no interval is stable, the preceding J − 1 J-1 J − 1 increases give
OPT τ i ( k ) ≥ ( 1 + η ) J − 1 OPT b i ( k ) ≥ 4 OPT b i ( k ) . \operatorname{OPT}_{\tau_i}(k) \ge(1+\eta)^{J-1}\operatorname{OPT}_{b_i}(k) \ge4\operatorname{OPT}_{b_i}(k). OPT τ i ( k ) ≥ ( 1 + η ) J − 1 OPT b i ( k ) ≥ 4 OPT b i ( k ) .
For the last inequality, Bernoulli’s inequality gives ( 1 + η ) J − 1 ≥ 1 + ( J − 1 ) η ≥ 5 − η > 4 (1+\eta)^{J-1} \ge1+(J-1)\eta\ge5-\eta> 4 ( 1 + η ) J − 1 ≥ 1 + ( J − 1 ) η ≥ 5 − η > 4 . For every t ∈ [ τ i , τ i + ℓ ] t \in[\tau_i,\tau_i+\ell] t ∈ [ τ i , τ i + ℓ ] , let B t = X t ∖ X b i B_t=X_t\setminus X_{b_i} B t = X t ∖ X b i . Split an optimal solution into its old part and its part in B t B_t B t . Subadditivity and monotonicity imply
f ( B t ) ≥ OPT t ( k ) − OPT b i ( k ) ≥ 3 4 OPT t ( k ) . (46) f(B_t) \ge\operatorname{OPT}_{t}(k)-\operatorname{OPT}_{b_i}(k) \ge\frac{3}{4}\operatorname{OPT}_{t}(k). \tag*{(46)} f ( B t ) ≥ OPT t ( k ) − OPT b i ( k ) ≥ 4 3 OPT t ( k ) . (46)
Moreover B t ⊆ R t B_t \subseteq R_t B t ⊆ R t . Thus each chosen interval is protected either by (44) or by the buffer itself. This includes the case OPT b i ( k ) = 0 \operatorname{OPT}_{b_i}(k)=0 OPT b i ( k ) = 0 .
The local windows. Window i i i freezes N i = X τ i N_i=X_{\tau_i} N i = X τ i as its set V n o w V_{\mathrm{now}} V now and uses the growing buffer R i ( t ) = X t ∖ X τ i R_i(t)=X_t\setminus X_{\tau_i} R i ( t ) = X t ∖ X τ i for τ i ≤ t ≤ τ i + 1 \tau_i\le t\le\tau_{i+1} τ i ≤ t ≤ τ i + 1 . Its initial value is V i = OPT τ i ( κ ) V_i=\operatorname{OPT}_{\tau_i}(\kappa) V i = OPT τ i ( κ ) . Its local benchmark satisfies
P i ( t ) ≥ OPT t ( κ ) , (47) P_i(t) \ge\operatorname{OPT}_{t}(\kappa), \tag*{(47)} P i ( t ) ≥ OPT t ( κ ) , (47)
because the old part of any size-κ \kappa κ solution is a feasible old core and all of its new elements lie in R i ( t ) R_i(t) R i ( t ) .
Choose a prescribed initial optimizer O i O_i O i of value V i V_i V i and a prescribed terminal old-core optimizer C i C_i C i for the buffer at τ i + 1 \tau_{i+1} τ i + 1 ; these are the candidates O 0 O_0 O 0 and O m O_m O m of window i i i . Retain O ( 1 / η ) O(1/\eta) O ( 1/ η ) stages and apply the fractional hypothesis, then Appendix § 9 .§ 4.3 . Denote the rounded anchor by T i T_i T i . After transition i i i , hold T i T_i T i until transition i + 1 i+1 i + 1 . If V i = 0 V_i=0 V i = 0 , take the old core empty: all its residuals are zero and the local buffer gives the full benchmark.
Joining two windows. During transition i i i , for i ≥ 2 i\ge2 i ≥ 2 , execute the following ordered list: the old exit from T i − 1 T_{i-1} T i − 1 to C i − 1 C_{i-1} C i − 1 ; a bridge from C i − 1 C_{i-1} C i − 1 to O i O_i O i ; the new entry from O i O_i O i to T i T_i T i . The old exit is evaluated under the fixed buffer Q = R i − 1 ( τ i ) Q=R_{i-1}(\tau_i) Q = R i − 1 ( τ i ) and gives
α P i − 1 ( τ i ) − O ( η ) V i − 1 ≥ ( α − O ( η ) ) V i . \alpha P_{i-1}(\tau_i)-O(\eta)V_{i-1} \ge(\alpha-O(\eta))V_i. α P i − 1 ( τ i ) − O ( η ) V i − 1 ≥ ( α − O ( η )) V i .
since P i − 1 ( τ i ) ≥ V i P_{i-1}(\tau_i)\ge V_i P i − 1 ( τ i ) ≥ V i and V i − 1 ≤ V i V_{i-1}\le V_i V i − 1 ≤ V i . Both bridge endpoints, under this same Q Q Q , have value at least V i V_i V i . Lemma B.3 therefore gives 3 V i / 4 3V_i/4 3 V i /4 before rounding. Round this bridge in old set N i N_i N i , with normalization V i V_i V i ; it loses O ( η ) V i O(\eta)V_i O ( η ) V i . Finally the new entry gives ( α − O ( η ) ) V i (\alpha-O(\eta))V_i ( α − O ( η )) V i even with an empty buffer. All elements used have arrived by τ i \tau_i τ i .
At the shared pure cores, remove the previous forced set before adding the next. During this operation the pure core remains present, so the endpoint value is preserved and the forced sets do not accumulate. A zero-value old window needs no rounding; if the new value is positive, its old terminal endpoint is still protected by Q Q Q and the same bridge argument applies. If the new value is also zero, the newly arriving buffer supplies all value during the transition.
The required buffer Q Q Q remains inside R t R_t R t until the transition ends: τ i + ℓ − τ i − 1 ≤ 2 b \tau_i+\ell-\tau_{i-1}\le2b τ i + ℓ − τ i − 1 ≤ 2 b . The same age bound protects R i ( t ) R_i(t) R i ( t ) throughout the subsequent holding interval. Additional arrivals can only improve the values of the protected sets.
On a stable transition interval, (44) and (45) give
f ( ALG t ) ≥ ( α − O ( η ) ) V i ≥ ( α − O ( η ) ) κ k ( 1 + η ) OPT t ( k ) = ( α − O ( η ) ) OPT t ( k ) . \begin{aligned}
f(\operatorname{ALG}_t) \ge(\alpha-O(\eta))V_i \\
&\ge(\alpha-O(\eta))\frac{\kappa}{k(1+\eta)}\operatorname{OPT}_t(k) = (\alpha-O(\eta))\operatorname{OPT}_t(k).
\end{aligned} f ( ALG t ) ≥ ( α − O ( η )) V i ≥ ( α − O ( η )) k ( 1 + η ) κ OPT t ( k ) = ( α − O ( η )) OPT t ( k ) .
On an unstable transition interval, (46) gives the stronger 3/4 guarantee. During holding intervals, anchor persistence, (47) , and thinning give the same ( α − O ( η ) ) (\alpha-O(\eta)) ( α − O ( η )) ratio directly.
Capacity, worst-case changes, and endpoints. After retaining the stages, L = O ( 1 / η ) L=O(1/\eta) L = O ( 1/ η ) and the rounding test count is M = O ( η − 2 ) M=O(\eta^{-2}) M = O ( η − 2 ) . Increasing c c c in K η K_\eta K η ensures that every forced set has size at most η k \eta k η k and that all rounding premises hold. Equations (42) and the buffer size give
∣ ALG t ∣ ≤ ( 1 + η ) κ + η k + 4 b ≤ k . |\operatorname{ALG}_t| \le(1+\eta)\kappa+\eta k+4b\le k. ∣ ALG t ∣ ≤ ( 1 + η ) κ + η k + 4 b ≤ k .
Deletion-first updates preserve the same bound at every intermediate operation. The concatenated list at a transition contains
O ( L κ + η − 2 log ( e / η ) ) = O ( k / η ) O(L\kappa+\eta^{-2}\log(e/\eta))=O(k/\eta) O ( L κ + η − 2 log ( e / η )) = O ( k / η )
operations. Execute at most the ceiling of this count divided by ℓ \ell ℓ at each of the ℓ \ell ℓ actual updates. This gives O ( η − 3 ) O(\eta^{-3}) O ( η − 3 ) operations per update, plus at most two buffer changes. Full symmetric difference is at most the number of insertions and deletions performed.
Before the first transition ends there are at most 2 b 2b 2 b arrived elements, and the rolling buffer contains the entire prefix. This protects initialization: construct O 1 O_1 O 1 and then follow its rounded entry during that interval, adding at most κ \kappa κ extra operations. For a finite stream, append enough formal zero-value arrivals to define the final windows and transitions, then restrict the sequence to the actual stream. Every core used before the real end consists of elements already present at its window start; the padding does not authorize any unarrived real element.
For k < K η k<K_\eta k < K η , recompute an exact optimum at each update, with recourse at most 2 k = O ( η − 3 log ( e / η ) ) 2k=O(\eta^{-3}\log(e/\eta)) 2 k = O ( η − 3 log ( e / η )) . The constant consistency in this case is implied due to the constant upper bound on k k k . Choose η \eta η a sufficiently small multiple of ε \varepsilon ε . For ε < α ≤ 3 / 4 \varepsilon<\alpha\le3/4 ε < α ≤ 3/4 , log ( e / ε ) = O ( log ( 1 / ε ) ) \log(e/\varepsilon)=O(\log(1/\varepsilon)) log ( e / ε ) = O ( log ( 1/ ε )) , as used in the theorem, and for ε ≥ α \varepsilon\ge\alpha ε ≥ α , the empty solution already gives the claimed nonpositive approximation guarantee with zero recourse. This proves Theorem 5. If f ( ∅ ) > 0 f(\varnothing)>0 f ( ∅ ) > 0 , apply the argument to f − f ( ∅ ) f-f(\varnothing) f − f ( ∅ ) ; restoring the baseline only improves an approximation ratio at most one.