Introduction
Many Web applications repeatedly need to select a high-quality subset of items from a large and continuously changing collection. For example, a Web platform may need to select a set of articles, products, advertisements, or recommended items to display to users. The quality of a selected set is often naturally modeled by a submodular function: adding an item provides diminishing marginal benefit as increasingly similar or redundant items are already selected. Submodular objectives have been widely used to model coverage and information-gathering objectives [6 ] , as well as diversity in recommendation and search [5 , 1 ] .
In practice, however, a platform cannot select an arbitrary subset of items. The selected items must satisfy combinatorial constraints reflecting limited display space, business rules, or diversity requirements. Matroid constraints provide a particularly natural and expressive way to model such requirements. For example, a partition matroid can impose quotas on different categories or content providers, such as allowing at most r i r_i r i items from category i i i . The rank of the matroid then has a direct interpretation as the total number of available selection slots. More general matroids can capture overlapping eligibility and resource constraints while allowing the algorithm to exchange selected items in a structured way. Thus, submodular maximization under a matroid constraint provides a general framework for balancing the quality of a selection with diversity and resource limitations that arise naturally in Web applications.
The role of the matroid rank is particularly intuitive in recommendation and content-selection systems. Suppose a platform must display at most k k k items. A uniform matroid of rank k k k models the basic capacity constraint that at most k k k items can be selected. A partition matroid can further distribute these k k k slots across categories or providers, for example by requiring that no category contribute more than a specified number of items. The submodular objective can then favor selections that cover diverse topics, users, or interests. In this setting, the rank represents the scale of the selection that the platform can maintain, while the matroid structure specifies how those limited slots may be allocated. More sophisticated matroids can similarly represent multiple interacting resource or eligibility constraints.
A defining characteristic of many Web applications is that their underlying collections and interactions evolve continuously. For example, in recommender systems, new items are introduced and users continuously interact with existing items, changing the interaction graph and the information available for recommendation [2 , 3 ] . Real-world recommendation systems must also adapt to changing item-popularity trends while scaling to millions of items [4 ] . These changes can affect both the objective value of a selected set and its feasibility under application-specific constraints. Recomputing an approximately optimal solution from scratch after every insertion or deletion can be prohibitively expensive at Web scale. This motivates the fully dynamic version of submodular maximization, in which the active ground set changes over time and the algorithm must efficiently maintain a near-optimal feasible solution after each update.
For instance, consider a recommendation platform that maintains a set of items to display while promoting diversity across categories or providers [1 ] . The utility of a recommendation set can be modeled by a submodular function that captures user engagement, coverage, or diversity, while category or provider quotas can be represented by a matroid constraint. As new items become available and existing items are removed, the platform must continuously update its recommendations to adapt to the changing collection [3 , 2 ] . Ideally, these updates should be processed in time that is polylogarithmic in the size of the system, rather than in time that grows with the number of available items or with the matroid rank.
Our work addresses this challenge by developing a fully dynamic algorithm for monotone submodular maximization under a matroid constraint with expected amortized update time p o l y ( log n , ϵ − 1 ) \mathrm{poly}(\log n,\epsilon^{-1}) poly ( log n , ϵ − 1 ) , independent of the matroid rank. This result provides a general algorithmic framework for maintaining approximately optimal constrained selections in dynamic Web environments, where both the collection of available items and the feasible solution may change continuously.
Submodular functions naturally express the principle of diminishing returns: the gain from adding an element decreases as the chosen set grows. Formally, a set function f : 2 N → R + f: 2^{\mathcal{N}} \rightarrow \mathbb{R}^+ f : 2 N → R + defined on a finite ground set N \mathcal{N} N is submodular if, for every A ⊆ B ⊆ N A \subseteq B \subseteq \mathcal{N} A ⊆ B ⊆ N and element e ∈ N ∖ B e \in \mathcal{N} \setminus B e ∈ N ∖ B , f ( A ∪ { e } ) − f ( A ) ≥ f ( B ∪ { e } ) − f ( B ) f(A \cup \{e\}) - f(A) \geq f(B \cup \{e\}) - f(B) f ( A ∪ { e }) − f ( A ) ≥ f ( B ∪ { e }) − f ( B ) . If, in addition, f ( A ) ≤ f ( B ) f(A) \le f(B) f ( A ) ≤ f ( B ) for all A ⊆ B A \subseteq B A ⊆ B , then f f f is monotone.
Constraints often reflect structural or resource limitations—such as selecting a subset of features, sensors, or network links, which can be modeled as a matroid to capture independence and exchange properties. A matroid M = ( N , I ) \mathcal{M} = (\mathcal{N}, \mathcal{I}) M = ( N , I ) is defined by a collection of independent sets I ⊆ 2 N \mathcal{I} \subseteq 2^{\mathcal{N}} I ⊆ 2 N that satisfy non-emptiness, heredity, and the exchange property. The rank k k k of M \mathcal{M} M is the size of its largest independent set. The classical offline problem of submodular maximization under a matroid constraint seeks an independent set S ∈ I S \in \mathcal{I} S ∈ I that maximizes f ( S ) f(S) f ( S ) , i.e., max S ∈ I f ( S ) \max_{S \in \mathcal{I}} f(S) max S ∈ I f ( S ) .
Submodular maximization has a broad range of applications. In machine learning, it appears in feature selection [23 , 42 ] , data summarization [8 , 15 ] , and active learning [12 , 13 ] . In data mining and network science, it models influence maximization [7 , 14 ] and community detection [27 , 24 ] , while in network design [25 , 26 ] , it captures objectives related to connectivity, reliability, and information flow.
The dynamic variant of submodular maximization under a matroid constraint has received growing attention [16 , 17 , 9 , 41 ] . Here, the ground set N \mathcal{N} N evolves over time through insertions and deletions, and the goal is to maintain an independent set S ∈ I S \in \mathcal{I} S ∈ I that remains near-optimal for the current instance, while limiting the computational overhead per update. Formally, the algorithm interacts with f f f through a value oracle and with M \mathcal{M} M through an independence oracle, and must update its maintained solution as the input changes.
While the offline version of submodular maximization under a matroid constraint is well understood—for instance, the classic greedy algorithm attains a ( 1 − 1 / e ) (1 - 1/e) ( 1 − 1/ e ) -approximation [36 ] —these offline methods recompute the entire solution from scratch following each change, resulting in linear update time in ∣ N ∣ |\mathcal{N}| ∣ N ∣ . Such costs become prohibitive in large-scale settings, which has spurred interest in efficient dynamic submodular maximization algorithms that offer near-optimal guarantees while maintaining polylogarithmic update times.
Designing efficient algorithms for maintaining near-optimal solutions to monotone submodular maximization under matroid constraints in a fully dynamic setting has been a longstanding challenge (was posed in [34 , 17 ] , and remains a natural open problem following [38 , 16 ] ). The goal is to handle insertions and deletions of elements while simultaneously achieving two key objectives:
maintain a constant-factor approximation (e.g., ( 4 + ϵ ) (4+\epsilon) ( 4 + ϵ ) ) to the optimal solution, and
ensure that each update requires only polylogarithmic time in the size of the ground set, measured in oracle queries to f f f and M \mathcal{M} M .
Prior work has made substantial progress toward this goal. Dütting et al. [17 ] provided a ( 4 + ϵ ) (4+\epsilon) ( 4 + ϵ ) -approximation algorithm with expected amortized update time O ( k 2 ϵ log k log n log 3 k ϵ ) O\bigl(\frac{k^2}{\epsilon} \log k \log n \log^3 \frac{k}{\epsilon}\bigr) O ( ϵ k 2 log k log n log 3 ϵ k ) . In concurrent and independent work, Banihashem et al. [16 ] improved this to a linear dependence on k k k , achieving O ( k log k log 3 k ϵ ) O\bigl(k \log k \log^3 \frac{k}{\epsilon}\bigr) O ( k log k log 3 ϵ k ) expected amortized update time while preserving the same approximation guarantee. Despite these advances, both approaches become computationally expensive when the matroid rank is large, since the update time still grows polynomially with k k k .
In this work, we overcome this barrier by introducing the first fully dynamic algorithm for submodular maximization under a general matroid constraint whose update time is polylogarithmic in n n n . Our algorithm maintains a ( 4 + ϵ ) (4+\epsilon) ( 4 + ϵ ) -approximate solution with expected amortized update time p o l y ( log n , ϵ − 1 ) \mathrm{poly}(\log n, \epsilon^{-1}) poly ( log n , ϵ − 1 ) , independent of the matroid rank k k k . This breakthrough ensures that even rapidly evolving datasets can be handled efficiently, resolving the open problem posed by earlier studies.
Overview of Our Algorithm.
Our dynamic algorithm for submodular maximization under matroid constraints builds on the dynamic framework developed for the simpler setting of cardinality constraints [32 ] , which was later extended to submodular cover [37 ] and submodular matching [11 ] . Prior to our work, it remained unclear whether these ideas could yield an algorithm with polylogarithmic update time under matroid constraints, whose rich combinatorial structure is notoriously difficult to handle1 .
To process elements, the algorithm organizes them into T T T hierarchical layers, with T T T polylogarithmic in expectation. At each layer ℓ \ell ℓ , our data structure maintains an independent set I ℓ ∈ I I_\ell \in \mathcal{I} I ℓ ∈ I , together with an auxiliary set I ∪ ℓ {I^{\cup}}_\ell I ∪ ℓ as the union of all elements present in the independent set I I I of its preceding levels. A key design choice is that marginal gains are always evaluated with respect to I ∪ {I^{\cup}} I ∪ rather than I I I . Since I ∪ {I^{\cup}} I ∪ only grows over time, marginal values are non-increasing, and elements that were discarded at some layer because of their small marginal contribution do not need to be reconsidered. This prevents costly re-evaluations.
Each layer ℓ \ell ℓ contains a set of elements E ℓ E_\ell E ℓ whose marginal gains with respect to I ∪ {I^{\cup}} I ∪ exceed a threshold and are feasible for addition to I I I under the matroid constraint. These elements are further partitioned into logarithmically many buckets according to their marginal values, and in each layer, the largest bucket is selected for processing. This bucket has two key properties: its elements have nearly equal marginal gains, and processing a constant fraction of them both ensures a substantial contribution to the solution and provides robustness against small deletions. These properties are crucial for controlling solution quality and for bounding the approximation guarantee.
Within each chosen bucket, we employ a sampling mechanism to estimate how many elements should be drawn so that a sufficient number can be successfully added to I I I without violating independence or, if necessary, by displacing existing elements that are less valuable. Once the sample size is determined, a set S ℓ S_\ell S ℓ of that size is drawn uniformly from the bucket. With high probability, most of these elements are successfully added to I I I . In the case of conflicts, elements currently in I I I are removed to restore independence while remaining in I ∪ {I^{\cup}} I ∪ , and the total marginal gain of the inserted elements is always at least twice that of the evicted ones. This geometric dominance guarantees that the overall loss is bounded and that the approximation ratio is preserved over time.
Insertions and deletions are handled using buffered updates. For insertions, each layer maintains a buffer A ℓ A_\ell A ℓ of new elements, and the layer is rebuilt only when the buffer reaches an ϵ \epsilon ϵ -fraction of the size of E ℓ E_\ell E ℓ . For deletions, a single shared buffer D D D is used across all layers, and a layer is rebuilt once an ϵ \epsilon ϵ -fraction of its elements have been deleted. These lazy updates spread the cost of reconstruction evenly over time, leading to low amortized query complexity.
Finally, to accommodate elements of widely varying submodular values, we run parallel copies of the algorithm with thresholds of the form τ = ϵ 4 k ⋅ 2 i \tau = \frac{\epsilon}{4k} \cdot 2^i τ = 4 k ϵ ⋅ 2 i , where i i i ranges over integers. Each element participates only in the runs whose thresholds match its value interval, ensuring efficiency across the full value range. This thresholding technique is inspired by the parallel-run method of [34 ] .
Theorem 1. For any ϵ > 0 \epsilon > 0 ϵ > 0 , there exists a fully dynamic randomized algorithm for submodular maximization under a matroid constraint that maintains an expected ( 4 + ϵ ) (4+\epsilon) ( 4 + ϵ ) -approximate solution against an oblivious adversary. The expected amortized update time is poly ( log n , 1 ϵ ) \operatorname{poly}(\log n, \frac{1}{\epsilon}) poly ( log n , ϵ 1 ) , where n = ∣ N ∣ n = |\mathcal{N}| n = ∣ N ∣ is the ground set size.
Next, we highlight the key novelties of our work in comparison with prior dynamic algorithms for submodular maximization under matroid and cardinality constraints. The dynamic algorithm for matroid constraints proposed in [16 ] achieves an update time linear in the rank k k k of the underlying matroid. In contrast, the dynamic algorithm for the cardinality constraint introduced in [32 ] achieves a polylogarithmic update time. However, neither of these techniques alone can be extended to develop a dynamic algorithm for matroid constraints that maintains a ( 4 + ϵ ) (4+\epsilon) ( 4 + ϵ ) -approximate solution with an expected amortized update time of p o l y ( log n , ϵ − 1 ) \mathrm{poly}(\log n, \epsilon^{-1}) poly ( log n , ϵ − 1 ) .
The approach in [16 ] maintains O ( k ) O(k) O ( k ) layers and, upon the deletion of an element e e e from the current solution, reconstructs the layer ℓ \ell ℓ where e e e was added, along with all subsequent layers. As a result, this framework cannot be directly transformed into a data structure that supports p o l y ( log n , ϵ − 1 ) \mathrm{poly}(\log n, \epsilon^{-1}) poly ( log n , ϵ − 1 ) update time under matroid constraints. To overcome this limitation, we partition the active set E ℓ E_{\ell} E ℓ in each layer ℓ \ell ℓ into logarithmically many buckets according to the marginal values of their elements, and we select the largest bucket for processing. This bucket contains at least O ( ϵ log n ∣ E ℓ ∣ ) O(\frac{\epsilon}{\log n}|E_{\ell}|) O ( l o g n ϵ ∣ E ℓ ∣ ) elements whose marginal gains are nearly identical. Using a sampling mechanism, we estimate the fraction of elements in this bucket that can be added to the current solution through a single uniform sample. The key insight is that, since all elements added to the solution at layer ℓ \ell ℓ have nearly equal marginal gains, as long as only an O ( ϵ ) O(\epsilon) O ( ϵ ) fraction of them are modified, the maintained solution continues to provide a ( 4 + ϵ ) (4+\epsilon) ( 4 + ϵ ) -approximation guarantee. Consequently, unlike the approach in [16 ] , which can tolerate only one update to the maintained solution (and therefore requires O ( k ) O(k) O ( k ) layers), our method can tolerate changes to an O ( ϵ ) O(\epsilon) O ( ϵ ) fraction of elements with nearly equal marginal gains. This property enables us to achieve an expected amortized update time of p o l y ( log n , ϵ − 1 ) \mathrm{poly}(\log n, \epsilon^{-1}) poly ( log n , ϵ − 1 ) .
Moreover, while submodular maximization under cardinality or matching constraints is closely related to the matroid-constrained problem—specifically where the matroid is uniform of rank k—extending dynamic algorithms (e.g., [34 , 32 , 11 ] ) to general matroids is far from trivial. The primary challenge lies in the structural nature of matroids, particularly the strong exchange property, which governs how independence is maintained as elements are inserted or deleted. Under a cardinality constraint, feasibility is a simple function of the set’s size. This simplicity facilitates efficient update operations and enables the maintenance of approximate solutions with amortized polylogarithmic complexity. Similarly, matching constraints possess a specific localized structure that limits the ripple effect of updates. In contrast, for general matroids, maintaining independence requires intricate coordination across the entire ground set; adding or removing a single element can shift the feasibility status of numerous other subsets. Consequently, existing algorithms cannot be directly adapted to general matroids without substantial new insights. Our analysis introduces non-trivial arguments leveraging matroid axioms to ensure that dynamic updates preserve both independence and near-optimality.
One of the technicalities of this dynamic framework lies in its sampling size estimation procedure, which differs fundamentally from the binary-search sampling method used in [32 ] , originally introduced in [33 ] and [20 ] . Due to the exchange property inherent in matroid constraints, this binary-search approach cannot be directly applied. Instead, we design a new sampling mechanism adapted to the matroid structure. For each layer ℓ \ell ℓ , to estimate the number of elements of the largest bucket that can be uniformly sampled all at once (i.e., non-adaptively), we consider a polylogarithmic number of random permutations of elements in the largest bucket. For each permutation, we iterate from its beginning to determine the elements that can be added to the current solution while maintaining independence. (Recall that if a conflict arises, elements currently in I I I are removed to restore feasibility, and the removed elements are added to I ∪ {I^{\cup}} I ∪ . It is important to note that, unlike the dynamic algorithm for cardinality constraint [32 ] , where marginal gains are compared directly against the current solution, in our matroid-constrained setting, the marginal gains are compared with respect to I ∪ {I^{\cup}} I ∪ , while the independence condition is enforced relative to the solution set I I I .)
After processing all permutations, we identify the largest index i i i of the permutations such that, in at least a ( 1 − ϵ ) (1-\epsilon) ( 1 − ϵ ) -fraction of the permutations, the element at index i i i could be added to I ∪ {I^{\cup}} I ∪ . Finally, in contrast to the cardinality-constrained setting, where all t t t uniformly sampled elements from the largest bucket are added to the solution, our framework must verify each sampled element individually to ensure matroid feasibility.
However, the primary technical challenge of this work, distinguishing it from [11 ] , arises from the fundamental structural disparities between matroids and matchings. Specifically, the \textsc{Inspect} and {\textsc{Adjust}} procedures required for matroids are more involved than those employed in the matching framework. These structural differences ultimately lead to a substantially different and more complex analysis to establish approximation guarantees.
Dynamic submodular maximization has attracted significant attention in recent years. Lattanzi et al. [34 ] presented a randomized dynamic algorithm that maintains a ( 2 + ϵ ) (2+\epsilon) ( 2 + ϵ ) -approximate solution for maximizing a monotone submodular function under a cardinality constraint k k k . Their method achieves an amortized expected query complexity O ( ϵ − 11 log 6 ( k ) log 2 ( n ) ) O(\epsilon^{-11} \log^6(k) \log^2(n)) O ( ϵ − 11 log 6 ( k ) log 2 ( n )) per update, which is polylogarithmic in n n n . Independently, Monemizadeh [22 ] developed another randomized dynamic algorithm with similar approximation guarantees, requiring O ( ϵ − 3 k 2 log 5 ( n ) ) O(\epsilon^{-3} k^2 \log^5(n)) O ( ϵ − 3 k 2 log 5 ( n )) queries per update. Subsequent work extended these results to the dynamic non-monotone setting [35 ] . Further advances demonstrated that near-optimal efficiency is achievable for related problems such as submodular cover [10 ] and maximum submodular matching [11 ] , attaining polylogarithmic query complexity. However, achieving polylogarithmic update time for matroid constraints remains an open challenge despite persistent efforts [16 , 38 , 17 , 34 ] . This paper resolves this open problem.
Chen and Peng [38 ] established lower bounds for dynamic submodular maximization with cardinality constraints, which is a special case of matroid constraints. They showed that any algorithm achieving better than a ( 2 − ϵ ) (2-\epsilon) ( 2 − ϵ ) -approximation must have amortized query complexity at least n Ω ~ ( ϵ ) / k 3 n^{\tilde{\Omega}(\epsilon)} / k^3 n Ω ~ ( ϵ ) / k 3 , and achieving an approximation better than 1.712 1.712 1.712 requires Ω ( n / k 3 ) \Omega(n / k^3) Ω ( n / k 3 ) queries per update, even if the optimal value of the current set is known. In the insertion-only model, they further provided algorithms for submodular maximization under a matroid constraint of rank k k k , achieving ( 2 + ϵ ) (2+\epsilon) ( 2 + ϵ ) and ( e e − 1 + ϵ ) (\frac{e}{e-1}+\epsilon) ( e − 1 e + ϵ ) -approximations with expected oracle query complexity k O ~ ( 1 / ϵ ) k^{\tilde{O}(1/\epsilon)} k O ~ ( 1/ ϵ ) and k O ~ ( 1 / ϵ 2 ) ⋅ log ( n ) k^{\tilde{O}(1/\epsilon^2)} \cdot \log(n) k O ~ ( 1/ ϵ 2 ) ⋅ log ( n ) , respectively.
For general matroid constraints, Dütting et al. [17 ] proposed a ( 4 + ϵ ) (4+\epsilon) ( 4 + ϵ ) -approximation algorithm with expected amortized update time O ( k 2 ϵ log k log n log 3 k ϵ ) O\!\bigl(\frac{k^2}{\epsilon} \log k \log n \log^3 \tfrac{k}{\epsilon}\bigr) O ( ϵ k 2 log k log n log 3 ϵ k ) , which scales quadratically with the matroid rank k k k . An improved method was later introduced by Banihashem et al. [16 ] , which achieves a similar approximation ratio but with expected amortized update time O ( k log k log 3 k ϵ ) O(k \log k \log^3 \tfrac{k}{\epsilon}) O ( k log k log 3 ϵ k ) , linear in k k k . Although these results represent progress, both approaches become inefficient when k k k is large (e.g., k = n o ( 1 ) k = n^{o(1)} k = n o ( 1 ) ), since their complexity still grows polynomially in k k k .
A related line of research considers the streaming setting, where the data arrives sequentially and algorithms must work with limited memory. The first streaming algorithm for submodular maximization under a cardinality constraint was proposed by Badanidiyuru et al. [15 ] , who gave a ( 2 + ϵ ) (2+\epsilon) ( 2 + ϵ ) -approximation using O ( k ϵ − 1 log k ) O(k\epsilon^{-1} \log k) O ( k ϵ − 1 log k ) space. This was later improved by Kazemi et al. [21 ] , who reduced the space requirement to O ( k ϵ − 1 ) O(k\epsilon^{-1}) O ( k ϵ − 1 ) . Chakrabarti and Kale [44 ] introduced a streaming framework applicable to a wide range of combinatorial constraints, including matroid and matching constraints. Their approach yields a 4 4 4 -approximation algorithm for submodular maximization under a matroid constraint, using O ( k ) O(k) O ( k ) space.
Preliminaries
In this section, we introduce submodular functions, matroids, the oblivious adversarial model used in our dynamic setting, and the notion of query complexity.
Submodular functions.
Let N \mathcal{N} N be a finite ground set. A function f : 2 N → R + f: 2^{\mathcal{N}} \rightarrow {\mathbb{R}}^+ f : 2 N → R + is called submodular if for all A ⊆ B ⊆ N A \subseteq B \subseteq \mathcal{N} A ⊆ B ⊆ N and any e ∉ B e \notin B e ∈ / B , f ( A ∪ { e } ) − f ( A ) ≥ f ( B ∪ { e } ) − f ( B ) , f(A \cup \{e\}) - f(A) \ge f(B \cup \{e\}) - f(B), f ( A ∪ { e }) − f ( A ) ≥ f ( B ∪ { e }) − f ( B ) , capturing the principle of diminishing returns: the benefit of adding an element e e e to a smaller set A A A is at least as large as adding it to its supersets. An equivalent definition states that for all A , B ⊆ N A, B \subseteq \mathcal{N} A , B ⊆ N , f ( A ) + f ( B ) ≥ f ( A ∪ B ) + f ( A ∩ B ) , f(A) + f(B) \ge f(A \cup B) + f(A \cap B), f ( A ) + f ( B ) ≥ f ( A ∪ B ) + f ( A ∩ B ) , . We assume that the submodular function f f f is also monotone, meaning f ( A ∪ { e } ) ≥ f ( A ) f(A \cup \{e\}) \ge f(A) f ( A ∪ { e }) ≥ f ( A ) for all A ⊆ N A \subseteq \mathcal{N} A ⊆ N . The value f ( A ∪ { e } ) − f ( A ) f(A \cup \{e\}) - f(A) f ( A ∪ { e }) − f ( A ) is called the marginal gain of adding e e e to A A A , and is denoted by f ( e ∣ A ) f(e | A) f ( e ∣ A ) . In this paper, we assume to have access to f f f via a value oracle.
Matroids.
Matroids are general combinatorial structures that capture the notion of independence. Formally, a matroid M = ( N , I ) \mathcal{M} = (\mathcal{N}, \mathcal{I}) M = ( N , I ) consists of a finite ground set N \mathcal{N} N and a collection of subsets I ⊆ 2 N \mathcal{I} \subseteq 2^{\mathcal{N}} I ⊆ 2 N , called independent sets, satisfying the following three properties: non-emptiness: ∅ ∈ I \emptyset \in \mathcal{I} ∅ ∈ I , i.e., the empty set is independent; heredity (downward-closedness): If A ∈ I A \in \mathcal{I} A ∈ I and B ⊆ A B \subseteq A B ⊆ A , then B ∈ I B \in \mathcal{I} B ∈ I , i.e., every subset of an independent set is also independent; exchange property: If A , B ∈ I A, B \in \mathcal{I} A , B ∈ I and ∣ A ∣ < ∣ B ∣ |A| < |B| ∣ A ∣ < ∣ B ∣ , then there exists an element x ∈ B ∖ A x \in B \setminus A x ∈ B ∖ A such that A ∪ { x } ∈ I A \cup \{x\} \in \mathcal{I} A ∪ { x } ∈ I . The rank k k k of the matroid is the size of its largest independent set; the exchange property ensures that all maximal independent sets (called bases) have the same size k k k . A circuit in a matroid is a minimal dependent set, i.e., a set C ⊆ N C \subseteq \mathcal{N} C ⊆ N that is not independent but every proper subset of C C C is independent. Circuits describe the minimal sets of elements whose presence causes dependence; thus, removal of at least one element from each circuit of a dependent set makes it independent. The family C \mathcal{C} C of circuits of a matroid M \mathcal{M} M satisfies the following properties: ∅ ∉ C \emptyset \notin \mathcal{C} ∅ ∈ / C ; if C 1 , C 2 ∈ C C_1, C_2 \in \mathcal{C} C 1 , C 2 ∈ C and C 1 ⊆ C 2 C_1 \subseteq C_2 C 1 ⊆ C 2 , then C 1 = C 2 C_1 = C_2 C 1 = C 2 ; and if C 1 , C 2 ∈ C C_1, C_2 \in \mathcal{C} C 1 , C 2 ∈ C , C 1 ≠ C 2 C_1 \neq C_2 C 1 = C 2 and e ∈ C 1 ∩ C 2 e \in C_1 \cap C_2 e ∈ C 1 ∩ C 2 , then there exists C 3 ∈ C C_3 \in \mathcal{C} C 3 ∈ C such that C 3 ⊆ ( C 1 ∪ C 2 ) ∖ { e } C_3 \subseteq (C_1 \cup C_2) \setminus \{e\} C 3 ⊆ ( C 1 ∪ C 2 ) ∖ { e } . It follows that if I ∈ I I \in \mathcal{I} I ∈ I and e ∈ N e \in \mathcal{N} e ∈ N with I ∪ { e } ∉ I I \cup \{e\} \notin \mathcal{I} I ∪ { e } ∈ / I , then I ∪ { e } I \cup \{e\} I ∪ { e } contains a unique circuit C C C (see Lemma 42 ); consequently, removing any element of C C C from I ∪ { e } I \cup \{e\} I ∪ { e } restores its independence. In this paper, we assume that we have access to an independence oracle for the matroid M \mathcal{M} M .
Oblivious adversarial model.
We analyze our dynamic algorithm in the oblivious adversarial model, a standard framework for randomized data structures [43 ] . In this model, the adversary knows both f f f and the algorithm but not its random bits; thus, the entire update sequence is fixed before execution.
Query complexity.
The query complexity of a dynamic algorithm is the number of oracle queries (to the value oracle for f f f and to the independence oracle for the matroid M \mathcal{M} M ) used to maintain an approximate solution at time t t t , given all computation up to time t − 1 t-1 t − 1 . We measure time complexity primarily in terms of this query complexity.
Finally, we give a few notations that we use frequently in this paper.
For a function x x x and a set A A A , we write x [ A ] x[A] x [ A ] to denote the restriction of x x x to the domain A A A . Given an event E E E , we use 1 [ E ] {\mathds{1}\left[E\right]} 1 [ E ] to denote its indicator function: it equals 1 1 1 if E E E occurs, and 0 0 0 otherwise. We use bold letters for random variables (e.g., X \textbf{X} X ) and the corresponding non-bold letters (e.g., X X X ) to represent their realizations. The probability and expectation of a random variable X \textbf{X} X are denoted by P [ X ] {\mathbb{P}\left[\textbf{X}\right]} P [ X ] and E [ X ] {\mathbb{E}\left[\textbf{X}\right]} E [ X ] , respectively. For two events A A A and B B B , we write P [ A ∣ B ] {\mathbb{P}\left[A \mid B\right]} P [ A ∣ B ] for the conditional probability of A A A given B B B . For an event A A A with nonzero probability and a discrete random variable X \textbf{X} X , the conditional expectation of X \textbf{X} X given A A A is written as E [ X ∣ A ] {\mathbb{E}\left[\textbf{X} \mid A\right]} E [ X ∣ A ] and defined by E [ X ∣ A ] = ∑ x x ⋅ P [ X = x ∣ A ] . {\mathbb{E}\left[\textbf{X} \mid A\right]} = \sum_{x} x \cdot {\mathbb{P}\left[\textbf{X} = x \mid A\right]}. E [ X ∣ A ] = ∑ x x ⋅ P [ X = x ∣ A ] . Similarly, for two discrete random variables X \textbf{X} X and Y \textbf{Y} Y , the conditional expectation of X \textbf{X} X given that Y = y \textbf{Y}=y Y = y is denoted by E [ X ∣ Y = y ] {\mathbb{E}\left[\textbf{X} \mid \textbf{Y}=y\right]} E [ X ∣ Y = y ] .
Algorithms
In this section, we describe our dynamic algorithm for submodular maximization under a matroid constraint that maintains an independent set I I I that achieves a ( 4 + ϵ ) (4+\epsilon) ( 4 + ϵ ) -approximation to the optimal solution, while efficiently handling insertions and deletions. The algorithm is built using several algorithms or subroutines:
Inspection procedure (Inspect):
For a new element e e e , we first check whether its marginal gain with respect to current set I ∪ {I^{\cup}} I ∪ exceeds threshold τ \tau τ . If e e e can be added to the independent set I I I without violating the matroid constraint, we include it. Otherwise, we identify an element e ^ ∈ I \hat{e} \in I e ^ ∈ I with the smallest marginal contribution Δ ( e ^ ) \Delta(\hat{e}) Δ ( e ^ ) , such that replacing e ^ \hat{e} e ^ by e e e still preserves independence. If 2 ⋅ Δ ( e ^ ) ≤ f ( e ∣ I ∪ ) 2 \cdot \Delta(\hat{e}) \le f(e | {I^{\cup}}) 2 ⋅ Δ ( e ^ ) ≤ f ( e ∣ I ∪ ) , we replace e ^ \hat{e} e ^ with e e e .
\caption{Inspection}
\begin{algorithmic}[1]
\Procedure{\textsc{Inspect}}{$e, (I, {I^{\cup}}, \Delta), \tau$}
\label{alg:inspect}
\If{$ f(e | {I^{\cup}}) < \tau$}\label{line:remove_w_not_in_range}
\State \Return \textsc{Fail}
\EndIf
\If{$I\cup\left\{\,e\,\right\} \in {\mathcal{I}}$}
\State \Return $\emptyset$
\EndIf
\State $\hat{e} \gets \arg\min \left\{\,\Delta(e') : e' \in I,
I\cup \left\{\,e\,\right\} \setminus \left\{\,e'\,\right\} \in {\mathcal{I}}\,\right\}$ \Comment{find by using a binary search}
\label{line:matroid:promote:find_min}
\If{$2\cdot \Delta(\hat{e}) \le f(e | {I^{\cup}}) $}
\State \Return $\left\{\,\hat{e}\,\right\}$
\EndIf
\State \Return \textsc{Fail}
\EndProcedure
\end{algorithmic}
Iterative Expansion (Expand):
Given a sample set S S S of candidate elements and the current triplet ( I , I ∪ , Δ ) (I, {I^{\cup}}, \Delta) ( I , I ∪ , Δ ) , we iterate over S S S , applying to each element e e e . The procedure tries to insert e e e via , and if successful, updates marginal contributions and keeps I I I independent.
\caption{Iterative Expansion}
\label{alg:expand}
\begin{algorithmic}[1]
\Procedure{{\textsc{Expand}}}{$S, (I, {I^{\cup}}, \Delta), \tau$}
\State $(I, {I^{\cup}}, \Delta)' \gets (I, {I^{\cup}}, \Delta)$
\For{$e \in S$} %\label{line:construct_for}
\State $(I, {I^{\cup}}, \Delta)' \gets
{\textsc{Adjust}}(e, (I, {I^{\cup}}, \Delta)', \tau)$
\EndFor
\State \Return $(I, {I^{\cup}}, \Delta)'$ \label{line:construct_sample_process_end}
\EndProcedure
\Procedure{{\textsc{Adjust}}}{$e, (I, {I^{\cup}}, \Delta), \tau$}
\label{alg:adjust}
\State $X \gets$ {\textsc{Inspect}}$(e, (I, {I^{\cup}}, \Delta), \tau)$
\If{$X \ne \textsc{Fail}$}
\State $\Delta(e) \gets f(e | {I^{\cup}})$ and $I\gets I\cup \left\{\,e\,\right\} \setminus X$ and ${I^{\cup}}{} \gets {I^{\cup}}\cup \left\{\,e\,\right\}$
\EndIf
\State \Return $(I, {I^{\cup}}, \Delta)$
\EndProcedure
\end{algorithmic}
\caption{Sample Size Estimation}
\label{alg:sample_size}
\begin{algorithmic}[1]
\Procedure{{\textsc{EstimateSampleSize}}}{$B, (I, {I^{\cup}}, \Delta), \tau$}
\State $t \gets {\left\lceil {\frac{4}{\epsilon_{\textnormal{sam}}^2}\ln(\frac{2nk^{10}}{\epsilon_{\textnormal{pr}}})} \right\rceil}$
\State Initialize $X$ as a $t \times (|B| + 1)$ matrix of zeros.
\For{$i \gets 1$ to $t$}
\State $B' \gets \text{a random permutation of } B$
\State $(I, {I^{\cup}}, \Delta)' \gets {\textsc{Expand}}(B', (I, {I^{\cup}}, \Delta), \tau)$
%\For{$j \gets 1$ to $|\buck'|$}
\State $X[i,j] \gets \ensuremath{\mathds{1}\left[B'[j] \in {I^{\cup}}{}'\right]}$ \qquad {$\forall 1 \le j \le |B|$}
%\EndFor
\EndFor
\State $ s' \gets \min{\left\{\,j : 1 \le j \le {\left|B \right|} + 1, \frac{1}{t}(\sum_{i=1}^t X[i,j])< 1 - \epsilon_{\textnormal{sam}}\,\right\}} $
%\State Let $\ssize'$ be the smallest index $j \in [1, |\buck| + 1]$ for which $\frac{1}{t}(\sum_{i=1}^t \acc[i,j])< 1 - \epsSamp$
\State \Return $s' - 1$
\EndProcedure
\end{algorithmic}
Sample Size Estimation (EstimateSampleSize):
At each layer ℓ \ell ℓ , we partition active elements into buckets based on their marginal gains relative to I ∪ ℓ − 1 {I^{\cup}}_{\ell-1} I ∪ ℓ − 1 . We estimate an appropriate sample size s ℓ s_{\ell} s ℓ to ensure, with high probability, that sampling from the largest bucket yields enough elements that can be successfully added to I I I .
\caption{Main Algorithm}
\label{alg:main}
\begin{algorithmic}[1]
\Procedure{{\textsc{Init}}{}}{$\tau$}
%\State $\elem_0, \add_0, \setd, \indep_0, \uni_0 \gets \emptyset$
\State $I_0, {I^{\cup}}_0, E_1, A_1, B_1, D\gets \emptyset$ and $T \gets 0$
\State Initialize $\Delta_0$ as a zero function
\EndProcedure
\Procedure{{\textsc{Insert}}}{$e$}
\State $D \gets D \setminus \{e\}$
%\State $\elem_{0} \gets \elem_0 \cup \cbr{e}$
\For{$\ell \gets 1$ to $T + 1$} \label{line:insert_loop}
\If{$\textsc{Inspect}{}(e, (I, {I^{\cup}}, \Delta)_{\ell - 1}, \tau) \ne \textsc{Fail}$ \& $e \notin E_{\ell}$ }
\State ${A}_{\ell} \gets {A}_{\ell} \cup \left\{\,e\,\right\}$
\EndIf
\If{${\left|A_{\ell} \right|} > \epsilon_{\textnormal{ins}}{\left|E_\ell \right|}$}
\label{line:insert_checkforconstruct}
\State \Return ${\textsc{LayerConstruct}}{}(\ell)$
\EndIf
\EndFor
\State \Return $I_T \setminus D$
\EndProcedure
\Procedure{{\textsc{Delete}}}{$e$}
\State $D\gets D\cup \left\{\,e\,\right\}$
%\State $\elem_{0} \gets \elem_0 \setminus \cbr{e}$
\For{$\ell \gets 1$ to $T$}
\If{${\left|D\cap B_\ell \right|} \ge \epsilon_{\textnormal{del}}{\left|B_\ell \right|}$} \label{line:delete_cond}
\State \Return ${\textsc{LayerConstruct}}{}(\ell)$
\EndIf
\EndFor
\State \Return $I_T \setminus D$
\EndProcedure
\Procedure{{\textsc{LayerConstruct}}}{$\ell$}
%\textbf{Input:} A layer $\ell \ge 1$
\State $E_{\ell} \gets (E_{\ell} \cup A_{\ell}) \setminus D$
\State $A_{\ell} \gets \emptyset$
\label{line:construct_init}
\If{$E_{\ell} = \emptyset$}
\State $T \gets \ell - 1$
\State \Return $I_{T} \setminus D$
\EndIf
\State $(B_{\ell}, \tau_{\ell}) \gets {\textsc{ChooseBucket}}{}(\ell)$
\State $s_{\ell} \gets {\textsc{EstimateSampleSize}}{}(B_{\ell}, (I, {I^{\cup}}, \Delta)_{\ell-1}, \tau_{\ell})$
\label{ln:estimatesz}
\State $S_{\ell} \gets$ a random permutation of a uniformly selected subset of size $s_{\ell}$ from $B_{\ell}$
\label{line:construct_sample}
\State $(I, {I^{\cup}}, \Delta)_{\ell} \gets {\textsc{Expand}}(S_{\ell}, (I, {I^{\cup}}, \Delta)_{\ell-1}, \tau_{\ell})$
\label{line:expand}
\State $E_{\ell + 1} \gets \left\{\,e \in E_{\ell}: \textsc{Inspect}{}(e, (I, {I^{\cup}}, \Delta)_{\ell}, \tau) \ne \textsc{Fail}\,\right\}$
\label{ln:filter}
\State $A_{\ell + 1} \gets \emptyset$
\State \Return ${\textsc{LayerConstruct}}(\ell + 1)$
\label{ln:ell+1}
\EndProcedure
\Procedure{{\textsc{ChooseBucket}}}{$\ell$}
\State $B_{\ell, j} \gets \emptyset$ \quad $\forall 0 \le j
< \log_{(1+\epsilon)}(\frac{4k}{\epsilon})$
%\le \ceil{\log_{(1+\epsTau)} (\frac{\MAX{}}{\tauMin})}$
\For{$e \in E_{\ell}$}
\State $j \gets \left\lfloor\,\log_{1+\epsilon}(\frac{f(e | {I^{\cup}}_{\ell - 1})}{\tau})\,\right\rfloor$
\State $B_{\ell, j} \gets B_{\ell, j} \cup \{e\}$
\Comment{
$B_{\ell, j} \gets \left\{\,e \in E_{\ell}: (1+\epsilon)^{j}\tau \le f(e | {I^{\cup}}_{\ell - 1}) < (1+\epsilon)^{j+1}\tau\,\right\}$
}
\EndFor
\State $j_{\ell} \gets \mathop{\mathrm{arg\,max}}_{j} \left\{\,{\left|B_{\ell, j} \right|}\,\right\}$
\State \Return $(B_{\ell, j_{\ell}}, (1+\epsilon)^{j_{\ell}} \tau)$
\Comment{
$B_{\ell} \gets B_{\ell, j_{\ell}} $ \quad $\tau_{\ell} \gets (1+\epsilon)^{j_{\ell}} \tau $
}
\EndProcedure
\end{algorithmic}
Layered Dynamic Structure:
Our algorithm organizes computation into multiple layers indexed by ℓ \ell ℓ . For each layer, we maintain a set of active elements E ℓ E_{\ell} E ℓ , an auxiliary buffer A ℓ A_{\ell} A ℓ for new insertions, and associated data structures. When a new element e e e arrives, we check in each layer whether it can be added to E ℓ E_{\ell} E ℓ . If so, we perform a lazy update: we add e e e to A ℓ A_{\ell} A ℓ . When ∣ A ℓ ∣ |A_{\ell}| ∣ A ℓ ∣ reaches an ϵ \epsilon ϵ -fraction of ∣ E ℓ ∣ |E_{\ell}| ∣ E ℓ ∣ , we merge A ℓ A_{\ell} A ℓ into E ℓ E_{\ell} E ℓ and reconstruct layer ℓ \ell ℓ from scratch.
For deletions, we keep a single shared buffer D D D collecting all removed elements. For each layer ℓ \ell ℓ , if an ϵ \epsilon ϵ -fraction of E ℓ E_{\ell} E ℓ appear in D D D , we rebuild that layer using the remaining undeleted elements. Unlike insertions—where each layer maintains its own buffer A ℓ A_{\ell} A ℓ —deletions use the same global buffer D D D .
Layer Construction (LayerConstruct):
To build the next layer, the algorithm uses ChooseBucket to select the largest bucket of elements with similar marginal gains. We then sample a subset from this bucket, expand I I I by adding feasible elements (via Expand), and filter elements to create the new set A ℓ + 1 A_{\ell+1} A ℓ + 1 for the subsequent layer.
Parallel Instances:
To handle elements with diverse marginal gains, we run parallel copies of the dynamic algorithm, each using a different threshold τ = ϵ 4 k ⋅ 2 i \tau = \frac{\epsilon}{4k} \cdot 2^i τ = 4 k ϵ ⋅ 2 i . When an element e e e is inserted or deleted, we update all instances whose threshold ranges include f ( e ) f(e) f ( e ) , following the parallel threshold idea from [34 ] .
\caption{Parallel Runs}
\label{alg:parallel}
\begin{algorithmic}[1]
\For{$i \in \mathbb{Z}$}
\State Let $\mathcal{I}_i$ be an instance of Main Algorithm \ref{alg:main}, with $\tau = \frac{\epsilon}{4k}\cdot 2^i$.
\EndFor
\Function{Global{\textsc{Insert}}}{$e$}
\label{alg:globins}
\State $V \gets V \cup \left\{\,e\,\right\}$
\For{\textbf{each} $
\log(f(v))
< i \leq \log(f(v)) + \log(\frac{4k}{\epsilon})$
} \label{line:paralle_run_insertion_interval}
\Comment{
\(\frac{\epsilon}{4k}\cdot 2^{i} \le f(v) < 2^{i}\)
}
\State Invoke ${\textsc{Insert}}(e)$ for instance $\mathcal{I}_i$.
\EndFor
\EndFunction
\Function{Global{\textsc{Delete}}}{$e$}
\label{alg:globdel}
\State $V \gets V \setminus \left\{\,e\,\right\}$
\For{\textbf{each} $
\log(f(v))
< i \leq \log(f(v)) + \log(\frac{4k}{\epsilon})$
} \label{line:paralle_run_deletion_interval}
\Comment{
\(\frac{\epsilon}{4k}\cdot 2^{i} \le f(v) < 2^{i}\)
}
\State Invoke ${\textsc{Delete}}(e)$ for instance $\mathcal{I}_i$.
\EndFor
\EndFunction
\end{algorithmic}
By combining layered reconstruction, careful sampling, and iterative expansion while always evaluating marginal gains relative to the persistent set I ∪ {I^{\cup}} I ∪ , our algorithm dynamically maintains an independent set I I I that remains a ( 4 + ϵ ) (4+\epsilon) ( 4 + ϵ ) -approximation to the optimum, even as elements are inserted to or removed from the ground set N \mathcal{N} N .
Analysis
We consider a fixed point in time immediately after the algorithm finishes executing an update. Throughout our analysis, we study the state of our algorithm at this fixed point of time, to which we may refer as the current time. As such, our Theorems, Definitions, and Lemmas are based on the current state of variables, unless explicitly specified.
Deterministic Properties of the Data structure
In this section, we establish a series of deterministic invariants that describe the state of our data structure at the said current time. We begin with a lemma that describes the structure of independent and union sets at layer zero.
Lemma. The following holds: I 0 = I ∪ 0 = ∅ . I_0 = {I^{\cup}}_0 = \emptyset. I 0 = I ∪ 0 = ∅.
Proof. Consider the full course of the algorithm’s execution. Both I 0 I_0 I 0 and I ∪ 0 {I^{\cup}}_0 I ∪ 0 are initialized as empty sets during the {\textsc{Init}} procedure, performed at the outset. Throughout the remainder of the algorithm, I 0 I_0 I 0 and I ∪ 0 {I^{\cup}}_0 I ∪ 0 remain unchanged, as none of the update procedures modify either of them, directly or indirectly, through the {\textsc{LayerConstruct}} procedure. This is because {\textsc{LayerConstruct}}(\ell) is only invoked for ℓ ≥ 1 \ell \geq 1 ℓ ≥ 1 and does not make any modifications to I ℓ ′ I_{\ell'} I ℓ ′ or I ∪ ℓ ′ {I^{\cup}}_{\ell'} I ∪ ℓ ′ for any ℓ ′ < ℓ \ell' < \ell ℓ ′ < ℓ . ◻
The following lemma establishes the relationship between the variables ( I , I ∪ , Δ ) (I, {I^{\cup}}, \Delta) ( I , I ∪ , Δ ) across successive layers, expressed in terms of the {\textsc{Expand}} operation.
Lemma. The following holds for all ℓ ∈ [ T ] \ell \in [T] ℓ ∈ [ T ] : (I, {I^{\cup}}, \Delta)_{\ell} = {\textsc{Expand}}(S_{\ell}, (I, {I^{\cup}}, \Delta)_{\ell-1}, \tau_{\ell}).
Proof. We prove this by considering a fixed ℓ ∈ [ T ] \ell \in [T] ℓ ∈ [ T ] and showing that (I, {I^{\cup}}, \Delta)_{\ell} = {\textsc{Expand}}(S_{\ell}, (I, {I^{\cup}}, \Delta)_{\ell-1}, \tau_{\ell}).
First, note that the helper functions \textsc{Inspect} , {\textsc{Expand}} , and {\textsc{EstimateSampleSize}} do not modify their input parameters during execution. Moreover, note that throughout the entire execution of the algorithm, the values of the variables ( I , I ∪ , Δ ) i (I, {I^{\cup}}, \Delta)_i ( I , I ∪ , Δ ) i , S i S_i S i , and τ i \tau_i τ i , for any arbitrary i i i , may change only within the {\textsc{LayerConstruct}}(i) procedure prior to its invocation of {\textsc{LayerConstruct}}(i + 1) in line ln:ell+1 .
Now, Consider the most recent invocation of {\textsc{LayerConstruct}}(\ell) . Immediately after the execution of line line:expand within {\textsc{LayerConstruct}}(\ell) , the equality (I, {I^{\cup}}, \Delta)_{\ell} = {\textsc{Expand}}(S_{\ell}, (I, {I^{\cup}}, \Delta)_{\ell-1}, \tau_{\ell}) holds by construction.
Since any invocation of {\textsc{LayerConstruct}}(\ell - 1) would subsequently trigger a call to {\textsc{LayerConstruct}}(\ell) , our choice implies that neither {\textsc{LayerConstruct}}(\ell - 1) nor {\textsc{LayerConstruct}}(\ell) has been invoked since then. Hence, the values of ( I , I ∪ , Δ ) ℓ − 1 (I, {I^{\cup}}, \Delta)_{\ell-1} ( I , I ∪ , Δ ) ℓ − 1 , S ℓ S_{\ell} S ℓ , τ ℓ \tau_{\ell} τ ℓ , and ( I , I ∪ , Δ ) ℓ (I, {I^{\cup}}, \Delta)_{\ell} ( I , I ∪ , Δ ) ℓ have remained unchanged since that point, confirming that the equality still holds at current time. ◻
The next lemma formalizes how the active elements are filtered across consecutive layers of our data structure. The proof of the following lemma captures how the algorithm handles reinsertions and redeletions that may occur during updates.
Lemma. Let E ^ ℓ \hat{E}_{\ell} E ^ ℓ denote ( E ℓ ∪ A ℓ ) ∖ D (E_{\ell} \cup A_{\ell}) \setminus D ( E ℓ ∪ A ℓ ) ∖ D for ℓ ∈ [ T + 1 ] \ell \in [T + 1] ℓ ∈ [ T + 1 ] . The following holds for all ℓ ∈ [ T ] \ell \in [T] ℓ ∈ [ T ] : \hat{E}_{\ell + 1} = \left\{\,e \in \hat{E}_{\ell}: \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{\ell}, \tau) \ne \textsc{Fail}\,\right\}.
Proof. Recall that the statement of this lemma concerns the state of the variables following the execution of a fixed update, namely, the current time.
We prove this by showing that the statement holds with respect to the state of the variables before any update is applied, and that, assuming it holds prior to an update, we can conclude it also holds afterward. Hence, by induction, the statement holds for the current time.
Note that before any update is applied, the claim holds trivially as T = 0 T = 0 T = 0 .
Consider a call to the procedure {\textsc{Insert}}(v) or {\textsc{Delete}}(v) . For any variable X X X , let X − X^{-} X − and X + X^{+} X + denote the state of X X X before and after the execution of the procedure, respectively. Suppose that for all ℓ ∈ [ T − ] \ell \in [T^{-}] ℓ ∈ [ T − ] ,
\hat{E}_{\ell + 1}^{-} = \left\{\,e \in \hat{E}_{\ell}^{-}: \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{\ell}^{-}, \tau) \ne \textsc{Fail}\,\right\}.
We aim to prove that for all ℓ ∈ [ T + ] \ell \in [T^{+}] ℓ ∈ [ T + ] ,
\hat{E}_{\ell + 1}^{+} = \left\{\,e \in \hat{E}_{\ell}^{+}: \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{\ell}^{+}, \tau) \ne \textsc{Fail}\,\right\}.
We first prove the following fact, which will be used in our argument.
Fact 5. If {\textsc{LayerConstruct}}(\ell) is invoked during an update, and we use Y / Y^{/} Y / to denote the state of Y Y Y immediately before the invocation of {\textsc{LayerConstruct}}(\ell) , then: E ^ ℓ + = E ℓ + = E ^ ℓ / . \hat{E}_{\ell}^{+} = E_{\ell}^{+} = \hat{E}_{\ell}^{/}. E ^ ℓ + = E ℓ + = E ^ ℓ / .
Proof. Note that D + = D / D^{+} = D^{/} D + = D / . During the execution of {\textsc{LayerConstruct}}(\ell) , the set E ℓ E_{\ell} E ℓ is updated as ( E ℓ ∪ A ℓ ) ∖ D (E_{\ell} \cup A_{\ell}) \setminus D ( E ℓ ∪ A ℓ ) ∖ D and does not change afterward. Then, A ℓ A_{\ell} A ℓ is set to ∅ \emptyset ∅ and also remains unchanged. We have
E i + = ( E i / ∪ A i / ) ∖ D / = E ^ i / , A i + = ∅ , E ^ i + = ( E i + ∪ A i + ) ∖ D + = ( ( ( E i / ∪ A i / ) ∖ D / ) ∪ ∅ ) ∖ D / = ( E i / ∪ A i / ) ∖ D / . \begin{align*}
E_{i}^{+} &= (E_{i}^{/} \cup A_{i}^{/}) \setminus D^{/} = \hat{E}_{i}^{/},\\
A_{i}^{+} &= \emptyset,\\
\hat{E}_{i}^{+} &= (E_{i}^{+} \cup A_{i}^{+}) \setminus D^{+} =
(((E_{i}^{/} \cup A_{i}^{/}) \setminus D^{/}) \cup \emptyset) \setminus D^{/}
=(E_{i}^{/} \cup A_{i}^{/}) \setminus D^{/}.
\end{align*} E i + A i + E ^ i + = ( E i / ∪ A i / ) ∖ D / = E ^ i / , = ∅ , = ( E i + ∪ A i + ) ∖ D + = ((( E i / ∪ A i / ) ∖ D / ) ∪ ∅ ) ∖ D / = ( E i / ∪ A i / ) ∖ D / . ◻
Now, we proceed to prove that the following claim holds for an arbitrary fixed i ∈ [ T + ] i \in [T^{+}] i ∈ [ T + ] , which will complete our proof.
\hat{E}_{i + 1}^{+} = \{ e \in \hat{E}_{i}^{+} : \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{i}^{+}, \tau) \ne \textsc{Fail}\}.
First, consider the case where {\textsc{LayerConstruct}}(i) is invoked. By Fact 5 , we have E ^ i + = E i + . \hat{E}_{i}^{+} = E_{i}^{+}. E ^ i + = E i + . When line ln:filter is executed, both E i E_{i} E i and ( I , I ∪ , Δ ) i (I, {I^{\cup}}, \Delta)_{i} ( I , I ∪ , Δ ) i are finalized. Hence, E i + 1 E_{i + 1} E i + 1 is set as
\{ e \in E_{i}^{+}: \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{i}^{+}, \tau) \ne \textsc{Fail}\} = \{ e \in \hat{E}_{i}^{+} : \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{i}^{+}, \tau) \ne \textsc{Fail}\} .
Then, A i + 1 A_{i + 1} A i + 1 is set to ∅ \emptyset ∅ . Since A i + 1 A_{i + 1} A i + 1 is already ∅ \emptyset ∅ , and ( E i + 1 ∩ D ) ⊆ ( E i ∩ D ) = ∅ (E_{i + 1} \cap D) \subseteq (E_i \cap D) = \emptyset ( E i + 1 ∩ D ) ⊆ ( E i ∩ D ) = ∅ , E i + 1 E_{i + 1} E i + 1 remains unchanged in {\textsc{LayerConstruct}}(i + 1) . Hence, we have shown that
E_{i + 1}^{+} = \{ e \in E_{i}^{+} = \hat{E}_{i}^{+} : \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{i}^{+}, \tau) \ne \textsc{Fail}\}
Moreover, by fact 5 , we have E ^ i + 1 + = E i + 1 + , \hat{E}_{i + 1}^{+} = E_{i + 1}^{+}, E ^ i + 1 + = E i + 1 + , thus proving the claim in this case.
Now, we consider the case where {\textsc{LayerConstruct}}(i) is not invoked.
Note that this assumption does not specify whether {\textsc{LayerConstruct}}(i + 1) is invoked. Let Y / Y^{/} Y / denote the state of the variable Y Y Y when we reach line line:insert_checkforconstruct in the case of executing {\textsc{Insert}}(v) , or line line:delete_cond in the case of executing {\textsc{Delete}}(v) , with ℓ = i \ell = i ℓ = i .
We know that by that point, no change is made to ( I , I ∪ , Δ ) ℓ (I, {I^{\cup}}, \Delta)_{\ell} ( I , I ∪ , Δ ) ℓ for ℓ ≤ i \ell \leq i ℓ ≤ i , and all of E i , A i , E_{i}, A_{i}, E i , A i , and consequently E ^ i \hat{E}_{i} E ^ i are already finalized; that is,
E i + = E i / , A i + = A i / and E ^ i + = E ^ i / . E_{i}^{+} = E_{i}^{/}\quad , \quad
A_{i}^{+} = A_{i}^{/} \quad \text{and} \quad
\hat{E}_{i}^{+} = \hat{E}_{i}^{/}. E i + = E i / , A i + = A i / and E ^ i + = E ^ i / . We also know that E i + 1 E_{i+1} E i + 1 and A i + 1 A_{i+1} A i + 1 are already finalized, and that E ^ i + 1 + = E ^ i + 1 / \hat{E}_{i + 1}^{+} = \hat{E}_{i + 1}^{/} E ^ i + 1 + = E ^ i + 1 / unless {\textsc{LayerConstruct}}(i + 1) is invoked. Even though E i + 1 / E_{i + 1}^{/} E i + 1 / and A i + 1 / A_{i + 1}^{/} A i + 1 / may then differ from E i + 1 + E_{i + 1}^{+} E i + 1 + and A i + 1 + A_{i + 1}^{+} A i + 1 + , by Fact 5 , we still have
E ^ i + 1 + = E ^ i + 1 / . \hat{E}_{i + 1}^{+} = \hat{E}_{i + 1}^{/}. E ^ i + 1 + = E ^ i + 1 / . Therefore, regardless of the case, it suffices to show that
\begin{align}
\hat{E}_{i + 1}^{/} = \{ e \in \hat{E}_{i}^{/} : \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{i}^{-}, \tau) \neq \textsc{Fail}\}, \tag*{(1)}
\end{align}
given the assumption that
\begin{align}
\hat{E}_{i + 1}^{-} = \{ e \in \hat{E}_{i}^{-} : \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{i}^{-}, \tau) \neq \textsc{Fail}\}. \tag*{(2)}
\end{align}
We prove this for {\textsc{Insert}} and {\textsc{Delete}} separately.
1. During {\textsc{Insert}}(v) , until we reach line line:insert_checkforconstruct with ℓ = i \ell = i ℓ = i , the element v v v is removed from D D D , and no change is made to E ℓ E_{\ell} E ℓ or ( I , I ∪ , Δ ) ℓ − 1 (I, {I^{\cup}}, \Delta)_{\ell - 1} ( I , I ∪ , Δ ) ℓ − 1 . For each ℓ ∈ [ i ] \ell \in [i] ℓ ∈ [ i ] , the procedure checks whether v v v passes \textsc{Inspect}(v, (I, {I^{\cup}}, \Delta)_{\ell - 1}, \tau) . If it does, v v v is added to A ℓ A_{\ell} A ℓ .
Given these changes, we know that the pairs E ^ i + 1 / \hat{E}_{i + 1}^{/} E ^ i + 1 / and E ^ i + 1 − \hat{E}_{i + 1}^{-} E ^ i + 1 − , and E ^ i / \hat{E}_{i}^{/} E ^ i / and E ^ i − \hat{E}_{i}^{-} E ^ i − , may only differ at v v v . Hence, to show that equation (1) holds, we only need to focus on v v v and show that
\begin{align}
v \in \hat{E}_{i + 1}^{/} \text{ if and only if }
v \in \hat{E}_{i}^{/}, \text{ and }
\textsc{Inspect}(v, (I, {I^{\cup}}, \Delta)_{i}^{-}, \tau) \neq \textsc{Fail}. \tag*{(3)}
\end{align}
We have that if v ∈ E ^ i + 1 / v \in \hat{E}_{i + 1}^{/} v ∈ E ^ i + 1 / , then v ∈ E i + 1 / ∪ A i + 1 / v \in E_{i + 1}^{/} \cup A_{i + 1}^{/} v ∈ E i + 1 / ∪ A i + 1 / . It follows that v ∈ E i + 1 − v \in E_{i + 1}^{-} v ∈ E i + 1 − or v A i + 1 / v A_{i + 1}^{/} v A i + 1 / . From both, we can infer that \textsc{Inspect}(v, (I, {I^{\cup}}, \Delta)_{i}^{-}, \tau) \neq \textsc{Fail}. It also follows that \textsc{Inspect}(v, (I, {I^{\cup}}, \Delta)_{i - 1}^{-}, \tau) \neq \textsc{Fail}. Hence, v v v was already in E i − E_{i}^{-} E i − or now is in A i / A_{i}^{/} A i / . Thus, v ∈ E ^ i / . v \in \hat{E}_{i}^{/}. v ∈ E ^ i / .
Moreover, we have that if \textsc{Inspect}(v, (I, {I^{\cup}}, \Delta)_{i}^{-}, \tau) \neq \textsc{Fail} , then v ∈ A i + 1 / v \in A_{i + 1}^{/} v ∈ A i + 1 / if v ∉ E i + 1 − v \notin E_{i + 1}^{-} v ∈ / E i + 1 − . Therefore, v ∈ A i + 1 / v \in A_{i + 1}^{/} v ∈ A i + 1 / or v ∈ E i + 1 / v \in E_{i + 1}^{/} v ∈ E i + 1 / . Hence, the statement (3) holds.
2. During {\textsc{Delete}}(v) , we only add v v v to D D D until we reach line line:delete_cond with ℓ = i \ell = i ℓ = i . Hence, we have E ^ i / = E ^ i − ∖ { v } \hat{E}_{i}^{/} = \hat{E}_{i}^{-} \setminus \{v\} E ^ i / = E ^ i − ∖ { v } and E ^ i + 1 / = E ^ i + 1 − ∖ { v } \hat{E}_{i + 1}^{/} = \hat{E}_{i + 1}^{-} \setminus \{v\} E ^ i + 1 / = E ^ i + 1 − ∖ { v } . Therefore, the assumption (2) clearly implies equation (1) .
This proves the claim in the case where {\textsc{LayerConstruct}}(i) is not invoked, thus completing the entire proof. ◻
The next lemma establishes T T T as the number of non-empty layers in our data structure.
Lemma 6. The following holds: E T + 1 = ∅ E_{T + 1} = \emptyset E T + 1 = ∅ , and if T > 0 T > 0 T > 0 then E T ≠ ∅ E_{T} \neq \emptyset E T = ∅ .
Proof. Consider the entire execution of the algorithm. The statement holds at the beginning, as initially T = 0 T = 0 T = 0 and E 1 = ∅ E_{1} = \emptyset E 1 = ∅ .
Both update procedures, {\textsc{Insert}}(e) and {\textsc{Delete}}(e) , may change T T T and E T + 1 E_{T + 1} E T + 1 only through a call to the procedure {\textsc{LayerConstruct}} . Consider the last update that triggers a call to {\textsc{LayerConstruct}} , and let i i i denote its corresponding layer number, i.e., {\textsc{Insert}}(e) or {\textsc{Delete}}(e) has called {\textsc{LayerConstruct}}(i) . Note that if no such update occurs, then T T T and E 1 E_{1} E 1 have not changed since the beginning.
Invocation of {\textsc{LayerConstruct}}(i) implies that the condition in line line:insert_checkforconstruct or line:delete_cond did not hold for 1 ≤ j < i 1 \le j < i 1 ≤ j < i , which guarantees E j ≠ ∅ E_{j} \neq \emptyset E j = ∅ for all 1 ≤ j < i 1 \leq j < i 1 ≤ j < i . Each call to {\textsc{LayerConstruct}}(\ell) is followed by a call to {\textsc{LayerConstruct}}(\ell + 1) , continuing until reaching {\textsc{LayerConstruct}}(h) (h ≥ i h \geq i h ≥ i ) with E h = ∅ E_{h} = \emptyset E h = ∅ . During {\textsc{LayerConstruct}}(h) , the value of T T T is updated to h − 1 h - 1 h − 1 , ensuring that E T + 1 = ∅ E_{T + 1} = \emptyset E T + 1 = ∅ , while E j ≠ ∅ E_{j} \neq \emptyset E j = ∅ for all 1 ≤ j ≤ T 1 \leq j \leq T 1 ≤ j ≤ T . By our selection of the last update that triggers a call to {\textsc{LayerConstruct}} , we conclude that no further changes have been made to T T T or E T + 1 E_{T + 1} E T + 1 thereafter. ◻
This final lemma characterizes the structural properties of our data structure imposed by the reconstruction conditions.
Lemma 7. The following hold: ∣ B i ∩ D ∣ ≤ ϵ del ∣ B i ∣ , For all i ∈ [ T ] , ∣ A i ∣ ≤ ϵ ins ∣ E i ∣ . For all i ∈ [ T + 1 ] . \begin{aligned}
&|B_i \cap D| \leq \epsilon_{\textnormal{del}}|B_i|, &\text{For all \( i \in [T] \),}\\
&|A_i| \leq \epsilon_{\textnormal{ins}}|E_i|.& \text{For all \( i \in [T + 1]. \)}
\end{aligned} ∣ B i ∩ D ∣ ≤ ϵ del ∣ B i ∣ , ∣ A i ∣ ≤ ϵ ins ∣ E i ∣. For all i ∈ [ T ] , For all i ∈ [ T + 1 ] .
Proof. Consider a fixed i ∈ [ T ] i \in [T] i ∈ [ T ] . Consider the most recent call to {\textsc{LayerConstruct}}(i) . Immediately after its execution, we have B i ∩ D = ∅ B_i \cap D = \emptyset B i ∩ D = ∅ . This holds because E i E_i E i was set to ( E i ∪ A i ) ∖ D (E_i \cup A_i) \setminus D ( E i ∪ A i ) ∖ D , and B i ⊆ E i B_i \subseteq E_i B i ⊆ E i .
Since any call to {\textsc{LayerConstruct}}(\ell) with ℓ < i \ell < i ℓ < i also triggers a call to {\textsc{LayerConstruct}}(i) , our selection of the most recent call to {\textsc{LayerConstruct}}(i) implies that during all subsequent executions of {\textsc{Delete}}(e) , we reached line line:delete_cond with ℓ = i \ell = i ℓ = i without invoking {\textsc{LayerConstruct}}(i) , meaning that the first condition was satisfied. We also know that no subsequent {\textsc{Insert}}(e) could be the first update to violate condition 1, as insertions do not modify B i B_i B i or D D D .
We make the same argument for insertions, but with a fixed i ∈ [ T + 1 ] i \in [T + 1] i ∈ [ T + 1 ] . We consider the most recent call to {\textsc{LayerConstruct}}(i) . Immediately after its execution, we have A i = ∅ A_i = \emptyset A i = ∅ . During each subsequent insertion, we reached the line line:insert_checkforconstruct with ℓ = i \ell = i ℓ = i , and {\textsc{LayerConstruct}}(i) was not invoked, meaning that the second condition was satisfied. Moreover, no subsequent {\textsc{Delete}}(v) could be the first update to violate condition 2, as deletions do not modify E i E_i E i or A i A_i A i .
Therefore, both conditions still hold. ◻
Approximation
This section initiates the analysis of the approximation ratio guaranteed by our algorithm. (Note that parts of this analysis draw inspiration from [44 ] .) We begin by formalizing the contribution of each element to the overall objective by introducing a weight function that quantifies the marginal significance of elements according to their state in the data structure.
Definition 8. We define the weight function w : N → R w: \mathcal{N} \to \mathbb{R} w : N → R as follows:
For e ∈ I ∪ T e \in {I^{\cup}}_T e ∈ I ∪ T , set w ( e ) = Δ T ( e ) w(e) = \Delta_T(e) w ( e ) = Δ T ( e ) .
For e ∉ I ∪ T e \notin {I^{\cup}}_T e ∈ / I ∪ T , set w ( e ) = f ( e ∣ I ∪ T ) w(e) = f(e | {I^{\cup}}_T) w ( e ) = f ( e ∣ I ∪ T ) .
We also extend the definition of the weight function to sets by defining the total weight of a subset S ⊆ N S \subseteq \mathcal{N} S ⊆ N as w ( S ) : = ∑ e ∈ S w ( e ) , w(S) := \sum_{e \in S} w(e), w ( S ) := ∑ e ∈ S w ( e ) , with the convention that w ( ∅ ) : = 0 w(\emptyset) := 0 w ( ∅ ) := 0 2 .
The following lemma demonstrates that when an element e e e gets accepted into, or already belongs to, the union set I ∪ {I^{\cup}} I ∪ during the execution of the {\textsc{Expand}} procedure, its associated marginal value Δ ( e ) \Delta(e) Δ ( e ) remains fixed.
Lemma 9. Consider the execution of {\textsc{Expand}}(S_{\ell}, (I, {I^{\cup}}, \Delta)_{\ell, 0}, \tau_{\ell}) with τ ℓ > 0 \tau_{\ell} > 0 τ ℓ > 0 . Let e 1 , e 2 , … , e ∣ S ℓ ∣ e_1, e_2, \ldots, e_{{\left|S_{\ell} \right|}} e 1 , e 2 , … , e ∣ S ℓ ∣ denote the elements of S ℓ S_{\ell} S ℓ in their processing order. For any η ∈ [ ∣ S ℓ ∣ ] \eta \in [{\left|S_{\ell} \right|}] η ∈ [ ∣ S ℓ ∣ ] , let ( I , I ∪ , Δ ) ℓ , η (I, {I^{\cup}}, \Delta)_{\ell, \eta} ( I , I ∪ , Δ ) ℓ , η denote the state of ( I , I ∪ , Δ ) ′ (I, {I^{\cup}}, \Delta)' ( I , I ∪ , Δ ) ′ immediately after processing e η e_{\eta} e η . If e ∈ I ∪ ℓ , i e \in {I^{\cup}}_{\ell, i} e ∈ I ∪ ℓ , i for some i ∈ [ 0 , ∣ S ℓ ∣ ] i \in [0, {\left|S_{\ell} \right|}] i ∈ [ 0 , ∣ S ℓ ∣ ] , then Δ ℓ , i ( e ) = Δ ℓ , ∣ S ℓ ∣ ( e ) . \Delta_{\ell, i}(e) = \Delta_{\ell, {\left|S_{\ell} \right|}}(e). Δ ℓ , i ( e ) = Δ ℓ , ∣ S ℓ ∣ ( e ) .
Informally, once e ∈ I ∪ e \in {I^{\cup}} e ∈ I ∪ , the {\textsc{Expand}} procedure preserves the value of Δ ( e ) \Delta(e) Δ ( e ) within that layer.
Proof. First, observe that {\textsc{Expand}}(S_{\ell}, (I, {I^{\cup}}, \Delta)_{\ell, 0}, \tau_{\ell}) initializes ( I , I ∪ , Δ ) ′ (I, {I^{\cup}}, \Delta)' ( I , I ∪ , Δ ) ′ as a copy of ( I , I ∪ , Δ ) ℓ , 0 (I, {I^{\cup}}, \Delta)_{\ell, 0} ( I , I ∪ , Δ ) ℓ , 0 , and that ( I , I ∪ , Δ ) ℓ , η (I, {I^{\cup}}, \Delta)_{\ell, \eta} ( I , I ∪ , Δ ) ℓ , η denotes the state of ( I , I ∪ , Δ ) ′ (I, {I^{\cup}}, \Delta)' ( I , I ∪ , Δ ) ′ immediately after processing e η e_{\eta} e η . Therefore, for all η ∈ [ ∣ S ℓ ∣ ] \eta \in [{\left|S_{\ell} \right|}] η ∈ [ ∣ S ℓ ∣ ] , we have
\begin{align}
(I, {I^{\cup}}, \Delta)_{\ell, \eta} = {\textsc{Adjust}}(e_{\eta}, (I, {I^{\cup}}, \Delta)_{\ell, \eta - 1}, \tau_{\ell}). \tag*{(4)}
\end{align}
Suppose, for the sake of contradiction, that Δ ℓ , i ( e ) ≠ Δ ℓ , ∣ S ℓ ∣ ( e ) \Delta_{\ell, i}(e) \ne \Delta_{\ell, {\left|S_{\ell} \right|}}(e) Δ ℓ , i ( e ) = Δ ℓ , ∣ S ℓ ∣ ( e ) . Then there must exist some index j j j such that i < j ≤ ∣ S ℓ ∣ i < j \le {\left|S_{\ell} \right|} i < j ≤ ∣ S ℓ ∣ and Δ ℓ , j ( e ) ≠ Δ ℓ , j − 1 ( e ) \Delta_{\ell, j}(e) \ne \Delta_{\ell, j - 1}(e) Δ ℓ , j ( e ) = Δ ℓ , j − 1 ( e ) .
By (4) , we have
(I, {I^{\cup}}, \Delta)_{\ell, j} = {\textsc{Adjust}}(e_j, (I, {I^{\cup}}, \Delta)_{\ell, j - 1}, \tau_{\ell}).
The procedure {\textsc{Adjust}}(e_j, \cdot, \tau_{\ell}) may only change the value of Δ ′ \Delta' Δ ′ at the element e j e_j e j . Therefore, for Δ ℓ , j ( e ) ≠ Δ ℓ , j − 1 ( e ) \Delta_{\ell, j}(e) \ne \Delta_{\ell, j - 1}(e) Δ ℓ , j ( e ) = Δ ℓ , j − 1 ( e ) to hold, it must be the case that e j = e e_j = e e j = e .
One may argue that given that e ∈ I ∪ ℓ , i e \in {I^{\cup}}_{\ell, i} e ∈ I ∪ ℓ , i and i < j i < j i < j this may never happen. However, we prove the Lemma without any further assumption on S ℓ S_{\ell} S ℓ .
We show that even if e j = e e_j = e e j = e , the call {\textsc{Adjust}}(e, (I, {I^{\cup}}, \Delta)_{\ell, j - 1}, \tau_{\ell}) does not change the value of Δ ′ \Delta' Δ ′ at element e e e . This is because such an update requires that \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{\ell, j - 1}, \tau_{\ell}) \ne \textsc{Fail} , which in turn requires:
f ( e ∣ I ∪ ℓ , j − 1 ) ≥ τ ℓ > 0. f(e | {I^{\cup}}_{\ell, j - 1}) \ge \tau_{\ell} > 0. f ( e ∣ I ∪ ℓ , j − 1 ) ≥ τ ℓ > 0. However, e ∈ I ∪ ℓ , i e \in {I^{\cup}}_{\ell, i} e ∈ I ∪ ℓ , i and i < j i < j i < j , implies I ∪ ℓ , i ⊆ I ∪ ℓ , j − 1 {I^{\cup}}_{\ell, i} \subseteq {I^{\cup}}_{\ell, j - 1} I ∪ ℓ , i ⊆ I ∪ ℓ , j − 1 . Therefore, e ∈ I ∪ ℓ , j − 1 e \in {I^{\cup}}_{\ell, j - 1} e ∈ I ∪ ℓ , j − 1 , and by definition, f ( e ∣ I ∪ ℓ , j − 1 ) = 0 f(e | {I^{\cup}}_{\ell, j - 1}) = 0 f ( e ∣ I ∪ ℓ , j − 1 ) = 0 .
This contradiction implies that Δ ℓ , j ( e ) = Δ ℓ , j − 1 ( e ) \Delta_{\ell, j}(e) = \Delta_{\ell, j - 1}(e) Δ ℓ , j ( e ) = Δ ℓ , j − 1 ( e ) for all j > i j > i j > i , and hence Δ ℓ , i ( e ) = Δ ℓ , ∣ S ℓ ∣ ( e ) \Delta_{\ell, i}(e) = \Delta_{\ell, {\left|S_{\ell} \right|}}(e) Δ ℓ , i ( e ) = Δ ℓ , ∣ S ℓ ∣ ( e ) , as claimed. ◻
We now use the above lemma to relate the weight assigned to each element to its recorded Δ \Delta Δ value across the different layers of the data structure, illustrating their alignment.
Lemma 10. If e ∈ I ∪ i e \in {I^{\cup}}_{i} e ∈ I ∪ i , then w ( e ) = Δ i ( e ) w(e) = \Delta_i({e}) w ( e ) = Δ i ( e ) .
Proof. We show that given e ∈ I ∪ i e \in {I^{\cup}}_i e ∈ I ∪ i , we have Δ T ( e ) = Δ i ( e ) \Delta_T(e) = \Delta_i(e) Δ T ( e ) = Δ i ( e ) . Fix any index h ∈ ( i , T ] h \in (i, T] h ∈ ( i , T ] . By Lemma (?) , we have:
\begin{align}
(I, {I^{\cup}}, \Delta)_{h} = {\textsc{Expand}}(S_{h}, (I, {I^{\cup}}, \Delta)_{h-1}, \tau_{h}). \tag*{(5)}
\end{align}
Consider the execution of {\textsc{Expand}}(S_{h}, (I, {I^{\cup}}, \Delta)_{h-1}, \tau_{h}) as described in Lemma 9 , by setting:
S ℓ = S h , ( I , I ∪ , Δ ) ℓ , 0 = ( I , I ∪ , Δ ) h , 0 = ( I , I ∪ , Δ ) h − 1 , τ ℓ = τ h . S_{\ell} = S_{h}, \quad (I, {I^{\cup}}, \Delta)_{\ell,0} = (I, {I^{\cup}}, \Delta)_{h,0} = (I, {I^{\cup}}, \Delta)_{h-1}, \quad \tau_{\ell} = \tau_{h}. S ℓ = S h , ( I , I ∪ , Δ ) ℓ , 0 = ( I , I ∪ , Δ ) h , 0 = ( I , I ∪ , Δ ) h − 1 , τ ℓ = τ h . Let e 1 , e 2 , … , e ∣ S h ∣ e_1, e_2, \ldots, e_{{\left|S_{h} \right|}} e 1 , e 2 , … , e ∣ S h ∣ denote the elements of S h S_{h} S h in their processing order. For any j ∈ [ ∣ S h ∣ ] j \in [{\left|S_{h} \right|}] j ∈ [ ∣ S h ∣ ] , let ( I , I ∪ , Δ ) h , j (I, {I^{\cup}}, \Delta)_{h,j} ( I , I ∪ , Δ ) h , j denote the state of ( I , I ∪ , Δ ) ′ (I, {I^{\cup}}, \Delta)' ( I , I ∪ , Δ ) ′ immediately after processing e j e_j e j . Lemma 9 states that if e ∈ I ∪ h , q e \in {I^{\cup}}_{h,q} e ∈ I ∪ h , q for some q ∈ [ 0 , ∣ S h ∣ ] q \in [0, {\left|S_{h} \right|}] q ∈ [ 0 , ∣ S h ∣ ] , then:
Δ h , q ( e ) = Δ h , ∣ S h ∣ ( e ) = Δ h ( e ) . \Delta_{h,q}(e) = \Delta_{h,{\left|S_{h} \right|}}(e) = \Delta_h(e). Δ h , q ( e ) = Δ h , ∣ S h ∣ ( e ) = Δ h ( e ) . Since h > i h > i h > i , the condition e ∈ I ∪ h , q e \in {I^{\cup}}_{h, q} e ∈ I ∪ h , q holds for q = 0 q = 0 q = 0 as I ∪ h , 0 = I ∪ h − 1 {I^{\cup}}_{h, 0} = {I^{\cup}}_{h - 1} I ∪ h , 0 = I ∪ h − 1 , and by Lemma 40 e ∈ I ∪ i e \in {I^{\cup}}_{i} e ∈ I ∪ i implies e ∈ I ∪ h − 1 e \in {I^{\cup}}_{h - 1} e ∈ I ∪ h − 1 . Thus, by Lemma 9 we have:
Δ h − 1 ( e ) = Δ h ( e ) . \Delta_{h - 1}(e) = \Delta_{h}(e). Δ h − 1 ( e ) = Δ h ( e ) . By induction over h h h from i + 1 i + 1 i + 1 to T T T , we conclude that Δ i ( e ) = Δ T ( e ) \Delta_i(e) = \Delta_T(e) Δ i ( e ) = Δ T ( e ) .
By Lemma 40 , we have I ∪ i ⊆ I ∪ T {I^{\cup}}_i \subseteq {I^{\cup}}_T I ∪ i ⊆ I ∪ T . Hence, e ∈ I ∪ i e \in {I^{\cup}}_i e ∈ I ∪ i implies e ∈ I ∪ T e \in {I^{\cup}}_T e ∈ I ∪ T . By Definition 8 , the weight function for an element e ∈ I ∪ T e \in {I^{\cup}}_T e ∈ I ∪ T is defined as w ( e ) = Δ T ( e ) w(e) = \Delta_T(e) w ( e ) = Δ T ( e ) . We also have established that given e ∈ I ∪ i e \in {I^{\cup}}_i e ∈ I ∪ i , Δ T ( e ) = Δ i ( e ) \Delta_T(e) = \Delta_i(e) Δ T ( e ) = Δ i ( e ) . Combined together, it follows that w ( e ) = Δ i ( e ) w(e) = \Delta_i(e) w ( e ) = Δ i ( e ) , as claimed. ◻
We now proceed to derive bounds between the weight function or the objective function values corresponding to various sets maintained in our data structure and the optimal solution.
Lemma 11. The following holds: w ( I ∪ T ) ≤ 2 w ( I T ) w({I^{\cup}}_{T}) \le 2w(I_{T}) w ( I ∪ T ) ≤ 2 w ( I T ) .
Proof. We prove by induction on i i i that w ( I ∪ i ) ≤ 2 w ( I i ) w({I^{\cup}}_i) \le 2w(I_i) w ( I ∪ i ) ≤ 2 w ( I i ) for all i ∈ [ 0 , T ] i \in [0, T] i ∈ [ 0 , T ] .
For the base case (i = 0 i = 0 i = 0 ), we know by Lemma (?) that I 0 = I ∪ 0 = ∅ I_0 = {I^{\cup}}_0 = \emptyset I 0 = I ∪ 0 = ∅ . This, by Definition 8 , implies that w ( I ∪ 0 ) = w ( I 0 ) = w ( ∅ ) w({I^{\cup}}_0) = w(I_0) = w(\emptyset) w ( I ∪ 0 ) = w ( I 0 ) = w ( ∅ ) , so the inequality holds trivially.
Now, for the inductive step, we show that w ( I ∪ i ) ≤ 2 w ( I i ) w({I^{\cup}}_i) \le 2w(I_i) w ( I ∪ i ) ≤ 2 w ( I i ) using the inductive hypothesis, which assumes the claim holds for i − 1 i - 1 i − 1 , i.e., w ( I ∪ i − 1 ) ≤ 2 w ( I i − 1 ) w({I^{\cup}}_{i-1}) \le 2w(I_{i-1}) w ( I ∪ i − 1 ) ≤ 2 w ( I i − 1 ) . To this end, it suffices to show that
w ( I ∪ i ) − w ( I ∪ i − 1 ) ≤ 2 ( w ( I i ) − w ( I i − 1 ) ) . w({I^{\cup}}_i) - w({I^{\cup}}_{i-1}) \le 2(w(I_i) - w(I_{i-1})). w ( I ∪ i ) − w ( I ∪ i − 1 ) ≤ 2 ( w ( I i ) − w ( I i − 1 )) . By Lemma (?) , we have
(I, {I^{\cup}}, \Delta)_{i} = {\textsc{Expand}}(S_{i}, (I, {I^{\cup}}, \Delta)_{i - 1}, \tau_{i}),
where {\textsc{Expand}} constructs ( I , I ∪ , Δ ) i (I, {I^{\cup}}, \Delta)_{i} ( I , I ∪ , Δ ) i by iteratively modifying a copy of ( I , I ∪ , Δ ) i − 1 (I, {I^{\cup}}, \Delta)_{i - 1} ( I , I ∪ , Δ ) i − 1 via calls to {\textsc{Adjust}} for each e ∈ S i e \in S_{i} e ∈ S i .
Within {\textsc{Adjust}} , each element is sent through inspection, which can result in one of three possible outcomes.
If an element e e e fails the test in \textsc{Inspect} , it is not added to either I ∪ {I^{\cup}} I ∪ or I I I , and thus contributes nothing to either w ( I ∪ i ) − w ( I ∪ i − 1 ) w({I^{\cup}}_i) - w({I^{\cup}}_{i-1}) w ( I ∪ i ) − w ( I ∪ i − 1 ) or w ( I i ) − w ( I i − 1 ) w(I_i) - w(I_{i-1}) w ( I i ) − w ( I i − 1 ) .
Elements that pass the test in \textsc{Inspect} and can be added to I I I without any replacement are added to both I ∪ {I^{\cup}} I ∪ and I I I , and thus contribute an equal amount of weight to both w ( I ∪ i ) − w ( I ∪ i − 1 ) w({I^{\cup}}_i) - w({I^{\cup}}_{i-1}) w ( I ∪ i ) − w ( I ∪ i − 1 ) and w ( I i ) − w ( I i − 1 ) w(I_i) - w(I_{i-1}) w ( I i ) − w ( I i − 1 ) .
Thus, it remains to examine the case where an element e e e passes the \textsc{Inspect} test and is added to both I ∪ {I^{\cup}} I ∪ and I I I while replacing another element e ^ \hat{e} e ^ in I I I .
It suffices to show that in such cases the following holds:
w ( e ) ≤ 2 ( w ( e ) − w ( e ^ ) ) . w(e) \le 2 (w(e) - w(\hat{e})). w ( e ) ≤ 2 ( w ( e ) − w ( e ^ )) . For such elements e e e and e ^ \hat{e} e ^ , since both belong to I ∪ i {I^{\cup}}_i I ∪ i and I ∪ i ⊆ I ∪ T {I^{\cup}}_i \subseteq {I^{\cup}}_T I ∪ i ⊆ I ∪ T by Lemma 40 , we have e , e ^ ∈ I ∪ T e, \hat{e} \in {I^{\cup}}_T e , e ^ ∈ I ∪ T . Hence, by Lemma 10 , it follows that w ( e ) = Δ i ( e ) w(e) = \Delta_i({e}) w ( e ) = Δ i ( e ) and w ( e ^ ) = Δ i ( e ^ ) w(\hat{e}) = \Delta_i(\hat{e}) w ( e ^ ) = Δ i ( e ^ ) . Therefore, it suffices to show that
Δ i ( e ) ≥ 2 Δ i ( e ^ ) . \Delta_i({e}) \ge 2\Delta_i(\hat{e}). Δ i ( e ) ≥ 2 Δ i ( e ^ ) . We know that in such cases for the {\textsc{Adjust}} procedure, during the \textsc{Inspect} test, it is verified that 2 Δ ( e ^ ) ≤ f ( e ∣ I ∪ ) 2\Delta(\hat{e}) \le f(e | {I^{\cup}}) 2Δ ( e ^ ) ≤ f ( e ∣ I ∪ ) . Immediately after the inspection Δ ( e ) \Delta({e}) Δ ( e ) is set to f ( e ∣ I ∪ ) f(e | {I^{\cup}}) f ( e ∣ I ∪ ) , and then I I I and I ∪ {I^{\cup}} I ∪ are modified accordingly. Once the {\textsc{Adjust}} completes, the followings hold for the updated ( I , I ∪ , Δ ) ′ (I, {I^{\cup}}, \Delta)' ( I , I ∪ , Δ ) ′ within the {\textsc{Expand}} :
e , e ^ ∈ I ∪ ′ , and Δ ′ ( e ) ≥ 2 Δ ′ ( e ^ ) . e, \hat{e} \in {I^{\cup}}', \quad \text{and} \quad \Delta'(e) \ge 2 \Delta'(\hat{e}). e , e ^ ∈ I ∪ ′ , and Δ ′ ( e ) ≥ 2 Δ ′ ( e ^ ) . By Lemma 9 , we know that once an element is included in I ∪ ′ {I^{\cup}}' I ∪ ′ , its corresponding Δ \Delta Δ remains unchanged during the execution of {\textsc{Expand}} . Therefore, we have
Δ i ( e ) ≥ 2 Δ i ( e ^ ) , \Delta_i({e}) \ge 2\Delta_i(\hat{e}), Δ i ( e ) ≥ 2 Δ i ( e ^ ) , completing the proof. ◻
Lemma 12. The following holds: f ( I ∪ T ) = w ( I ∪ T ) f({I^{\cup}}_{T}) = w({I^{\cup}}_{T}) f ( I ∪ T ) = w ( I ∪ T ) .
Proof. Similar to Lemma 11 , we use an induction on i i i , and prove that w ( I ∪ i ) = f ( I ∪ i ) w({I^{\cup}}_i) = f({I^{\cup}}_i) w ( I ∪ i ) = f ( I ∪ i ) for all i ∈ [ 0 , T ] i \in [0, T] i ∈ [ 0 , T ] .
For the base case (i = 0 i = 0 i = 0 ), we know by Lemma (?) that I ∪ 0 = ∅ {I^{\cup}}_0 = \emptyset I ∪ 0 = ∅ , and by Definition 8 , we have w ( ∅ ) = f ( ∅ ) w(\emptyset) = f(\emptyset) w ( ∅ ) = f ( ∅ ) . Thus, the base case holds.
For the inductive step, we assume that the claim holds for i − 1 i - 1 i − 1 , i.e., w ( I ∪ i − 1 ) = f ( I ∪ i − 1 ) w({I^{\cup}}_{i-1}) = f({I^{\cup}}_{i-1}) w ( I ∪ i − 1 ) = f ( I ∪ i − 1 ) , and prove that w ( I ∪ i ) = f ( I ∪ i ) w({I^{\cup}}_i) = f({I^{\cup}}_i) w ( I ∪ i ) = f ( I ∪ i ) . It suffices to show that:
w ( I ∪ i ) − w ( I ∪ i − 1 ) = f ( I ∪ i ) − f ( I ∪ i − 1 ) . \begin{align}
w({I^{\cup}}_i) - w({I^{\cup}}_{i-1}) = f({I^{\cup}}_i) - f({I^{\cup}}_{i-1}). \tag*{(6)}
\end{align} w ( I ∪ i ) − w ( I ∪ i − 1 ) = f ( I ∪ i ) − f ( I ∪ i − 1 ) . (6) By Lemma (?) , we have
(I, {I^{\cup}}, \Delta)_i = {\textsc{Expand}}(S_i, (I, {I^{\cup}}, \Delta)_{i-1}, \tau_i).
The procedure {\textsc{Expand}}(S_i, (I, {I^{\cup}}, \Delta)_{i-1}, \tau_i) initializes ( I , I ∪ , Δ ) ′ (I, {I^{\cup}}, \Delta)' ( I , I ∪ , Δ ) ′ as a copy of ( I , I ∪ , Δ ) i − 1 (I, {I^{\cup}}, \Delta)_{i-1} ( I , I ∪ , Δ ) i − 1 , then sequentially modifies it via calls to {\textsc{Adjust}} for each e ∈ S i e \in S_i e ∈ S i , and uses it to set the value of ( I , I ∪ , Δ ) i (I, {I^{\cup}}, \Delta)_i ( I , I ∪ , Δ ) i at the end. Let e 1 , e 2 , … , e ∣ S i ∣ e_1, e_2, \ldots, e_{{\left|S_{i} \right|}} e 1 , e 2 , … , e ∣ S i ∣ denote the elements of S i S_i S i in the order they are processed. For each j ∈ [ ∣ S i ∣ ] j \in [{\left|S_{i} \right|}] j ∈ [ ∣ S i ∣ ] , let I ∪ i , j {I^{\cup}}_{i, j} I ∪ i , j denote the state of I ∪ ′ {I^{\cup}}' I ∪ ′ immediately after processing e j e_j e j . This inherently implies that I ∪ i , ∣ S i ∣ {I^{\cup}}_{i, {\left|S_{i} \right|}} I ∪ i , ∣ S i ∣ = I ∪ i {I^{\cup}}_{i} I ∪ i . We also use I ∪ i , 0 {I^{\cup}}_{i, 0} I ∪ i , 0 to denote I ∪ i − 1 {I^{\cup}}_{i - 1} I ∪ i − 1 .
Then, the equality (6) , which we aim to prove can be rewritten as:
∑ j = 1 ∣ S i ∣ ( w ( I ∪ i , j ) − w ( I ∪ i , j − 1 ) ) = ∑ j = 1 ∣ S i ∣ ( f ( I ∪ i , j ) − f ( I ∪ i , j − 1 ) ) . \begin{align}
\sum_{j=1}^{|S_i|} \left( w({I^{\cup}}_{i,j}) - w({I^{\cup}}_{i,j-1}) \right)
= \sum_{j=1}^{|S_i|} \left( f({I^{\cup}}_{i,j}) - f({I^{\cup}}_{i,j-1}) \right). \tag*{(7)}
\end{align} j = 1 ∑ ∣ S i ∣ ( w ( I ∪ i , j ) − w ( I ∪ i , j − 1 ) ) = j = 1 ∑ ∣ S i ∣ ( f ( I ∪ i , j ) − f ( I ∪ i , j − 1 ) ) . (7) Now, we consider the outcome of the call to {\textsc{Adjust}} on each element e j e_j e j :
If e j e_j e j fails the test in \textsc{Inspect} , then I ∪ i , j = I ∪ i , j − 1 {I^{\cup}}_{i,j} = {I^{\cup}}_{i,j-1} I ∪ i , j = I ∪ i , j − 1 , so the terms corresponding to e j e_j e j on both sides of (7) are equal to zero.
Assuming e j e_j e j passes the \textsc{Inspect} test, the following hold:
I ∪ i , j = I ∪ i , j − 1 ∪ { e j } {I^{\cup}}_{i,j} = {I^{\cup}}_{i,j-1} \cup \{e_j\} I ∪ i , j = I ∪ i , j − 1 ∪ { e j } ,
e j ∉ I ∪ i , j − 1 e_j \notin {I^{\cup}}_{i,j-1} e j ∈ / I ∪ i , j − 1 .
Property (b) follows because if e j ∈ I ∪ i , j − 1 e_j \in {I^{\cup}}_{i,j-1} e j ∈ I ∪ i , j − 1 , then f ( e j ∣ I ∪ i , j − 1 ) f(e_j | {I^{\cup}}_{i,j-1}) f ( e j ∣ I ∪ i , j − 1 ) would be zero, contradicting the fact that e j e_j e j passed the inspect test, which requires f ( e j ∣ I ∪ i , j − 1 ) ≥ τ i f(e_j | {I^{\cup}}_{i,j-1}) \ge \tau_i f ( e j ∣ I ∪ i , j − 1 ) ≥ τ i .
From Definition 8 , together with (a) and (b), we have:
w ( I ∪ i , j ) − w ( I ∪ i , j − 1 ) = w ( e j ) = Δ i ( e j ) , \begin{align}
w({I^{\cup}}_{i,j}) - w({I^{\cup}}_{i,j-1}) = w(e_j) = \Delta_i(e_j), \tag*{(8)}
\end{align} w ( I ∪ i , j ) − w ( I ∪ i , j − 1 ) = w ( e j ) = Δ i ( e j ) , (8) where the second equality follows from Lemma 10 and the fact that e j ∈ I ∪ i e_j \in {I^{\cup}}_i e j ∈ I ∪ i .
Additionally, by the definition of relative contribution and using (a), we have:
f ( I ∪ i , j ) − f ( I ∪ i , j − 1 ) = f ( e j ∣ I ∪ i , j − 1 ) . \begin{align}
f({I^{\cup}}_{i,j}) - f({I^{\cup}}_{i,j-1}) = f(e_j | {I^{\cup}}_{i,j-1}). \tag*{(9)}
\end{align} f ( I ∪ i , j ) − f ( I ∪ i , j − 1 ) = f ( e j ∣ I ∪ i , j − 1 ) . (9) Immediately after the completion of the {\textsc{Adjust}} procedure for e j e_j e j , we have:
Δ ′ ( e j ) = f ( e j ∣ I ∪ i , j − 1 ) . \Delta'(e_j) = f(e_j | {I^{\cup}}_{i,j-1}). Δ ′ ( e j ) = f ( e j ∣ I ∪ i , j − 1 ) . By Lemma 9 , we know that throughout the execution of {\textsc{Expand}} , once an element is included in I ∪ ′ {I^{\cup}}' I ∪ ′ , its corresponding Δ \Delta Δ value remains unchanged. Hence,
Δ i ( e j ) = f ( e j ∣ I ∪ i , j − 1 ) . \Delta_i(e_j) = f(e_j | {I^{\cup}}_{i,j-1}). Δ i ( e j ) = f ( e j ∣ I ∪ i , j − 1 ) . Therefore, using this together with Equations (8) and (9) , we conclude:
w ( I ∪ i , j ) − w ( I ∪ i , j − 1 ) = f ( I ∪ i , j ) − f ( I ∪ i , j − 1 ) . w({I^{\cup}}_{i,j}) - w({I^{\cup}}_{i,j-1}) = f({I^{\cup}}_{i,j}) - f({I^{\cup}}_{i,j-1}). w ( I ∪ i , j ) − w ( I ∪ i , j − 1 ) = f ( I ∪ i , j ) − f ( I ∪ i , j − 1 ) . Since, regardless of the case, each pair of corresponding terms in (7) is equal, the equality holds. This completes the inductive step and the proof. ◻
Lemma 13. Let I ∗ I^* I ∗ denote the optimal solution at the current time. The following holds: f ( I ∗ ) ≤ 2 w ( I T ) + w ( I ∗ ∖ I ∪ T ) . f(I^*) \le 2w(I_T) + w(I^*\setminus {I^{\cup}}_T). f ( I ∗ ) ≤ 2 w ( I T ) + w ( I ∗ ∖ I ∪ T ) .
Proof. We begin by bounding the difference between f ( I ∗ ) f(I^*) f ( I ∗ ) and f ( I ∪ T ) f({I^{\cup}}_T) f ( I ∪ T ) . By submodularity of f f f , we have:
f ( I ∗ ) − f ( I ∪ T ) ≤ ∑ e ∈ I ∗ ∖ I ∪ T f ( e ∣ I ∪ T ) . f(I^*) - f({I^{\cup}}_T) \le \sum_{e \in I^*\setminus {I^{\cup}}_T} f(e | {I^{\cup}}_T). f ( I ∗ ) − f ( I ∪ T ) ≤ e ∈ I ∗ ∖ I ∪ T ∑ f ( e ∣ I ∪ T ) . By Definition 8 , for any element e e e that e ∉ I ∪ T e \notin {I^{\cup}}_T e ∈ / I ∪ T , the weight function is defined as w ( e ) = f ( e ∣ I ∪ T ) w(e) = f(e | {I^{\cup}}_T) w ( e ) = f ( e ∣ I ∪ T ) . Therefore, we have:
f ( I ∗ ) ≤ f ( I ∪ T ) + ∑ e ∈ I ∗ ∖ I ∪ T w ( e ) = f ( I ∪ T ) + w ( I ∗ ∖ I ∪ T ) , f(I^*) \le f({I^{\cup}}_T) + \sum_{e \in I^*\setminus {I^{\cup}}_T} w(e) = f({I^{\cup}}_T) + w(I^*\setminus {I^{\cup}}_T), %\le f(\uni_T) + w(\optInd), f ( I ∗ ) ≤ f ( I ∪ T ) + e ∈ I ∗ ∖ I ∪ T ∑ w ( e ) = f ( I ∪ T ) + w ( I ∗ ∖ I ∪ T ) , where the equality follows from Definition 8 for sets, which defines the total weight of a set of elements as the sum of their individual weights.
By Lemma 12 , we have f ( I ∪ T ) = w ( I ∪ T ) f({I^{\cup}}_T) = w({I^{\cup}}_T) f ( I ∪ T ) = w ( I ∪ T ) , and by Lemma 11 , we know w ( I ∪ T ) ≤ 2 w ( I T ) w({I^{\cup}}_T) \le 2w(I_T) w ( I ∪ T ) ≤ 2 w ( I T ) . Therefore, we have:
f ( I ∪ T ) ≤ 2 w ( I T ) . f({I^{\cup}}_T) \le 2w(I_T). f ( I ∪ T ) ≤ 2 w ( I T ) . Combining the above, we conclude that:
f ( I ∗ ) ≤ f ( I ∪ T ) + w ( I ∗ ∖ I ∪ T ) ≤ 2 w ( I T ) + w ( I ∗ ∖ I ∪ T ) , f(I^*) \le f({I^{\cup}}_T) + w(I^*
\setminus {I^{\cup}}_T) \le 2w(I_T) + w(I^*
\setminus {I^{\cup}}_T), f ( I ∗ ) ≤ f ( I ∪ T ) + w ( I ∗ ∖ I ∪ T ) ≤ 2 w ( I T ) + w ( I ∗ ∖ I ∪ T ) , as desired. ◻
The following lemma shows how the existence of a blocking subset in the independent set is preserved under the execution of the {\textsc{Adjust}} procedure for another element.
Lemma 14. Consider arbitrary elements e 1 e_1 e 1 and e 2 e_2 e 2 , and a set ( I , I ∪ , Δ ) (I, {I^{\cup}}, \Delta) ( I , I ∪ , Δ ) . Assume that f ( e 1 ∣ I ∪ ) ≥ τ f(e_1 | {I^{\cup}}) \ge \tau f ( e 1 ∣ I ∪ ) ≥ τ , but \textsc{Inspect}(e_1, (I, {I^{\cup}}, \Delta), \tau) = \textsc{Fail} . Let ( I , I ∪ , Δ ) ′ (I, {I^{\cup}}, \Delta)' ( I , I ∪ , Δ ) ′ be the output of {\textsc{Adjust}}(e_2, (I, {I^{\cup}}, \Delta), \tau) . Then, there exists a set N ⊆ I ′ N \subseteq I' N ⊆ I ′ such that N ∪ { e 1 } N \cup \left\{\,e_1\,\right\} N ∪ { e 1 } forms a circuit, and f ( e 1 ∣ I ∪ ′ ) < 2 Δ ′ ( e ′ ) f(e_1 | {I^{\cup}}') < 2\Delta'(e') f ( e 1 ∣ I ∪ ′ ) < 2 Δ ′ ( e ′ ) for all e ′ ∈ N e' \in N e ′ ∈ N .
Proof. Firstly, we note a few helpful facts for the proof.
1.We have I ∪ ⊆ I ∪ ′ {I^{\cup}}\subseteq {I^{\cup}}' I ∪ ⊆ I ∪ ′ , and the submodularity of the function f f f ensures that f ( e 1 ∣ I ∪ ′ ) ≤ f ( e 1 ∣ I ∪ ) f(e_1 | {I^{\cup}}') \le f(e_1 | {I^{\cup}}) f ( e 1 ∣ I ∪ ′ ) ≤ f ( e 1 ∣ I ∪ ) .
2.Δ \Delta Δ and Δ ′ \Delta' Δ ′ may only differ at e 2 e_2 e 2 .
3.The condition f ( e 1 ∣ I ∪ ′ ) < 2 Δ ( e ′ ) f(e_1 | {I^{\cup}}') < 2\Delta(e') f ( e 1 ∣ I ∪ ′ ) < 2Δ ( e ′ ) for all e ′ ∈ N e' \in N e ′ ∈ N is equivalent to
f ( e 1 ∣ I ∪ ′ ) < 2 Δ ′ ( e ^ ) for e ^ = arg min { Δ ′ ( e ′ ) : e ′ ∈ N } . f(e_1 | {I^{\cup}}') < 2\Delta'(\hat{e}) \text{ for }
\hat{e} = \arg\min \{ \Delta'(e') : e' \in N
\}. f ( e 1 ∣ I ∪ ′ ) < 2 Δ ′ ( e ^ ) for e ^ = arg min { Δ ′ ( e ′ ) : e ′ ∈ N } . Since f ( e 1 ∣ I ∪ ) ≥ τ f(e_1 | {I^{\cup}}) \ge \tau f ( e 1 ∣ I ∪ ) ≥ τ , but \textsc{Inspect}(e_1, (I, {I^{\cup}}, \Delta), \tau) = \textsc{Fail} , I ∪ { e 1 } I\cup \left\{\,e_1\,\right\} I ∪ { e 1 } must be dependent. We define C 1 C_1 C 1 as:
C 1 : = { e 1 } ∪ { e ′ ∈ I : I ∪ { e 1 } ∖ { e ′ } ∈ I } . C_1 := \left\{\,e_1\,\right\} \cup \left\{\,e' \in I:
I\cup \left\{\,e_1\,\right\} \setminus \left\{\,e'\,\right\} \in {\mathcal{I}}\,\right\}. C 1 := { e 1 } ∪ { e ′ ∈ I : I ∪ { e 1 } ∖ { e ′ } ∈ I } . We know that C 1 C_1 C 1 is the unique circuit in I ∪ { e 1 } I\cup \left\{\,e_1\,\right\} I ∪ { e 1 } . (It can be easily verified that each element in C 1 C_1 C 1 must be in a circuit, I ∪ { e 1 } I\cup \left\{\,e_1\,\right\} I ∪ { e 1 } contains only one circuit by Lemma 42 , and any element in the circuit is included in C 1 C_1 C 1 .) Since \textsc{Inspect}(e_1, (I, {I^{\cup}}, \Delta), \tau) = \textsc{Fail} , for the element e ^ ∈ C 1 ∖ { e 1 } \hat{e} \in C_1 \setminus \{e_1\} e ^ ∈ C 1 ∖ { e 1 } with minimum Δ \Delta Δ , we have:
f ( e 1 ∣ I ∪ ) < 2 Δ ( e ^ ) . f(e_1 | {I^{\cup}}) < 2 \Delta(\hat{e}). f ( e 1 ∣ I ∪ ) < 2Δ ( e ^ ) . Now, consider the {\textsc{Adjust}}(e_2, (I, {I^{\cup}}, \Delta), \tau) procedure. The {\textsc{Adjust}} procedure calls \textsc{Inspect}(e_2, (I, {I^{\cup}}, \Delta), \tau) . If the output is either \textsc{Fail} or ∅ \emptyset ∅ or { e ^ 2 } ⊈ C 1 \left\{\,\hat{e}_2\,\right\} \not\subseteq C_1 { e ^ 2 } ⊆ C 1 , the set C 1 ∖ { e 1 } C_1 \setminus \{e_1\} C 1 ∖ { e 1 } satisfies all the requirements for N N N . This is because in all these cases, C 1 ∖ { e 1 } ⊆ I ′ C_1 \setminus \{e_1\} \subseteq I' C 1 ∖ { e 1 } ⊆ I ′ , C 1 C_1 C 1 is a circuit and the facts imply that
f ( e 1 ∣ I ∪ ′ ) ≤ f ( e 1 ∣ I ∪ ) < 2 Δ ( e ^ ) = 2 Δ ′ ( e ^ ) for e ^ = arg min { Δ ′ ( e ′ ) : e ′ ∈ C 1 ∖ { e 1 } } . f(e_1 | {I^{\cup}}') \le f(e_1 | {I^{\cup}}) < 2 \Delta(\hat{e}) =
2\Delta'(\hat{e}) \text{ for } \hat{e} = \arg\min \{ \Delta'(e') : e' \in C_1 \setminus \{e_1\} \}. f ( e 1 ∣ I ∪ ′ ) ≤ f ( e 1 ∣ I ∪ ) < 2Δ ( e ^ ) = 2 Δ ′ ( e ^ ) for e ^ = arg min { Δ ′ ( e ′ ) : e ′ ∈ C 1 ∖ { e 1 }} . The only remaining case, is that if \textsc{Inspect}(e_2, (I, {I^{\cup}}, \Delta), \tau) returns { e 3 } \{e_3\} { e 3 } that e 3 ∈ C 1 e_3 \in C_1 e 3 ∈ C 1 . Let C 2 C_2 C 2 denote the circuit in I ∪ { e 2 } I\cup \left\{\,e_2\,\right\} I ∪ { e 2 } . We know that e 3 e_3 e 3 was the edge with minimum Δ \Delta Δ , and
Δ ′ ( e 2 ) = f ( e 2 ∣ I ∪ ) ≥ Δ ( e 3 ) = Δ ′ ( e 3 ) . \Delta'(e_2) = f(e_2 | {I^{\cup}}) \ge \Delta(e_3) = \Delta'(e_3). Δ ′ ( e 2 ) = f ( e 2 ∣ I ∪ ) ≥ Δ ( e 3 ) = Δ ′ ( e 3 ) . Moreover, since e 3 ∈ C 1 e_3 \in C_1 e 3 ∈ C 1 , for all e ′ ∈ C 1 ∪ C 2 ∖ { e 1 } e' \in C_1 \cup C_2 \setminus \{e_1\} e ′ ∈ C 1 ∪ C 2 ∖ { e 1 } , we have
f ( e 1 ∣ I ∪ ′ ) < 2 Δ ′ ( e ′ ) . f(e_1 | {I^{\cup}}') < 2\Delta'(e'). f ( e 1 ∣ I ∪ ′ ) < 2 Δ ′ ( e ′ ) . By Lemma 41 , there exists a circuit C 3 C_3 C 3 such that
C 3 ⊆ C 1 ∪ C 2 ∖ { e 3 } . C_3 \subseteq C_1 \cup C_2 \setminus \{e_3\}. C 3 ⊆ C 1 ∪ C 2 ∖ { e 3 } . We have established that C 3 ∖ { e 1 } C_3 \setminus \{e_1\} C 3 ∖ { e 1 } satisfies all the properties for N N N . The proof is complete. ◻
Combining the previous results and leveraging our carefully designed Algorithm alg:parallel alongside an elegant charging scheme yields a global bound on the optimum’s value in terms of the weight of I T I_T I T .
Lemma 15. Let I ∗ I^* I ∗ denote the optimal solution at the current time. There exists an instance I \mathcal{I} I in Algorithm alg:parallel , for which the following holds: ( 1 − ϵ 2 ) f ( I ∗ ) < 4 w ( I T ) . (1 - \frac{\epsilon}{2})f(I^*) < 4 w(I_T). ( 1 − 2 ϵ ) f ( I ∗ ) < 4 w ( I T ) .
Proof. Let’s assume that 2 i ∗ − 1 ≤ f ( I ∗ ) < 2 i ∗ . 2^{i^{*} - 1} \le f(I^*) < 2^{i^{*}}. 2 i ∗ − 1 ≤ f ( I ∗ ) < 2 i ∗ . In this Lemma, we bound w ( I ∗ ∖ I ∪ T ) w(I^*\setminus {I^{\cup}}_T) w ( I ∗ ∖ I ∪ T ) . Define I ≥ τ ∗ I^*_{\ge \tau} I ≥ τ ∗ and I < τ ∗ I^*_{< \tau} I < τ ∗ with τ = ϵ 4 k ⋅ 2 i ∗ \tau = \frac{\epsilon}{4k}\cdot 2^{i^*} τ = 4 k ϵ ⋅ 2 i ∗ , as follows:
I ≥ τ ∗ : = { e ∗ ∈ I ∗ ∖ I ∪ T : w ( e ∗ ) ≥ τ } , I < τ ∗ : = { e ∗ ∈ I ∗ ∖ I ∪ T : w ( e ∗ ) < τ } . \begin{align*}
I^*_{\ge \tau} := \{e^* \in I^*\setminus {I^{\cup}}_T : w(e^*) \ge \tau\},
\quad
I^*_{< \tau} := \{e^* \in I^*\setminus {I^{\cup}}_T : w(e^*) < \tau\}.
\end{align*} I ≥ τ ∗ := { e ∗ ∈ I ∗ ∖ I ∪ T : w ( e ∗ ) ≥ τ } , I < τ ∗ := { e ∗ ∈ I ∗ ∖ I ∪ T : w ( e ∗ ) < τ } . By definition of weight function for set, we have
w ( I < τ ∗ ) = ∑ e ∈ I < τ ∗ w ( e ) ≤ ∣ I < τ ∗ ∣ τ ≤ τ k , \begin{align*}
w(I^*_{< \tau}) =\sum_{e\in I^*_{< \tau}} w(e)
\le |I^*_{< \tau}|\tau \le \tau k,
\end{align*} w ( I < τ ∗ ) = e ∈ I < τ ∗ ∑ w ( e ) ≤ ∣ I < τ ∗ ∣ τ ≤ τ k , where the last inequality follows from the fact that ∣ I < τ ∗ ∣ ≤ ∣ I ∗ ∣ ≤ k . {\left|I^*_{< \tau} \right|} \le {\left|I^* \right|} \le k. ∣ I < τ ∗ ∣ ≤ ∣ I ∗ ∣ ≤ k . By assumption it follows that
τ k ≤ ϵ 4 ⋅ 2 i ∗ = ϵ 2 ⋅ 2 ( i ∗ − 1 ) ≤ ϵ 2 ⋅ f ( I ∗ ) . \tau k \le \frac{\epsilon}{4} \cdot 2^{i^*} = \frac{\epsilon}{2} \cdot 2^{(i^* - 1)} \le \frac{\epsilon}{2}\cdot f(I^*). τ k ≤ 4 ϵ ⋅ 2 i ∗ = 2 ϵ ⋅ 2 ( i ∗ − 1 ) ≤ 2 ϵ ⋅ f ( I ∗ ) . Hence, we have the following bound on w ( I < τ ∗ ) w(I^*_{< \tau}) w ( I < τ ∗ ) that
\begin{align*}
}
w(I^*_{< \tau}) &\le \frac{\epsilon}{2} \cdot f(I^*).
\end{align*}
Now, we turn our focus to I ≥ τ ∗ I^*_{\ge \tau} I ≥ τ ∗ . By Definition 8 , for e ∉ I ∪ T e \notin {I^{\cup}}_T e ∈ / I ∪ T , we have w ( e ) = f ( e ∣ I ∪ T ) w(e) = f(e | {I^{\cup}}_T) w ( e ) = f ( e ∣ I ∪ T ) . Therefore, since for any element e ∈ I ≥ τ ∗ e \in I^*_{\ge \tau} e ∈ I ≥ τ ∗ , we know that e ∉ I ∪ T e \notin {I^{\cup}}_T e ∈ / I ∪ T , we have
τ ≤ w ( e ) = f ( e ∣ I ∪ T ) ≤ f ( e ) , \tau \le w(e) = f(e | {I^{\cup}}_T) \le f(e), τ ≤ w ( e ) = f ( e ∣ I ∪ T ) ≤ f ( e ) , where the last inequality comes from the submodularity of f f f . The assumption also implies that f ( e ) ≤ f ( I ∗ ) < 2 i ∗ . f(e) \le f(I^*) < 2^{i^*}. f ( e ) ≤ f ( I ∗ ) < 2 i ∗ . Consider the instance I i ∗ \mathcal{I}_{i^*} I i ∗ in Algorithm alg:parallel . We are certain that any element e ∈ I ≥ τ ∗ e \in I^*_{\ge \tau} e ∈ I ≥ τ ∗ exists in the instance I i ∗ \mathcal{I}_{i^*} I i ∗ .
Consider a fixed arbitrary element e ∈ I ≥ τ ∗ e \in I^*_{\ge \tau} e ∈ I ≥ τ ∗ . For all ℓ ∈ [ T + 1 ] \ell \in [T + 1] ℓ ∈ [ T + 1 ] , we define E ^ ℓ \hat{E}_{\ell} E ^ ℓ as in Lemma (?) to be ( E ℓ ∪ A ℓ ) ∖ D (E_{\ell} \cup A_{\ell}) \setminus D ( E ℓ ∪ A ℓ ) ∖ D . We know that e e e is an element present at the current time, with f ( e ) ≥ τ f(e) \ge \tau f ( e ) ≥ τ . Hence, it must exist in one of E 1 E_1 E 1 or A 1 A_1 A 1 , and e ∉ D e \notin D e ∈ / D . It follows that e ∈ E ^ 1 e \in \hat{E}_1 e ∈ E ^ 1 .
We know by Lemma 6 that E T + 1 = ∅ E_{T + 1} = \emptyset E T + 1 = ∅ . Moreover, Lemma 7 implies that A T + 1 = ∅ A_{T + 1} = \emptyset A T + 1 = ∅ . Hence, e ∉ E ^ T + 1 e \notin \hat{E}_{T + 1} e ∈ / E ^ T + 1 .
let ℓ ∗ \ell^* ℓ ∗ be a level such that e ∈ E ^ ℓ ∗ e \in \hat{E}_{\ell^*} e ∈ E ^ ℓ ∗ but e ∉ E ^ ℓ ∗ + 1 e \notin \hat{E}_{\ell^* + 1} e ∈ / E ^ ℓ ∗ + 1 . By Lemma (?) , we have
\hat{E}_{\ell^* + 1} = \left\{\,e' \in \hat{E}_{\ell^*}: \textsc{Inspect}(e', (I, {I^{\cup}}, \Delta)_{\ell^*}, \tau) \ne \textsc{Fail}\,\right\}.
Therefore, we have
\textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{\ell^*}, \tau) = \textsc{Fail}.
Furthermore, since f ( e ∣ I ∪ T ) ≥ τ f(e | {I^{\cup}}_T) \ge \tau f ( e ∣ I ∪ T ) ≥ τ , we have f ( e ∣ I ∪ ℓ ∗ ) ≥ τ . f(e | {I^{\cup}}_{\ell^*}) \ge \tau. f ( e ∣ I ∪ ℓ ∗ ) ≥ τ .
We know from Lemma (?) that ( I , I ∪ , Δ ) T (I, {I^{\cup}}, \Delta)_{T} ( I , I ∪ , Δ ) T is obtained from ( I , I ∪ , Δ ) ℓ ∗ (I, {I^{\cup}}, \Delta)_{\ell^*} ( I , I ∪ , Δ ) ℓ ∗ by iteratively applying {\textsc{Adjust}} to the elements of S ℓ ∗ + 1 S_{\ell^* + 1} S ℓ ∗ + 1 , then S ℓ ∗ + 2 S_{\ell^* + 2} S ℓ ∗ + 2 , until S T S_{T} S T .
Therefore, even when ℓ ∗ ≠ T \ell^* \neq T ℓ ∗ = T by applying Lemma 14 , we know that there exists a set N ⊆ I T N \subseteq I_{T} N ⊆ I T such that N ∪ { e } N \cup \left\{\,e\,\right\} N ∪ { e } forms a circuit, and for all e ′ ∈ N e' \in N e ′ ∈ N ,
w ( e ) = f ( e ∣ I ∪ T ) < 2 Δ T ( e ′ ) = 2 w ( e ′ ) . w(e) = f(e | {I^{\cup}}_{T}) < 2\Delta_{T}(e') = 2w(e'). w ( e ) = f ( e ∣ I ∪ T ) < 2 Δ T ( e ′ ) = 2 w ( e ′ ) . For each element e ∈ I ≥ τ ∗ e \in I^*_{\ge \tau} e ∈ I ≥ τ ∗ , we denote its corresponding N N N by N ( e ) N(e) N ( e ) .
Consider a bipartite graph ( I ≥ τ ∗ , I T , E ) (I^*_{\ge \tau}, I_T, E) ( I ≥ τ ∗ , I T , E ) with an edge from e ∈ I ≥ τ ∗ e \in I^*_{\ge \tau} e ∈ I ≥ τ ∗ to r ∈ I T r \in I_T r ∈ I T if r ∈ N ( e ) r \in N(e) r ∈ N ( e ) . For each e ∈ I ≥ τ ∗ e \in I^*_{\ge \tau} e ∈ I ≥ τ ∗ , we know that e ∈ Span ( N ( e ) ) e \in \texttt{Span}(N(e)) e ∈ Span ( N ( e )) . This further implies that for all E ⊆ I ≥ τ ∗ E \subseteq I^*_{\ge \tau} E ⊆ I ≥ τ ∗ , E ⊆ Span ( N ( E ) ) E \subseteq \texttt{Span}(N(E)) E ⊆ Span ( N ( E )) . Therefore, Since E E E is independent, we can conclude that ∣ E ∣ ≤ ∣ N ( E ) ∣ |E| \le |N(E)| ∣ E ∣ ≤ ∣ N ( E ) ∣ . Thus, by Hall’s theorem, There is a perfect matching M M M of I ≥ τ ∗ I^*_{\ge \tau} I ≥ τ ∗ into I T I_T I T . Since, weight of each element in I ≥ τ ∗ I^*_{\ge \tau} I ≥ τ ∗ is less than twice the weight of its matched element in I T I_{T} I T , we have
w ( I ≥ τ ∗ ) < 2 w ( I T ) . w(I^*_{\ge \tau}) < 2 w(I_T). w ( I ≥ τ ∗ ) < 2 w ( I T ) . Therefore, we have
w ( I ∗ ∖ I ∪ T ) = w ( I ≥ τ ∗ ) + w ( I < τ ∗ ) < 2 w ( I T ) + ϵ 2 ⋅ f ( I ∗ ) . \begin{align*}
w(I^*\setminus {I^{\cup}}_T) &= w(I^*_{\ge \tau}) + w(I^*_{< \tau})
< 2 w(I_T) + \frac{\epsilon}{2} \cdot f(I^*).
\end{align*} w ( I ∗ ∖ I ∪ T ) = w ( I ≥ τ ∗ ) + w ( I < τ ∗ ) < 2 w ( I T ) + 2 ϵ ⋅ f ( I ∗ ) . Then, by Lemma 13 , we obtain
( 1 − ϵ 2 ) f ( I ∗ ) < 4 w ( I T ) . (1 - \frac{\epsilon}{2})f(I^*) < 4 w(I_T). ( 1 − 2 ϵ ) f ( I ∗ ) < 4 w ( I T ) . The proof is complete. ◻
Sample Size and Randomized Properties of the Data Structure
This section analyzes the randomized aspects of our data structure. We begin by formally defining the notion of a suitable sample size, which is a key component of our algorithm.
Definition 16. Consider given variables B B B , ( I , I ∪ , Δ ) (I, {I^{\cup}}, \Delta) ( I , I ∪ , Δ ) , and τ \tau τ . Let B ′ B' B ′ be a random permutation of B B B , and let ( I , I ∪ , Δ ) ′ (I, {I^{\cup}}, \Delta)' ( I , I ∪ , Δ ) ′ denote the output of {\textsc{Expand}}(B', (I, {I^{\cup}}, \Delta), \tau) . Define a random vector Y Y Y of length ∣ B ∣ + 1 {\left|B \right|} + 1 ∣ B ∣ + 1 as follows: for each j ∈ [ ∣ B ∣ ] j \in [{\left|B \right|}] j ∈ [ ∣ B ∣ ] , Y [ j ] = P [ B ′ [ j ] ∈ I ∪ ′ ] , Y[j] = {\mathbb{P}\left[B'[j] \in {I^{\cup}}'\right]}, Y [ j ] = P [ B ′ [ j ] ∈ I ∪ ′ ] , and set Y [ ∣ B ∣ + 1 ] = 0. Y[{\left|B \right|} + 1] = 0. Y [ ∣ B ∣ + 1 ] = 0. We define Suit ( B , ( I , I ∪ , Δ ) , τ ) \texttt{Suit}(B, (I, {I^{\cup}}, \Delta), \tau) Suit ( B , ( I , I ∪ , Δ ) , τ ) as the set of indices s , s, s , for which the following conditions hold:
Y [ j ] ≥ 1 − 3 ϵ sam 2 for all j ≤ s , Y[j] \ge 1 - \frac{3\epsilon_{\textnormal{sam}}}{2} \quad \text{for all } j \le s, Y [ j ] ≥ 1 − 2 3 ϵ sam for all j ≤ s ,
Y [ j ] ≤ 1 − ϵ sam 2 for j = s + 1. Y[j] \le 1 - \frac{\epsilon_{\textnormal{sam}}}{2} \quad \text{for } j = s + 1. Y [ j ] ≤ 1 − 2 ϵ sam for j = s + 1.
In particular, for ℓ ∈ [ T ] \ell \in [T] ℓ ∈ [ T ] , we define Suit ℓ : = Suit ( B ℓ , ( I , I ∪ , Δ ) ℓ − 1 , τ ℓ ) \texttt{Suit}_\ell := \texttt{Suit}(B_\ell, (I, {I^{\cup}}, \Delta)_{\ell - 1}, \tau_\ell) Suit ℓ := Suit ( B ℓ , ( I , I ∪ , Δ ) ℓ − 1 , τ ℓ ) .
The following lemma further establishes the significance of the above definition by demonstrating desirable probabilistic properties of selecting a sample subset with a suitable size, guaranteeing both sufficient expansion of the solution at the current level and effective filtration of the remaining elements for the next level.
Lemma 17. Consider B B B , ( I , I ∪ , Δ ) (I, {I^{\cup}}, \Delta) ( I , I ∪ , Δ ) , τ \tau τ , B ′ B' B ′ , ( I , I ∪ , Δ ) ′ (I, {I^{\cup}}, \Delta)' ( I , I ∪ , Δ ) ′ , and Y Y Y as in Definition 16 . Let S S S be an ordered sample subset of B B B of size s s s , and let ( I , I ∪ , Δ ) ′ ′ (I, {I^{\cup}}, \Delta)'' ( I , I ∪ , Δ ) ′′ denote the output of {\textsc{Expand}}(S, (I, {I^{\cup}}, \Delta), \tau) .
Assume s ∈ Suit ( B , ( I , I ∪ , Δ ) , τ ) s\in \texttt{Suit}(B, (I, {I^{\cup}}, \Delta), \tau) s ∈ Suit ( B , ( I , I ∪ , Δ ) , τ ) , then the following hold:
E [ ∣ S ∩ I ∪ ′ ′ ∣ ] ≥ ( 1 − 3 ϵ sam 2 ) s , {\mathbb{E}\left[{\left|S\cap {I^{\cup}}'' \right|}\right]} \ge (1- \frac{3\epsilon_{\textnormal{sam}}}{2})s, E [ S ∩ I ∪ ′′ ] ≥ ( 1 − 2 3 ϵ sam ) s ,
\ensuremath{\mathbb{E}\left[
{\left|\left\{\,e \in B: \textsc{Inspect}{}(e, (I, {I^{\cup}}, \Delta)'', \tau) = \textsc{Fail}\,\right\} \right|}\right]} \ge (\frac{\epsilon_{\textnormal{sam}}}{2}){\left|B \right|}.
Proof. Recall that B ′ B' B ′ is a random permutation of B B B , ( I , I ∪ , Δ ) ′ (I, {I^{\cup}}, \Delta)' ( I , I ∪ , Δ ) ′ denotes the output of {\textsc{Expand}}(B', (I, {I^{\cup}}, \Delta), \tau) , and Y Y Y is a random vector of length ∣ B ∣ + 1 {\left|B \right|} + 1 ∣ B ∣ + 1 such that for all j ∈ [ ∣ B ∣ ] j \in [{\left|B \right|}] j ∈ [ ∣ B ∣ ] ,
Y [ j ] = P [ B ′ [ j ] ∈ I ∪ ′ ] , and Y [ ∣ B ∣ + 1 ] = 0. Y[j] = {\mathbb{P}\left[B'[j] \in {I^{\cup}}'\right]}
, \quad \text{and} \quad Y[{\left|B \right|} + 1] = 0. Y [ j ] = P [ B ′ [ j ] ∈ I ∪ ′ ] , and Y [ ∣ B ∣ + 1 ] = 0. For each j ∈ [ s ] j \in [s] j ∈ [ s ] , the random variables 1 [ B ′ [ j ] ∈ I ∪ ′ ] {\mathds{1}\left[B'[j] \in {I^{\cup}}'\right]} 1 [ B ′ [ j ] ∈ I ∪ ′ ] and 1 [ S [ j ] ∈ I ∪ ′ ′ ] {\mathds{1}\left[S[j] \in {I^{\cup}}''\right]} 1 [ S [ j ] ∈ I ∪ ′′ ] have the same distribution. Therefore,
E [ ∣ S ∩ I ∪ ′ ′ ∣ ] = E [ ∑ j ∈ [ s ] 1 [ S [ j ] ∈ I ∪ ′ ′ ] ] = ∑ j ∈ [ s ] E [ 1 [ B ′ [ j ] ∈ I ∪ ′ ] ] = ∑ j ∈ [ s ] P [ B ′ [ j ] ∈ I ∪ ′ ] = ∑ j ∈ [ s ] Y [ j ] \begin{align*}
{\mathbb{E}\left[{\left|S\cap {I^{\cup}}'' \right|}\right]}
&= {\mathbb{E}\left[\sum_{j \in [s]} {\mathds{1}\left[S[j] \in {I^{\cup}}''\right]}\right]}
= \sum_{j \in [s]} {\mathbb{E}\left[{\mathds{1}\left[B'[j] \in {I^{\cup}}'\right]}\right]}\\
&= \sum_{j \in [s]} {\mathbb{P}\left[B'[j] \in {I^{\cup}}'\right]}
= \sum_{j \in [s]} Y[j]
\end{align*} E [ S ∩ I ∪ ′′ ] = E j ∈ [ s ] ∑ 1 [ S [ j ] ∈ I ∪ ′′ ] = j ∈ [ s ] ∑ E [ 1 [ B ′ [ j ] ∈ I ∪ ′ ] ] = j ∈ [ s ] ∑ P [ B ′ [ j ] ∈ I ∪ ′ ] = j ∈ [ s ] ∑ Y [ j ] Given the assumption that s ∈ Suit ( B , ( I , I ∪ , Δ ) , τ ) s \in \texttt{Suit}(B, (I, {I^{\cup}}, \Delta), \tau) s ∈ Suit ( B , ( I , I ∪ , Δ ) , τ ) , condition def:suitable-cond1 in Definition 16 gives Y [ j ] ≥ 1 − 3 ϵ sam 2 Y[j] \geq 1 - \frac{3\epsilon_{\textnormal{sam}}}{2} Y [ j ] ≥ 1 − 2 3 ϵ sam for all j ≤ s j \leq s j ≤ s . Hence,
E [ ∣ S ∩ I ∪ ′ ′ ∣ ] ≥ ( 1 − 3 ϵ sam 2 ) s , {\mathbb{E}\left[{\left|S\cap {I^{\cup}}'' \right|}\right]} \ge (1- \frac{3\epsilon_{\textnormal{sam}}}{2})s, E [ S ∩ I ∪ ′′ ] ≥ ( 1 − 2 3 ϵ sam ) s , as desired.
Next, consider B ∖ S B\setminus S B ∖ S . If nonempty, let e ‾ \overline{e} e be an element selected uniformly at random from B ∖ S B\setminus S B ∖ S , and define S ‾ \overline{S} S as S S S followed by e ‾ \overline{e} e . Let ( I , I ∪ , Δ ) ′ ′ ′ (I, {I^{\cup}}, \Delta)''' ( I , I ∪ , Δ ) ′′′ be {\textsc{Expand}}(\overline{S}, (I, {I^{\cup}}, \Delta), \tau) . By construction,
{\textsc{Expand}}(\overline{S}, (I, {I^{\cup}}, \Delta), \tau) = {\textsc{Adjust}}(\overline{e}, (I, {I^{\cup}}, \Delta)'', \tau),
and e ‾ ∈ I ∪ ′ ′ ′ \overline{e} \in {I^{\cup}}''' e ∈ I ∪ ′′′ if and only if \textsc{Inspect}(\overline{e}, (I, {I^{\cup}}, \Delta)'', \tau) \neq \textsc{Fail} . Therefore,
\ensuremath{\mathbb{E}\left[\ensuremath{\mathds{1}\left[\textsc{Inspect}(\overline{e}, (I, {I^{\cup}}, \Delta)'', \tau) \neq \textsc{Fail}\right]}\right]} = \ensuremath{\mathbb{E}\left[\ensuremath{\mathds{1}\left[B'[s+ 1] \in {I^{\cup}}'\right]}\right]} = Y[s+ 1] \leq 1 - \frac{\epsilon_{\textnormal{sam}}}{2},
where the first equality comes from the fact that the random variables 1 [ B ′ [ s + 1 ] ∈ I ∪ ′ ] {\mathds{1}\left[B'[s+ 1] \in {I^{\cup}}'\right]} 1 [ B ′ [ s + 1 ] ∈ I ∪ ′ ] and 1 [ e ‾ ∈ I ∪ ′ ′ ′ ] {\mathds{1}\left[\overline{e} \in {I^{\cup}}'''\right]} 1 [ e ∈ I ∪ ′′′ ] have the same distribution, and the last inequality uses condition (2) in Definition 16 . It follows that
\ensuremath{\mathbb{E}\left[\ensuremath{\mathds{1}\left[\textsc{Inspect}(\overline{e}, (I, {I^{\cup}}, \Delta)'', \tau) = \textsc{Fail}\right]}\right]} \geq \frac{\epsilon_{\textnormal{sam}}}{2},
and thus,
\ensuremath{\mathbb{E}\left[{\left|\{ e \in B\setminus S: \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)'', \tau) = \textsc{Fail}\} \right|}\right]} \geq \frac{\epsilon_{\textnormal{sam}}}{2} {\left|B\setminus S \right|}.
Now, it remains to show that
\ensuremath{\mathbb{E}\left[{\left|\left\{\,e \in S: \textsc{Inspect}{}(e, (I, {I^{\cup}}, \Delta)'', \tau) = \textsc{Fail}\,\right\} \right|}\right]} \ge (\frac{\epsilon_{\textnormal{sam}}}{2}){\left|S \right|}.
It is in fact true that \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)'', \tau) = \textsc{Fail} for any e ∈ S e \in S e ∈ S . Yet, it suffices to show that this holds for any e ∈ S ∩ I ∪ ′ ′ e \in S\cap {I^{\cup}}'' e ∈ S ∩ I ∪ ′′ , which in turn implies
{\left|\left\{\,e \in S: \textsc{Inspect}{}(e, (I, {I^{\cup}}, \Delta)'', \tau) = \textsc{Fail}\,\right\} \right|} \ge
{\left|S\cap {I^{\cup}}'' \right|}.
This is because we have already established that E [ ∣ S ∩ I ∪ ′ ′ ∣ ] ≥ ( 1 − 3 ϵ sam 2 ) s , {\mathbb{E}\left[{\left|S\cap {I^{\cup}}'' \right|}\right]} \ge (1- \tfrac{3\epsilon_{\textnormal{sam}}}{2})s, E [ S ∩ I ∪ ′′ ] ≥ ( 1 − 2 3 ϵ sam ) s , and 1 − 3 ϵ sam 2 ≥ ϵ sam 2 1- \tfrac{3\epsilon_{\textnormal{sam}}}{2} \ge \frac{\epsilon_{\textnormal{sam}}}{2} 1 − 2 3 ϵ sam ≥ 2 ϵ sam under the assumption ϵ sam ≤ 1 2 . \epsilon_{\textnormal{sam}}\le \tfrac{1}{2}. ϵ sam ≤ 2 1 .
Finally, for all e ∈ S ∩ I ∪ ′ ′ e \in S\cap {I^{\cup}}'' e ∈ S ∩ I ∪ ′′ , we argue that \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)'', \tau) = \textsc{Fail} since \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)'', \tau) = \textsc{Fail} if f ( e ∣ I ∪ ′ ′ ) < τ f(e | {I^{\cup}}'') < \tau f ( e ∣ I ∪ ′′ ) < τ , which is the case for elements e ∈ S ∩ I ∪ ′ ′ e \in S\cap {I^{\cup}}'' e ∈ S ∩ I ∪ ′′ because f ( e ∣ I ∪ ′ ′ ) = 0 f(e | {I^{\cup}}'') = 0 f ( e ∣ I ∪ ′′ ) = 0 , for e ∈ I ∪ ′ ′ e \in {I^{\cup}}'' e ∈ I ∪ ′′ .
The proof is complete. ◻
The next lemma demonstrates that the procedure {\textsc{EstimateSampleSize}} returns a sample size from the set of suitable sample sizes defined above efficiently and with high probability.
Lemma 18. Suppose the procedure {\textsc{EstimateSampleSize}} is called with input parameters B B B , ( I , I ∪ , Δ ) (I, {I^{\cup}}, \Delta) ( I , I ∪ , Δ ) , and τ \tau τ .
With probability at least 1 − ϵ pr k 10 1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}} 1 − k 10 ϵ pr , the following holds: {\textsc{EstimateSampleSize}}(B, (I, {I^{\cup}}, \Delta), \tau) \in \texttt{Suit}(B, (I, {I^{\cup}}, \Delta), \tau).
Proof. Hoeffding’s inequality implies that for any j ∈ [ ∣ B ∣ ] j \in [|B|] j ∈ [ ∣ B ∣ ] ,
P [ ∣ ∑ i = 1 t X [ i , j ] t − E [ ∑ i = 1 t X [ i , j ] t ] ∣ ≥ ϵ sam 2 ] ≤ 2 e − t ϵ sam 2 4 . \begin{align*}
{\mathbb{P}\left[ \left| \frac{\sum_{i=1}^t X[i, j]}{t} - {\mathbb{E}\left[
\frac{\sum_{i=1}^t X[i, j]}{t}
\right]} \right| \geq \frac{\epsilon_{\textnormal{sam}}}{2} \right]} \leq 2e^{-\frac{t \epsilon_{\textnormal{sam}}^2}{4}}.
\end{align*} P [ t ∑ i = 1 t X [ i , j ] − E [ t ∑ i = 1 t X [ i , j ] ] ≥ 2 ϵ sam ] ≤ 2 e − 4 t ϵ sam 2 . Since we have:
X [ i , j ] ≔ 1 [ B ′ [ j ] ∈ I ∪ ′ ] , and Y [ j ] ≔ P [ B ′ [ j ] ∈ I ∪ ′ ] , X[i, j] \coloneqq {\mathds{1}\left[B'[j] \in {I^{\cup}}'\right]}, \quad \text{and} \quad
Y[j] \coloneqq {\mathbb{P}\left[B'[j] \in {I^{\cup}}'\right]}, X [ i , j ] : = 1 [ B ′ [ j ] ∈ I ∪ ′ ] , and Y [ j ] : = P [ B ′ [ j ] ∈ I ∪ ′ ] , it follows that
E [ ∑ i = 1 t X [ i , j ] t ] = Y [ j ] . {\mathbb{E}\left[\frac{\sum_{i=1}^t X[i, j]}{t}\right]} = Y[j]. E [ t ∑ i = 1 t X [ i , j ] ] = Y [ j ] . Thus, we have:
P [ ∣ ∑ i = 1 t X [ i , j ] t − Y [ j ] ∣ ≥ ϵ sam 2 ] ≤ 2 e − t ϵ sam 2 4 . \begin{align*}
{\mathbb{P}\left[\left| \frac{\sum_{i=1}^t X[i, j]}{t} - Y[j] \right| \geq \frac{\epsilon_{\textnormal{sam}}}{2}\right]} \leq 2e^{-\frac{t \epsilon_{\textnormal{sam}}^2}{4}}.
\end{align*} P [ t ∑ i = 1 t X [ i , j ] − Y [ j ] ≥ 2 ϵ sam ] ≤ 2 e − 4 t ϵ sam 2 . By substituting t = 4 ϵ sam 2 ln ( 2 n k 10 ϵ pr ) t = {\frac{4}{\epsilon_{\textnormal{sam}}^2}\ln(\frac{2nk^{10}}{\epsilon_{\textnormal{pr}}})} t = ϵ sam 2 4 ln ( ϵ pr 2 n k 10 ) , we get:
P [ ∣ ∑ i = 1 t X [ i , j ] t − Y [ j ] ∣ ≥ ϵ sam 2 ] ≤ 2 e − ln ( 2 n k 10 ϵ pr ) = ϵ pr n k 10 . \begin{align*}
{\mathbb{P}\left[ \left| \frac{\sum_{i=1}^t X[i, j]}{t} - Y[j] \right| \geq \frac{\epsilon_{\textnormal{sam}}}{2} \right]}
\leq 2e^{-\ln\left( \frac{2nk^{10}}{\epsilon_{\textnormal{pr}}} \right)} = \frac{\epsilon_{\textnormal{pr}}}{nk^{10}}.
\end{align*} P [ t ∑ i = 1 t X [ i , j ] − Y [ j ] ≥ 2 ϵ sam ] ≤ 2 e − l n ( ϵ pr 2 n k 10 ) = n k 10 ϵ pr . By applying the union bound over all j ∈ [ ∣ B ∣ ] j \in [|B|] j ∈ [ ∣ B ∣ ] , we have
P [ ∃ j ∈ [ ∣ B ∣ ] : ∣ ∑ i = 1 t X [ i , j ] t − Y [ j ] ∣ ≥ ϵ sam 2 ] ≤ ∣ B ∣ ⋅ ϵ pr n k 10 ≤ ϵ pr k 10 , \begin{align*}
{\mathbb{P}\left[ \exists j \in [|B|] : \left| \frac{\sum_{i=1}^t X[i, j]}{t} - Y[j] \right| \geq \frac{\epsilon_{\textnormal{sam}}}{2} \right]}
&\leq |B| \cdot \frac{\epsilon_{\textnormal{pr}}}{nk^{10}}
\leq \frac{\epsilon_{\textnormal{pr}}}{k^{10}},
\end{align*} P [ ∃ j ∈ [ ∣ B ∣ ] : t ∑ i = 1 t X [ i , j ] − Y [ j ] ≥ 2 ϵ sam ] ≤ ∣ B ∣ ⋅ n k 10 ϵ pr ≤ k 10 ϵ pr , where the last inequality uses ∣ B ∣ ≤ n |B| \leq n ∣ B ∣ ≤ n . Therefore,
P [ ∀ j ∈ [ ∣ B ∣ ] : ∣ ∑ i = 1 t X [ i , j ] t − Y [ j ] ∣ < ϵ sam 2 ] ≥ 1 − ϵ pr k 10 . \begin{align*}
{\mathbb{P}\left[ \forall j \in [|B|] : \left| \frac{\sum_{i=1}^t X[i, j]}{t} - Y[j] \right| < \frac{\epsilon_{\textnormal{sam}}}{2} \right]}
&\geq 1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}}.
\end{align*} P [ ∀ j ∈ [ ∣ B ∣ ] : t ∑ i = 1 t X [ i , j ] − Y [ j ] < 2 ϵ sam ] ≥ 1 − k 10 ϵ pr . Also note that by definition, ∣ ∑ i = 1 t X [ i , ∣ B ∣ + 1 ] t − Y [ ∣ B ∣ + 1 ] ∣ = 0 \left| \frac{\sum_{i=1}^t X[i, |B| + 1]}{t} - Y[|B| + 1] \right| = 0 t ∑ i = 1 t X [ i , ∣ B ∣ + 1 ] − Y [ ∣ B ∣ + 1 ] = 0 . Hence, with probability at least 1 − ϵ pr k 10 1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}} 1 − k 10 ϵ pr , for all j ∈ [ ∣ B ∣ + 1 ] j \in [|B| + 1] j ∈ [ ∣ B ∣ + 1 ] , we have
∑ i = 1 t X [ i , j ] t − ϵ sam 2 < Y [ j ] < ∑ i = 1 t X [ i , j ] t + ϵ sam 2 . \frac{\sum_{i=1}^t X[i, j]}{t} - \frac{\epsilon_{\textnormal{sam}}}{2} < Y[j] < \frac{\sum_{i=1}^t X[i, j]}{t} + \frac{\epsilon_{\textnormal{sam}}}{2}. t ∑ i = 1 t X [ i , j ] − 2 ϵ sam < Y [ j ] < t ∑ i = 1 t X [ i , j ] + 2 ϵ sam . We know that min { j : 1 ≤ j ≤ ∣ B ∣ + 1 , ∑ i = 1 t X [ i , j ] t < 1 − ϵ sam } \min{\left\{\,j : 1 \le j \le {\left|B \right|} + 1, \frac{\sum_{i=1}^t X[i,j]}{t}< 1 - \epsilon_{\textnormal{sam}}\,\right\}} min { j : 1 ≤ j ≤ ∣ B ∣ + 1 , t ∑ i = 1 t X [ i , j ] < 1 − ϵ sam } is selected as s ′ s' s ′ . Note that since ∑ i = 1 t X [ i , ∣ B ∣ + 1 ] ] t = 0 \frac{\sum_{i=1}^t X[i,|B| + 1]]}{t} = 0 t ∑ i = 1 t X [ i , ∣ B ∣ + 1 ]] = 0 , such s ′ s' s ′ exists. The choice of s ′ s' s ′ implies that
∑ i = 1 t X [ i , j ] t ≥ 1 − ϵ sam for all j < s ′ , ∑ i = 1 t X [ i , j ] t < 1 − ϵ sam for j = s ′ . \begin{align*}
\frac{\sum_{i=1}^t X[i,j]}{t} &\geq 1 - \epsilon_{\textnormal{sam}}&\text{for all }
j < s',\\
\frac{\sum_{i=1}^t X[i,j]}{t} &< 1 - \epsilon_{\textnormal{sam}}&\text{for } j = s'.
\end{align*} t ∑ i = 1 t X [ i , j ] t ∑ i = 1 t X [ i , j ] ≥ 1 − ϵ sam < 1 − ϵ sam for all j < s ′ , for j = s ′ . Hence, the following holds:
Y [ j ] > 1 − 3 ϵ sam 2 for all j < s ′ − 1 , Y [ j ] < 1 − ϵ sam 2 for j = ( s ′ − 1 ) + 1. \begin{align*}
Y[j] &> 1 - \frac{3\epsilon_{\textnormal{sam}}}{2} &\text{for all } j < s' - 1, \\
Y[j] &< 1 - \frac{\epsilon_{\textnormal{sam}}}{2} &\text{for } j = (s' - 1) + 1.
\end{align*} Y [ j ] Y [ j ] > 1 − 2 3 ϵ sam < 1 − 2 ϵ sam for all j < s ′ − 1 , for j = ( s ′ − 1 ) + 1. This implies that
{\textsc{EstimateSampleSize}}(B, (I, {I^{\cup}}, \Delta), \tau) = s' - 1 \in \texttt{Suit}(B, (I, {I^{\cup}}, \Delta), \tau).
◻
Next, before proceeding with the randomized invariants of our dynamic algorithm, we first present a fact used in their analysis.
Fact 19. Let C C C be collection of random variables X X X , and events Y Y Y , and let Z Z Z be a random variable. If Z Z Z is a function of X X X , given Y Y Y , that is, it can be deterministically determined given X X X and Y Y Y , then: E [ A ∣ X , Y , Z ] = E [ A ∣ X , Y ] or P [ A ∣ X , Y , Z ] = P [ A ∣ X , Y ] . {\mathbb{E}\left[A \mid X, Y, Z\right]} = {\mathbb{E}\left[A \mid X, Y\right]} \quad \text{or} \quad {\mathbb{P}\left[A \mid X, Y, Z\right]} = \mathbb{P}[A \mid X, Y]. E [ A ∣ X , Y , Z ] = E [ A ∣ X , Y ] or P [ A ∣ X , Y , Z ] = P [ A ∣ X , Y ] .
The same holds if Z Z Z is an event that is implied by X X X and Y Y Y .
However, note that if X X X and Y Y Y are contradictory to Z Z Z , P [ A ∣ X , Y , Z ] {\mathbb{P}\left[A \mid X, Y, Z\right]} P [ A ∣ X , Y , Z ] and E [ A ∣ X , Y , Z ] {\mathbb{E}\left[A \mid X, Y, Z\right]} E [ A ∣ X , Y , Z ] are undefined. Note that when we get E [ A ∣ X , Y ] = E [ E [ A ∣ X , Y , Z ] ] {\mathbb{E}\left[A \mid X, Y\right]} = {\mathbb{E}\left[{\mathbb{E}\left[A \mid X, Y, Z\right]}\right]} E [ A ∣ X , Y ] = E [ E [ A ∣ X , Y , Z ] ] by the law of iterated expectations, E [ A ∣ X , Y , Z ] {\mathbb{E}\left[A \mid X, Y, Z\right]} E [ A ∣ X , Y , Z ] is itself a random variable, a function only defined over values of ( x , z ) (x, z) ( x , z ) satisfying P [ X = x , Y , Z = z ] > 0 {\mathbb{P}\left[\ X = x, Y, Z = z\right]} > 0 P [ X = x , Y , Z = z ] > 0 .
We then follow with defining the notion of History H < ℓ H_{< \ell} H < ℓ , which serves as the conditioning context for our randomized invariant concerning the sample size at each layer.
Definition 20. Let L ℓ L_{\ell} L ℓ denote ( ( I , I ∪ , Δ ) ℓ , E ℓ + 1 , A ℓ + 1 ) ((I, {I^{\cup}}, \Delta)_{\ell}, E_{\ell + 1}, A_{\ell + 1}) (( I , I ∪ , Δ ) ℓ , E ℓ + 1 , A ℓ + 1 ) for ℓ ∈ [ 0 , T ] \ell \in [0, T] ℓ ∈ [ 0 , T ] . We define History H < ℓ H_{< \ell} H < ℓ as H < ℓ : = { D , L 0 , … , L ℓ − 1 } . \begin{aligned}
H_{< \ell} &:= \left\{\,D, L_{0}, \dots, L_{\ell - 1}\,\right\}.
\end{aligned} H < ℓ := { D , L 0 , … , L ℓ − 1 } . We use H < ℓ \mathbf{H}_{< \ell} H < ℓ to denote the random variables corresponding to H < ℓ H_{< \ell} H < ℓ .
Note that conditioning on the values of H < ℓ \mathbf{H}_{< \ell} H < ℓ inherently implies T > ℓ {\mathbf{T}}> \ell T > ℓ .
The following lemma establishes that, conditioned on its preceding history, the sample size at each layer is suitable with high probability.
Lemma 21. For all ℓ ∈ [ T ] \ell \in [T] ℓ ∈ [ T ] , the following holds: P [ s ℓ ∈ Suit ℓ ∣ H < ℓ ] ≥ 1 − ϵ pr k 10 . \begin{aligned}
{\mathbb{P}\left[{\mathbf{s}}_\ell \in \texttt{Suit}_\ell \mid \mathbf{H}_{< \ell}\right]} \ge 1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}}.
\end{aligned} P [ s ℓ ∈ Suit ℓ ∣ H < ℓ ] ≥ 1 − k 10 ϵ pr .
Proof. We prove this by showing that the statement holds before any update is applied and that, assuming that it holds prior to an update, we can conclude that it also holds afterward.
At the beginning, before any update, the claim holds trivially, as T = 0 T = 0 T = 0 . Since the set [ T ] [T] [ T ] is empty, the lemma statement holds vacuously for the initial state.
For any variable X X X , we use the notations X − X^{-} X − and X + X^{+} X + to denote X X X before and after the execution of an update, respectively. Hence, we aim to proof P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + ] ≥ 1 − ϵ pr k 10 {\mathbb{P}\left[{\mathbf{s}}_\ell^{+} \in \texttt{Suit}_\ell^{+} \mid \mathbf{H}_{< \ell}^{+}\right]} \ge 1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}} P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + ] ≥ 1 − k 10 ϵ pr given the assumption that P [ s ℓ − ∈ Suit ℓ − ∣ H < ℓ − ] ≥ 1 − ϵ pr k 10 . {\mathbb{P}\left[{\mathbf{s}}_\ell^{-} \in \texttt{Suit}_\ell^{-} \mid \mathbf{H}_{< \ell}^{-}\right]} \ge 1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}}. P [ s ℓ − ∈ Suit ℓ − ∣ H < ℓ − ] ≥ 1 − k 10 ϵ pr .
Let C ℓ C_\ell C ℓ be a random variable that takes the value 1 1 1 if {\textsc{LayerConstruct}}{}(\ell) was called during this update (whether directly or through {\textsc{LayerConstruct}}{}(\ell - 1) ).
By the law of iterated expectation, we have
P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + ] = E [ P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ ] ] . \begin{align*}
{\mathbb{P}\left[{\mathbf{s}}_\ell^{+} \in \texttt{Suit}_\ell^{+} \mid \mathbf{H}_{< \ell}^{+}\right]} =
{\mathbb{E}\left[{\mathbb{P}\left[{\mathbf{s}}_\ell^{+} \in \texttt{Suit}_\ell^{+} \mid \mathbf{H}_{< \ell}^{+}, C_\ell\right]}\right]}.
\end{align*} P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + ] = E [ P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ ] ] . Therefore, proving the following inequalities completes the proof.
P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ = 0 ] ≥ 1 − ϵ pr k 10 , \begin{align}
{\mathbb{P}\left[{\mathbf{s}}_\ell^{+} \in \texttt{Suit}_\ell^{+} \mid \mathbf{H}_{< \ell}^{+}, C_\ell=0\right]} \ge 1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}}, \tag*{(10)}
\end{align} P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ = 0 ] ≥ 1 − k 10 ϵ pr , (10) and
P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ = 1 ] ≥ 1 − ϵ pr k 10 . \begin{align}
{\mathbb{P}\left[{\mathbf{s}}_\ell^{+} \in \texttt{Suit}_\ell^{+} \mid \mathbf{H}_{< \ell}^{+}, C_\ell=1\right]} \ge 1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}}. \tag*{(11)}
\end{align} P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ = 1 ] ≥ 1 − k 10 ϵ pr . (11) Equation (11) holds by Lemma 18 . We also know that if T − < ℓ {\mathbf{T}}^- < \ell T − < ℓ but T + ≥ ℓ {\mathbf{T}}^+ \ge \ell T + ≥ ℓ , then {\textsc{LayerConstruct}}{}(\ell) has been called and therefore P [ C ℓ = 1 ] = 1 {\mathbb{P}\left[C_\ell=1\right]} = 1 P [ C ℓ = 1 ] = 1 , which means Equation (11) is sufficient to prove the claim for those levels. Thus we only need to focus on proving Equation (10) when T − ≥ ℓ {\mathbf{T}}^- \ge \ell T − ≥ ℓ .
We know that conditioning on H < ℓ + , C ℓ = 0 \mathbf{H}_{< \ell}^{+}, C_\ell=0 H < ℓ + , C ℓ = 0 implies that T − ≥ ℓ {\mathbf{T}}^- \ge \ell T − ≥ ℓ . Thus, we can also condition on H < ℓ − \mathbf{H}_{< \ell}^{-} H < ℓ − . By the law of iterated expectation, we have
P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ = 0 ] = E [ P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ = 0 , H < ℓ − ] ] \begin{align*}
{\mathbb{P}\left[{\mathbf{s}}_\ell^{+} \in \texttt{Suit}_\ell^{+} \mid \mathbf{H}_{< \ell}^{+}, C_\ell=0\right]}
=
{\mathbb{E}\left[{\mathbb{P}\left[{\mathbf{s}}_\ell^{+} \in \texttt{Suit}_\ell^{+} \mid \mathbf{H}_{< \ell}^{+}, C_\ell=0, \mathbf{H}_{< \ell}^{-}\right]}\right]}
\end{align*} P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ = 0 ] = E [ P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ = 0 , H < ℓ − ] ] It therefore suffices to show that
P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ = 0 , H < ℓ − ] ≥ 1 − ϵ pr k 10 . \begin{align*}
{\mathbb{P}\left[{\mathbf{s}}_\ell^{+} \in \texttt{Suit}_\ell^{+} \mid \mathbf{H}_{< \ell}^{+}, C_\ell=0, \mathbf{H}_{< \ell}^-\right]} \ge 1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}}.
\end{align*} P [ s ℓ + ∈ Suit ℓ + ∣ H < ℓ + , C ℓ = 0 , H < ℓ − ] ≥ 1 − k 10 ϵ pr . Now we note that s ℓ {\mathbf{s}}_\ell s ℓ and Suit ℓ \texttt{Suit}_\ell Suit ℓ would not change during an update unless the update triggers the {\textsc{LayerConstruct}}(\ell) . Hence, given the condition C ℓ = 0 C_\ell=0 C ℓ = 0 , we can replace s ℓ + ∈ Suit ℓ + {\mathbf{s}}_\ell^{+} \in \texttt{Suit}_\ell^{+} s ℓ + ∈ Suit ℓ + with s ℓ − ∈ Suit ℓ − {\mathbf{s}}_\ell^{-} \in \texttt{Suit}_\ell^{-} s ℓ − ∈ Suit ℓ − . This makes it sufficient to show that
P [ s ℓ − ∈ Suit ℓ − ∣ H < ℓ + , C ℓ = 0 , H < ℓ − ] ≥ 1 − ϵ pr k 10 . \begin{align}
{\mathbb{P}\left[{\mathbf{s}}_\ell^{-} \in \texttt{Suit}_\ell^{-} \mid \mathbf{H}_{< \ell}^{+}, C_\ell=0, \mathbf{H}_{< \ell}^-\right]} \ge 1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}}. \tag*{(12)}
\end{align} P [ s ℓ − ∈ Suit ℓ − ∣ H < ℓ + , C ℓ = 0 , H < ℓ − ] ≥ 1 − k 10 ϵ pr . (12) Then we highlight that H < ℓ + \mathbf{H}_{< \ell}^{+} H < ℓ + is a function of H < ℓ − \mathbf{H}_{< \ell}^{-} H < ℓ − , given C ℓ = 0 C_\ell=0 C ℓ = 0 , and by Fact 19 we have
P [ s ℓ − ∈ Suit ℓ − ∣ H < ℓ + , C ℓ = 0 , H < ℓ − ] = P [ s ℓ − ∈ Suit ℓ − ∣ C ℓ = 0 , H < ℓ − ] . \begin{align}
{\mathbb{P}\left[{\mathbf{s}}_\ell^{-} \in \texttt{Suit}_\ell^{-} \mid \mathbf{H}_{< \ell}^{+}, C_\ell=0, \mathbf{H}_{< \ell}^-\right]} = {\mathbb{P}\left[{\mathbf{s}}_\ell^{-} \in \texttt{Suit}_\ell^{-} \mid C_\ell=0, \mathbf{H}_{< \ell}^-\right]}. \tag*{(13)}
\end{align} P [ s ℓ − ∈ Suit ℓ − ∣ H < ℓ + , C ℓ = 0 , H < ℓ − ] = P [ s ℓ − ∈ Suit ℓ − ∣ C ℓ = 0 , H < ℓ − ] . (13) Lastly, we argue that C ℓ C_\ell C ℓ is a function of H < ℓ − \mathbf{H}_{< \ell}^- H < ℓ − . In other words, H < ℓ − = H < ℓ − \mathbf{H}_{< \ell}^- = H_{< \ell}^- H < ℓ − = H < ℓ − either implies C ℓ = 0 C_\ell=0 C ℓ = 0 or is in contradiction with it, and P [ s ℓ − ∈ Suit ℓ − ∣ C ℓ = 0 , H < ℓ − ] {\mathbb{P}\left[{\mathbf{s}}_\ell^{-} \in \texttt{Suit}_\ell^{-} \mid C_\ell=0, \mathbf{H}_{< \ell}^-\right]} P [ s ℓ − ∈ Suit ℓ − ∣ C ℓ = 0 , H < ℓ − ] is only defined for the former. Therefore, we also have
P [ s ℓ − ∈ Suit ℓ − ∣ C ℓ = 0 , H < ℓ − ] = P [ s ℓ − ∈ Suit ℓ − ∣ H < ℓ − ] . \begin{align}
{\mathbb{P}\left[{\mathbf{s}}_\ell^{-} \in \texttt{Suit}_\ell^{-} \mid C_\ell=0, \mathbf{H}_{< \ell}^-\right]} =
{\mathbb{P}\left[{\mathbf{s}}_\ell^{-} \in \texttt{Suit}_\ell^{-} \mid \mathbf{H}_{< \ell}^-\right]} . \tag*{(14)}
\end{align} P [ s ℓ − ∈ Suit ℓ − ∣ C ℓ = 0 , H < ℓ − ] = P [ s ℓ − ∈ Suit ℓ − ∣ H < ℓ − ] . (14) Equations (14) and (13) and our assumption prove the inequality (12) , and thus complete the proof. ◻
We now extend the history notion to define H < ℓ s H_{< \ell}^{\text{s}} H < ℓ s , incorporating the estimated sample size at layer ℓ \ell ℓ along with the history of preceding layers, used to condition the final randomized invariant of our data structure.
Definition 22. Recall that L ℓ L_{\ell} L ℓ denotes ( ( I , I ∪ , Δ ) ℓ , E ℓ + 1 , A ℓ + 1 ) ((I, {I^{\cup}}, \Delta)_{\ell}, E_{\ell + 1}, A_{\ell + 1}) (( I , I ∪ , Δ ) ℓ , E ℓ + 1 , A ℓ + 1 ) for ℓ ∈ [ 0 , T ] \ell \in [0, T] ℓ ∈ [ 0 , T ] . Post-estimate history H < ℓ s H_{< \ell}^{\text{s}} H < ℓ s as H < ℓ s : = { H < ℓ , s } = { D , L 0 , … , L ℓ − 1 , s ℓ } . \begin{aligned}
H_{< \ell}^{\text{s}} &:= \left\{\,H_{< \ell}, s\,\right\} = \left\{\,D, L_{0}, \dots, L_{\ell - 1}, s_{\ell}\,\right\}.
\end{aligned} H < ℓ s := { H < ℓ , s } = { D , L 0 , … , L ℓ − 1 , s ℓ } . We let H < ℓ s \mathbf{H}_{< \ell}^{\text{s}} H < ℓ s denote the random variables corresponding to H < ℓ s H_{< \ell}^{\text{s}} H < ℓ s .
Note that conditioning on the values of H < ℓ s \mathbf{H}_{< \ell}^{\text{s}} H < ℓ s inherently implies T > ℓ {\mathbf{T}}> \ell T > ℓ .
With H < ℓ s \mathbf{H}_{< \ell}^{\text{s}} H < ℓ s defined, we now establish the uniformity of the sampled subset of each layer, conditioned on the post-estimate history of that layer. The proof of this lemma is similar to the proof of Lemma 21 .
Effect of deletions on Approximation
Since the algorithm returns I T ∖ D I_T \setminus D I T ∖ D (more precisely, the best I T ∖ D I_T \setminus D I T ∖ D among its instances), it suffices to bound f ( I ∗ ) f(I^*) f ( I ∗ ) by f ( I T ∖ D ) f(I_T \setminus D) f ( I T ∖ D ) . Having already established a connection between f ( I ∗ ) f(I^*) f ( I ∗ ) and w ( I T ) w(I_T) w ( I T ) , this section analyzes the relationship between w ( I T ) w(I_T) w ( I T ) and f ( I T ∖ D ) f(I_T \setminus D) f ( I T ∖ D ) and thereby finishes the approximation analysis. The proofs of some of the following lemmas rely on the randomized components of our data structure to capture the impact of removing D D D from the final output.
The following Lemma bounds the weight of elements added to I ∪ {I^{\cup}} I ∪ at layer ℓ \ell ℓ .
Lemma 24. For any ℓ ∈ [ T ] \ell \in [T] ℓ ∈ [ T ] , the following holds: E [ w ( I ∪ ℓ \ I ∪ ℓ − 1 ) ∣ H < ℓ s = H < ℓ s ] ≥ ( 1 − 3 ϵ sam 2 ) τ ℓ s ℓ 1 [ s ℓ ∈ Suit ℓ ] . \begin{aligned}
{\mathbb{E}\left[w({I^{\cup}}_\ell \backslash {I^{\cup}}_{\ell-1}) \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}} \right]}\ge
\Bigl(1- \frac{3\epsilon_{\textnormal{sam}}}{2}\Bigr)
\tau_\ell s_\ell{\mathds{1}\left[s_\ell \in \texttt{Suit}_\ell\right]}.
\end{aligned} E [ w ( I ∪ ℓ \ I ∪ ℓ − 1 ) ∣ H < ℓ s = H < ℓ s ] ≥ ( 1 − 2 3 ϵ sam ) τ ℓ s ℓ 1 [ s ℓ ∈ Suit ℓ ] .
Proof. We consider a fixed ℓ ∈ [ T ] \ell \in [T] ℓ ∈ [ T ] and a fixed condition H < ℓ s = H < ℓ s \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}} H < ℓ s = H < ℓ s .
Since the weight w ( I ∪ ℓ \ I ∪ ℓ − 1 ) w({I^{\cup}}_\ell \backslash {I^{\cup}}_{\ell-1}) w ( I ∪ ℓ \ I ∪ ℓ − 1 ) is non-negative, by the law of total expectation we have
E [ w ( I ∪ ℓ \ I ∪ ℓ − 1 ) ∣ H < ℓ s = H < ℓ s ] ≥ E [ w ( I ∪ ℓ \ I ∪ ℓ − 1 ) ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] 1 [ s ℓ ∈ Suit ℓ ] . \begin{align*}
{\mathbb{E}\left[w({I^{\cup}}_\ell \backslash {I^{\cup}}_{\ell-1}) \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}} \right]} &\ge {\mathbb{E}\left[w({I^{\cup}}_\ell \backslash {I^{\cup}}_{\ell-1}) \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}, s_\ell \in \texttt{Suit}_\ell\right]}{\mathds{1}\left[s_\ell \in \texttt{Suit}_\ell\right]}.
\end{align*} E [ w ( I ∪ ℓ \ I ∪ ℓ − 1 ) ∣ H < ℓ s = H < ℓ s ] ≥ E [ w ( I ∪ ℓ \ I ∪ ℓ − 1 ) ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] 1 [ s ℓ ∈ Suit ℓ ] . Recall that by Lemma (?) , we have
(I, {I^{\cup}}, \Delta)_{\ell} = {\textsc{Expand}}(S_{\ell}, (I, {I^{\cup}}, \Delta)_{\ell-1}, \tau_{\ell}),
where during {\textsc{Expand}} each sampled element is processed by {\textsc{Adjust}} , and those passing the \textsc{Inspect} test are added to I ∪ ℓ {I^{\cup}}_{\ell} I ∪ ℓ . Thus, the newly added elements I ∪ ℓ ∖ I ∪ ℓ − 1 {I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1} I ∪ ℓ ∖ I ∪ ℓ − 1 are those in S ℓ S_\ell S ℓ that pass the \textsc{Inspect} test, also equal to S ℓ ∩ I ∪ ℓ S_{\ell} \cap {I^{\cup}}_\ell S ℓ ∩ I ∪ ℓ .
The \textsc{Inspect} test guarantees that the relative contribution of any element e e e added to I ∪ {I^{\cup}} I ∪ satisfies Δ ℓ ( e ) ≥ τ ℓ \Delta_\ell(e) \ge \tau_\ell Δ ℓ ( e ) ≥ τ ℓ . Moreover, by Lemma 10 , we have w ( e ) = Δ ℓ ( e ) w(e) = \Delta_\ell(e) w ( e ) = Δ ℓ ( e ) for any such element. Therefore, for any newly added element e e e , w ( e ) ≥ τ ℓ w(e) \ge \tau_\ell w ( e ) ≥ τ ℓ .
Furthermore, by construction, w ( I ∪ ℓ \ I ∪ ℓ − 1 ) w({I^{\cup}}_\ell \backslash {I^{\cup}}_{\ell-1}) w ( I ∪ ℓ \ I ∪ ℓ − 1 ) is the sum of the weights of the elements in I ∪ ℓ \ I ∪ ℓ − 1 {I^{\cup}}_\ell \backslash {I^{\cup}}_{\ell-1} I ∪ ℓ \ I ∪ ℓ − 1 . We therefore have
E [ w ( I ∪ ℓ \ I ∪ ℓ − 1 ) ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] = E [ ∑ e ∈ I ∪ ℓ ∖ I ∪ ℓ − 1 w ( e ) ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] ≥ E [ ∑ e ∈ S ℓ ∩ I ∪ ℓ τ ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] = τ ℓ E [ ∣ S ℓ ∩ I ∪ ℓ ∣ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] . \begin{align*}
{\mathbb{E}\left[w({I^{\cup}}_\ell \backslash {I^{\cup}}_{\ell-1}) \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}, s_\ell \in \texttt{Suit}_\ell\right]} &= {\mathbb{E}\left[\sum_{e \in {I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}} w(e) \mid \mathbf{H}_{< \ell}^{\text{s}}= H_{< \ell}^{\text{s}}, s_\ell \in \texttt{Suit}_\ell\right]} \\
&\ge {\mathbb{E}\left[\sum_{e \in S_{\ell} \cap {I^{\cup}}_\ell} \tau_\ell \mid \mathbf{H}_{< \ell}^{\text{s}}= H_{< \ell}^{\text{s}}, s_\ell \in \texttt{Suit}_\ell\right]} \\
&= \tau_\ell {\mathbb{E}\left[{\left|S_{\ell} \cap {I^{\cup}}_\ell \right|} \mid \mathbf{H}_{< \ell}^{\text{s}}= H_{< \ell}^{\text{s}}, s_\ell \in \texttt{Suit}_\ell\right]}.
\end{align*} E [ w ( I ∪ ℓ \ I ∪ ℓ − 1 ) ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] = E e ∈ I ∪ ℓ ∖ I ∪ ℓ − 1 ∑ w ( e ) ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ≥ E [ e ∈ S ℓ ∩ I ∪ ℓ ∑ τ ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] = τ ℓ E [ ∣ S ℓ ∩ I ∪ ℓ ∣ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] . Since S ℓ S_\ell S ℓ is an ordered sample of s ℓ s_\ell s ℓ elements from B ℓ B_\ell B ℓ , the condition s ℓ ∈ Suit ℓ s_{\ell} \in \texttt{Suit}_\ell s ℓ ∈ Suit ℓ and Lemma 17 give
E [ ∣ S ℓ ∩ I ∪ ℓ ∣ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] ≥ ( 1 − 3 ϵ sam 2 ) s ℓ , \begin{align*}
{\mathbb{E}\left[{\left|S_{\ell} \cap {I^{\cup}}_\ell \right|} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}, s_\ell \in \texttt{Suit}_\ell\right]} \ge (1- \frac{3\epsilon_{\textnormal{sam}}}{2})s_{\ell},
\end{align*} E [ ∣ S ℓ ∩ I ∪ ℓ ∣ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] ≥ ( 1 − 2 3 ϵ sam ) s ℓ , Combining the above with the initial inequality yields the desired bound
E [ w ( I ∪ ℓ \ I ∪ ℓ − 1 ) ∣ H < ℓ s = H < ℓ s ] ≥ ( 1 − 3 ϵ sam 2 ) τ ℓ s ℓ 1 [ s ℓ ∈ Suit ℓ ] . \begin{align*}
{\mathbb{E}\left[w({I^{\cup}}_\ell \backslash {I^{\cup}}_{\ell-1}) \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}} \right]}&\ge (1- \frac{3\epsilon_{\textnormal{sam}}}{2}) \tau_\ell s_\ell{\mathds{1}\left[s_\ell \in \texttt{Suit}_\ell\right]}.
\end{align*} E [ w ( I ∪ ℓ \ I ∪ ℓ − 1 ) ∣ H < ℓ s = H < ℓ s ] ≥ ( 1 − 2 3 ϵ sam ) τ ℓ s ℓ 1 [ s ℓ ∈ Suit ℓ ] . ◻
The following lemma bounds the total weight of elements added to I ∪ {I^{\cup}} I ∪ at layer ℓ \ell ℓ that belong to D D D , thereby quantifying the expected loss in the weight of I ∪ {I^{\cup}} I ∪ at this layer, due to the deletions.
Lemma 25. For any ℓ ∈ [ T ] \ell \in [T] ℓ ∈ [ T ] , the following holds: E [ w ( ( I ∪ ℓ \ I ∪ ℓ − 1 ) ∩ D ) ∣ H < ℓ s = H < ℓ s ] ≤ ϵ del ( 1 + ϵ ) τ ℓ s ℓ . \begin{aligned}
{\mathbb{E}\left[w(({I^{\cup}}_\ell \backslash {I^{\cup}}_{\ell-1}) \cap D ) \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}} \right]}\le
\epsilon_{\textnormal{del}}(1+\epsilon) \tau_\ell s_\ell.
\end{aligned} E [ w (( I ∪ ℓ \ I ∪ ℓ − 1 ) ∩ D ) ∣ H < ℓ s = H < ℓ s ] ≤ ϵ del ( 1 + ϵ ) τ ℓ s ℓ .
Proof. We consider a fixed ℓ ∈ [ T ] \ell \in [T] ℓ ∈ [ T ] and condition on H < ℓ s = H < ℓ s \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}} H < ℓ s = H < ℓ s . By Lemma (?) , we have
(I, {I^{\cup}}, \Delta)_{\ell} = {\textsc{Expand}}(\ensuremath{\mathbf{S}}_\ell, (I, {I^{\cup}}, \Delta)_{\ell-1}, \tau_{\ell}),
which means I ∪ ℓ ∖ I ∪ ℓ − 1 {I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1} I ∪ ℓ ∖ I ∪ ℓ − 1 is the set of elements in S ℓ {\mathbf{S}}_\ell S ℓ that are added to I ∪ ℓ {I^{\cup}}_{\ell} I ∪ ℓ during the {\textsc{Expand}} procedure. Thus, I ∪ ℓ ∖ I ∪ ℓ − 1 ⊆ S ℓ {I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1} \subseteq {\mathbf{S}}_\ell I ∪ ℓ ∖ I ∪ ℓ − 1 ⊆ S ℓ , and therefore
∣ ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ∣ ≤ ∣ S ℓ ∩ D ∣ {\left|({I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}) \cap D \right|}
\le {\left|{\mathbf{S}}_\ell \cap D \right|} ∣ ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ∣ ≤ ∣ S ℓ ∩ D ∣ By Lemma 23 , we know that S ℓ {\mathbf{S}}_\ell S ℓ is a uniform sample of size s ℓ s_\ell s ℓ from B ℓ B_\ell B ℓ , and by Lemma 7 , we have ∣ B ℓ ∩ D ∣ ≤ ϵ del ∣ B ℓ ∣ . {\left|B_{\ell} \cap D \right|} \leq \epsilon_{\textnormal{del}}{\left|B_{\ell} \right|}. ∣ B ℓ ∩ D ∣ ≤ ϵ del ∣ B ℓ ∣ . Therefore, we have
E [ ∣ ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ∣ ] ≤ E [ ∣ S ℓ ∩ D ∣ ] = s ℓ ∣ B ℓ ∣ ⋅ ∣ B ℓ ∩ D ∣ ≤ s ℓ ∣ B ℓ ∣ ⋅ ϵ del ∣ B ℓ ∣ ≤ ϵ del s ℓ . {\mathbb{E}\left[{\left|({I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}) \cap D \right|}\right]}
\le {\mathbb{E}\left[{\left|{\mathbf{S}}_\ell \cap D \right|} \right]}
= \frac{s_{\ell}}{{\left|B_{\ell} \right|}} \cdot {\left|B_{\ell} \cap D \right|}
\le \frac{s_{\ell}}{{\left|B_{\ell} \right|}} \cdot \epsilon_{\textnormal{del}}{\left|B_{\ell} \right|}
\le \epsilon_{\textnormal{del}}s_{\ell}. E [ ∣ ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ∣ ] ≤ E [ ∣ S ℓ ∩ D ∣ ] = ∣ B ℓ ∣ s ℓ ⋅ ∣ B ℓ ∩ D ∣ ≤ ∣ B ℓ ∣ s ℓ ⋅ ϵ del ∣ B ℓ ∣ ≤ ϵ del s ℓ . Furthermore, we know by Lemma 10 that w ( e ) = Δ ℓ ( e ) w(e) = \Delta_\ell(e) w ( e ) = Δ ℓ ( e ) for any element in I ∪ ℓ {I^{\cup}}_\ell I ∪ ℓ . On the other hand, for any element e ∈ B i e \in B_i e ∈ B i , we know that f ( e ∣ I ∪ ℓ − 1 ) ≤ ( 1 + ϵ ) τ ℓ f(e | {I^{\cup}}_{\ell - 1}) \le (1+\epsilon)\tau_\ell f ( e ∣ I ∪ ℓ − 1 ) ≤ ( 1 + ϵ ) τ ℓ . Also, by submodularity we know that the marginal contribution of element e e e at the time of its addition to I ∪ ℓ {I^{\cup}}_{\ell} I ∪ ℓ is less than or equal to its contribution with respect to I ∪ ℓ − 1 {I^{\cup}}_{\ell - 1} I ∪ ℓ − 1 , i.e., Δ ℓ ( e ) ≤ f ( e ∣ I ∪ ℓ − 1 ) \Delta_\ell(e) \le f(e | {I^{\cup}}_{\ell - 1}) Δ ℓ ( e ) ≤ f ( e ∣ I ∪ ℓ − 1 ) . Therefore, for any element e ∈ ( I ∪ ℓ \ I ∪ ℓ − 1 ) e \in ({I^{\cup}}_\ell \backslash {I^{\cup}}_{\ell-1}) e ∈ ( I ∪ ℓ \ I ∪ ℓ − 1 ) , we have
w ( e ) ≤ ( 1 + ϵ ) τ ℓ . w(e) \le (1+\epsilon)\tau_\ell. w ( e ) ≤ ( 1 + ϵ ) τ ℓ . By construction, w ( ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ) w(({I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}) \cap D) w (( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ) is the sum of the weights of all elements in ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ({I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}) \cap D ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D . Combining the above, we obtain
w ( ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ) = ∑ e ∈ ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D w ( e ) ≤ ∑ e ∈ ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ( 1 + ϵ ) τ ℓ = ( 1 + ϵ ) τ ℓ ⋅ ∣ ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ∣ \begin{align*}
w(({I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}) \cap D)
&= \sum_{e \in ({I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}) \cap D} w(e) \\
&\le \sum_{e \in ({I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}) \cap D} (1+\epsilon)\tau_\ell \\
&= (1+\epsilon)\tau_\ell \cdot {\left|({I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}) \cap D \right|}
\end{align*} w (( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ) = e ∈ ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ∑ w ( e ) ≤ e ∈ ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ∑ ( 1 + ϵ ) τ ℓ = ( 1 + ϵ ) τ ℓ ⋅ ∣ ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ∣ Combining the above proves that conditioned on H < ℓ s = H < ℓ s \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}} H < ℓ s = H < ℓ s ,
E [ w ( ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ) ] ≤ ϵ del ( 1 + ϵ ) τ ℓ s ℓ . {\mathbb{E}\left[w(({I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}) \cap D)\right]}
\le \epsilon_{\textnormal{del}}(1+\epsilon) \tau_\ell s_\ell. E [ w (( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ) ] ≤ ϵ del ( 1 + ϵ ) τ ℓ s ℓ . ◻
Building on the previous results, the following lemma demonstrates that I ∪ T {I^{\cup}}_T I ∪ T retains almost all of its weight after the removal of D D D .
Lemma 26. The following holds: E [ w ( I ∪ T ∖ D ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I ∪ T ) ] , {\mathbb{E}\left[{w}({{I^{\cup}}_T} \setminus D)\right]} \ge (1-\epsilon_2) {\mathbb{E}\left[{w}({{I^{\cup}}_T})\right]}, E [ w ( I ∪ T ∖ D ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I ∪ T ) ] , where ϵ 2 : = ϵ del ( 1 + ϵ ) 1 − 3 2 ϵ sam + 8 ϵ pr k 8 ϵ \epsilon_2 := \frac{\epsilon_{\textnormal{del}}(1+\epsilon)}{1 - \tfrac{3}{2}\epsilon_{\textnormal{sam}}} + \frac{8\epsilon_{\textnormal{pr}}}{k^{8}\epsilon} ϵ 2 := 1 − 2 3 ϵ sam ϵ del ( 1 + ϵ ) + k 8 ϵ 8 ϵ pr .
Proof. For each ℓ \ell ℓ , define the respective gain and loss of level ℓ \ell ℓ as
w ℓ : = w ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) , d ℓ : = w ( ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ) , {\mathbf{w}}_\ell := w({I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}), \quad
{\mathbf{d}}_\ell := w(({I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1}) \cap D), w ℓ := w ( I ∪ ℓ ∖ I ∪ ℓ − 1 ) , d ℓ := w (( I ∪ ℓ ∖ I ∪ ℓ − 1 ) ∩ D ) , with the convention that w ℓ = d ℓ = 0 {\mathbf{w}}_\ell = {\mathbf{d}}_\ell = 0 w ℓ = d ℓ = 0 for ℓ > T \ell > T ℓ > T . It follows from the definition that
w ( I ∪ T ) = ∑ ℓ = 1 ∞ w ℓ , w ( I ∪ T ∖ D ) = ∑ ℓ = 1 ∞ ( w ℓ − d ℓ ) . w({I^{\cup}}_T) = \sum_{\ell=1}^{\infty} {\mathbf{w}}_\ell,
\quad
w({I^{\cup}}_T \setminus D) = \sum_{\ell=1}^{\infty} ({\mathbf{w}}_\ell - {\mathbf{d}}_\ell). w ( I ∪ T ) = ℓ = 1 ∑ ∞ w ℓ , w ( I ∪ T ∖ D ) = ℓ = 1 ∑ ∞ ( w ℓ − d ℓ ) . We aim to show that for each ℓ \ell ℓ
E [ d ℓ ∣ H < ℓ ] ≤ ϵ 2 E [ w ℓ ∣ H < ℓ ] . \begin{align}
{\mathbb{E}\left[{\mathbf{d}}_\ell \mid \mathbf{H}_{< \ell}\right]} \le \epsilon_2 {\mathbb{E}\left[{\mathbf{w}}_\ell \mid \mathbf{H}_{< \ell}\right]}. \tag*{(15)}
\end{align} E [ d ℓ ∣ H < ℓ ] ≤ ϵ 2 E [ w ℓ ∣ H < ℓ ] . (15) By the law of iterated expectation, this implies
E [ d ℓ ] ≤ ϵ 2 E [ w ℓ ] , {\mathbb{E}\left[{\mathbf{d}}_\ell\right]} \le \epsilon_2 {\mathbb{E}\left[{\mathbf{w}}_\ell\right]}, E [ d ℓ ] ≤ ϵ 2 E [ w ℓ ] , and therefore
E [ w ℓ − d ℓ ] ≥ ( 1 − ϵ 2 ) E [ w ℓ ] . {\mathbb{E}\left[{\mathbf{w}}_\ell - {\mathbf{d}}_\ell\right]} \ge (1-\epsilon_2){\mathbb{E}\left[{\mathbf{w}}_\ell\right]}. E [ w ℓ − d ℓ ] ≥ ( 1 − ϵ 2 ) E [ w ℓ ] . Finally, summing over ℓ \ell ℓ and applying linearity of expectation yields
E [ w ( I ∪ T ∖ D ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I ∪ T ) ] , {\mathbb{E}\left[w({I^{\cup}}_T \setminus D)\right]} \ge (1-\epsilon_2){\mathbb{E}\left[w({I^{\cup}}_T)\right]}, E [ w ( I ∪ T ∖ D ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I ∪ T ) ] , which completes the proof.
To establish Equation (15) , it suffices to show that
E [ d ℓ ∣ H < ℓ s = H < ℓ s ] ≤ ϵ 2 E [ w ℓ ∣ H < ℓ s = H < ℓ s ] , \begin{align}
{\mathbb{E}\left[{\mathbf{d}}_\ell \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]}
\le \epsilon_2 \, {\mathbb{E}\left[{\mathbf{w}}_\ell \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]}, \tag*{(16)}
\end{align} E [ d ℓ ∣ H < ℓ s = H < ℓ s ] ≤ ϵ 2 E [ w ℓ ∣ H < ℓ s = H < ℓ s ] , (16) for any H < ℓ s H_{< \ell}^{\text{s}} H < ℓ s with P [ H < ℓ s = H < ℓ s ] > 0 {\mathbb{P}\left[\mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]} > 0 P [ H < ℓ s = H < ℓ s ] > 0 .
By Lemma 24 , we have
E [ w ℓ ∣ H < ℓ s = H < ℓ s ] ≥ ( 1 − 3 ϵ sam 2 ) s ℓ τ ℓ 1 [ s ℓ ∈ Suit ℓ ] . {\mathbb{E}\left[{\mathbf{w}}_\ell \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]}
\ge \Bigl(1- \tfrac{3\epsilon_{\textnormal{sam}}}{2}\Bigr)s_\ell \tau_\ell {\mathds{1}\left[s_\ell \in \texttt{Suit}_\ell\right]}. E [ w ℓ ∣ H < ℓ s = H < ℓ s ] ≥ ( 1 − 2 3 ϵ sam ) s ℓ τ ℓ 1 [ s ℓ ∈ Suit ℓ ] . On the other hand, by Lemma 25 , we have
E [ d ℓ ∣ H < ℓ s = H < ℓ s ] ≤ ϵ del ( 1 + ϵ ) τ ℓ s ℓ . {\mathbb{E}\left[{\mathbf{d}}_\ell \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]}
\le \epsilon_{\textnormal{del}}(1+\epsilon)\tau_\ell s_\ell. E [ d ℓ ∣ H < ℓ s = H < ℓ s ] ≤ ϵ del ( 1 + ϵ ) τ ℓ s ℓ . Combining the above gives us
1 [ s ℓ ∈ Suit ℓ ] E [ d ℓ ∣ H < ℓ s = H < ℓ s ] ≤ ϵ del ( 1 + ϵ ) 1 − 3 ϵ sam 2 E [ w ℓ ∣ H < ℓ s = H < ℓ s ] , {\mathds{1}\left[s_\ell \in \texttt{Suit}_\ell\right]} {\mathbb{E}\left[{\mathbf{d}}_\ell \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]}
\le
\frac{\epsilon_{\textnormal{del}}(1+\epsilon)}{1 - \tfrac{3\epsilon_{\textnormal{sam}}}{2}}\;
{\mathbb{E}\left[{\mathbf{w}}_\ell \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]}, 1 [ s ℓ ∈ Suit ℓ ] E [ d ℓ ∣ H < ℓ s = H < ℓ s ] ≤ 1 − 2 3 ϵ sam ϵ del ( 1 + ϵ ) E [ w ℓ ∣ H < ℓ s = H < ℓ s ] , which then implies
E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] ≤ ϵ del ( 1 + ϵ ) 1 − 3 ϵ sam 2 E [ w ℓ ∣ H < ℓ s = H < ℓ s ] . {\mathbb{E}\left[{\mathbf{d}}_\ell \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}, s_\ell \in \texttt{Suit}_\ell\right]}
\le
\frac{\epsilon_{\textnormal{del}}(1+\epsilon)}{1 - \tfrac{3\epsilon_{\textnormal{sam}}}{2}}\;
{\mathbb{E}\left[{\mathbf{w}}_\ell \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]}. E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] ≤ 1 − 2 3 ϵ sam ϵ del ( 1 + ϵ ) E [ w ℓ ∣ H < ℓ s = H < ℓ s ] . By Lemma 21 , we have P [ s ℓ ∈ Suit ℓ ∣ H < ℓ = H < ℓ ] ≥ 1 − ϵ pr k 10 . {\mathbb{P}\left[{\mathbf{s}}_\ell \in \texttt{Suit}_\ell \mid \mathbf{H}_{< \ell} = H_{< \ell}\right]} \ge 1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}}. P [ s ℓ ∈ Suit ℓ ∣ H < ℓ = H < ℓ ] ≥ 1 − k 10 ϵ pr . Hence,
P [ s ℓ ∉ Suit ℓ ∣ H < ℓ = H < ℓ ] ≤ ϵ pr k 10 . \begin{align*}
{\mathbb{P}\left[{\mathbf{s}}_\ell \notin \texttt{Suit}_\ell \mid \mathbf{H}_{< \ell} = H_{< \ell}\right]} \le \frac{\epsilon_{\textnormal{pr}}}{k^{10}}.
\end{align*} P [ s ℓ ∈ / Suit ℓ ∣ H < ℓ = H < ℓ ] ≤ k 10 ϵ pr . By above inequalities and the law of total expectation we have
E [ d ℓ ∣ H < ℓ s = H < ℓ s ] = E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] P [ s ℓ ∈ Suit ℓ ∣ H < ℓ = H < ℓ ] + E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∉ Suit ℓ ] P [ s ℓ ∉ Suit ℓ ∣ H < ℓ = H < ℓ ] ≤ E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] + E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∉ Suit ℓ ] P [ s ℓ ∉ Suit ℓ ∣ H < ℓ = H < ℓ ] ≤ ϵ del ( 1 + ϵ ) 1 − 3 2 ϵ sam E [ w ℓ ∣ H < ℓ s = H < ℓ s ] + ϵ pr k 10 E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∉ Suit ℓ ] . \begin{align*}
{\mathbb{E}\left[{{\mathbf{d}}_{\ell}} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]}
&=
{\mathbb{E}\left[{{\mathbf{d}}_{\ell}} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}, s_\ell \in \texttt{Suit}_\ell\right]}
{\mathbb{P}\left[{\mathbf{s}}_\ell \in \texttt{Suit}_\ell \mid \mathbf{H}_{< \ell} = H_{< \ell}\right]} \\
&+
{\mathbb{E}\left[{{\mathbf{d}}_{\ell}} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}, s_\ell \notin \texttt{Suit}_\ell\right]}
{\mathbb{P}\left[{\mathbf{s}}_\ell \notin \texttt{Suit}_\ell \mid \mathbf{H}_{< \ell} = H_{< \ell}\right]} \\
&\le
{\mathbb{E}\left[{{\mathbf{d}}_{\ell}} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}, s_\ell \in \texttt{Suit}_\ell\right]} \\
&+
{\mathbb{E}\left[{{\mathbf{d}}_{\ell}} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}, s_\ell \notin \texttt{Suit}_\ell\right]}
{\mathbb{P}\left[{\mathbf{s}}_\ell \notin \texttt{Suit}_\ell \mid \mathbf{H}_{< \ell} = H_{< \ell}\right]} \\
&\le
\frac{\epsilon_{\textnormal{del}}(1+\epsilon)}{1 - \tfrac{3}{2}\epsilon_{\textnormal{sam}}}
{\mathbb{E}\left[{\mathbf{w}}_\ell \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]} +
\frac{\epsilon_{\textnormal{pr}}}{k^{10}}
{\mathbb{E}\left[{{\mathbf{d}}_{\ell}} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}, s_\ell \notin \texttt{Suit}_\ell\right]}.
\end{align*} E [ d ℓ ∣ H < ℓ s = H < ℓ s ] = E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] P [ s ℓ ∈ Suit ℓ ∣ H < ℓ = H < ℓ ] + E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ / Suit ℓ ] P [ s ℓ ∈ / Suit ℓ ∣ H < ℓ = H < ℓ ] ≤ E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ Suit ℓ ] + E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ / Suit ℓ ] P [ s ℓ ∈ / Suit ℓ ∣ H < ℓ = H < ℓ ] ≤ 1 − 2 3 ϵ sam ϵ del ( 1 + ϵ ) E [ w ℓ ∣ H < ℓ s = H < ℓ s ] + k 10 ϵ pr E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ / Suit ℓ ] . By definition, we know that d ℓ ≤ w ( I ∪ T ) {\mathbf{d}}_{\ell} \le w({I^{\cup}}_T) d ℓ ≤ w ( I ∪ T ) . Then, by Lemma 11 , it follows that d ℓ ≤ 2 w ( I T ) {\mathbf{d}}_{\ell} \le 2\, w(I_T) d ℓ ≤ 2 w ( I T ) . Moreover, we know that I T I_T I T contains at most k k k elements and for each element e e e , we have w ( e ) ≤ f ( e ) ≤ 4 k ϵ τ w(e) \le f(e) \le \frac{4k}{\epsilon}\, \tau w ( e ) ≤ f ( e ) ≤ ϵ 4 k τ . Therefore, we conclude that d ℓ {\mathbf{d}}_{\ell} d ℓ is deterministically bounded by 2 k ⋅ 4 k ϵ τ 2k \cdot \frac{4k}{\epsilon}\tau 2 k ⋅ ϵ 4 k τ .
Meanwhile, we know that E [ w ℓ ∣ H < ℓ s = H < ℓ s ] ≥ τ {\mathbb{E}\left[{\mathbf{w}}_{\ell} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]} \ge \tau E [ w ℓ ∣ H < ℓ s = H < ℓ s ] ≥ τ since conditioning on H < ℓ s = H < ℓ s \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}} H < ℓ s = H < ℓ s implies that ℓ ≤ T \ell \leq {\mathbf{T}} ℓ ≤ T , which ensures there is at least one element in I ∪ ℓ ∖ I ∪ ℓ − 1 {I^{\cup}}_\ell \setminus {I^{\cup}}_{\ell-1} I ∪ ℓ ∖ I ∪ ℓ − 1 . Thus, we obtain the following bound:
E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∉ Suit ℓ ] ≤ 8 k 2 ϵ E [ w ℓ ∣ H < ℓ s = H < ℓ s ] . {\mathbb{E}\left[{{\mathbf{d}}_{\ell}} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}, s_\ell \notin \texttt{Suit}_\ell\right]} \le \frac{8k^2}{\epsilon} {\mathbb{E}\left[{\mathbf{w}}_{\ell} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]}. E [ d ℓ ∣ H < ℓ s = H < ℓ s , s ℓ ∈ / Suit ℓ ] ≤ ϵ 8 k 2 E [ w ℓ ∣ H < ℓ s = H < ℓ s ] . This gives us
E [ d ℓ ∣ H < ℓ s = H < ℓ s ] ≤ ϵ del ( 1 + ϵ ) 1 − 3 2 ϵ sam E [ w ℓ ∣ H < ℓ s = H < ℓ s ] + 8 ϵ pr k 8 ϵ E [ w ℓ ∣ H < ℓ s = H < ℓ s ] , \begin{align*}
{\mathbb{E}\left[{{\mathbf{d}}_{\ell}} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]}
&\le
\frac{\epsilon_{\textnormal{del}}(1+\epsilon)}{1 - \tfrac{3}{2}\epsilon_{\textnormal{sam}}}
{\mathbb{E}\left[{\mathbf{w}}_\ell \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]} +
\frac{8\epsilon_{\textnormal{pr}}}{k^{8}\epsilon}
{\mathbb{E}\left[{\mathbf{w}}_{\ell} \mid \mathbf{H}_{< \ell}^{\text{s}} = H_{< \ell}^{\text{s}}\right]},
\end{align*} E [ d ℓ ∣ H < ℓ s = H < ℓ s ] ≤ 1 − 2 3 ϵ sam ϵ del ( 1 + ϵ ) E [ w ℓ ∣ H < ℓ s = H < ℓ s ] + k 8 ϵ 8 ϵ pr E [ w ℓ ∣ H < ℓ s = H < ℓ s ] , which establishes Equation (16) and completes the proof. ◻
Using the previous lemma, we extend the earlier guarantee and show that the expected weight of I T I_T I T remains nearly unchanged after the removal of D D D .
Lemma 27. The following holds: ( 1 − 2 ϵ 2 ) E [ w ( I T ) ] ≤ E [ w ( I T \ D ) ] . (1-2\epsilon_2) {\mathbb{E}\left[{w}({I_T})\right]} \le {\mathbb{E}\left[{w}({I_T} \backslash D)\right]}. ( 1 − 2 ϵ 2 ) E [ w ( I T ) ] ≤ E [ w ( I T \ D ) ] .
Proof. Let Z T = I ∪ T ∖ I T Z_T = {I^{\cup}}_T \setminus I_T Z T = I ∪ T ∖ I T . By Lemma 26 we have:
E [ w ( I ∪ T \ D ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I ∪ T ) ] . {\mathbb{E}\left[{w}({{I^{\cup}}_T} \backslash D)\right]} \ge (1-\epsilon_2) {\mathbb{E}\left[{w}({{I^{\cup}}_T})\right]}. E [ w ( I ∪ T \ D ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I ∪ T ) ] . Using the linearity of expectation for partition I ∪ T = I T ∪ Z T {I^{\cup}}_T = I_T \cup Z_T I ∪ T = I T ∪ Z T gives us:
E [ w ( I T \ D ) ] + E [ w ( Z T \ D ) ] ≥ ( 1 − ϵ 2 ) ( E [ w ( I T ) ] + E [ w ( Z T ) ] ) . {\mathbb{E}\left[{w}({I_T}\backslash D)\right]} + {\mathbb{E}\left[{w}({Z_T}\backslash D)\right]} \ge (1-\epsilon_2) \left({\mathbb{E}\left[{w}({I_T})\right]} + {\mathbb{E}\left[{w}({Z_T})\right]}\right). E [ w ( I T \ D ) ] + E [ w ( Z T \ D ) ] ≥ ( 1 − ϵ 2 ) ( E [ w ( I T ) ] + E [ w ( Z T ) ] ) . By using the simple bound E [ w ( Z T \ D ) ] ≤ E [ w ( Z T ) ] {\mathbb{E}\left[w(Z_T \backslash D)\right]} \le {\mathbb{E}\left[w(Z_T)\right]} E [ w ( Z T \ D ) ] ≤ E [ w ( Z T ) ] , we obtain:
E [ w ( I T \ D ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I T ) ] + ( 1 − ϵ 2 ) E [ w ( Z T ) ] − E [ w ( Z T ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I T ) ] − ϵ 2 E [ w ( Z T ) ] . \begin{align}
{\mathbb{E}\left[{w}({I_T}\backslash D)\right]}
&\ge (1-\epsilon_2) {\mathbb{E}\left[{w}({I_T})\right]} + (1-\epsilon_2) {\mathbb{E}\left[{w}({Z_T})\right]} - {\mathbb{E}\left[{w}({Z_T})\right]}
\notag
\\&\ge (1-\epsilon_2){\mathbb{E}\left[{w}({I_T})\right]} - \epsilon_2 {\mathbb{E}\left[{w}({Z_T})\right]}. \tag*{(17)}
\end{align} E [ w ( I T \ D ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I T ) ] + ( 1 − ϵ 2 ) E [ w ( Z T ) ] − E [ w ( Z T ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I T ) ] − ϵ 2 E [ w ( Z T ) ] . (17) By Lemma 11 and then applying linearity of expectation to the partition I ∪ T = I T ∪ Z T {I^{\cup}}_T = I_T \cup Z_T I ∪ T = I T ∪ Z T again, we have
2 E [ w ( I T ) ] ≥ E [ w ( I ∪ T ) ] = E [ w ( I T ) ] + E [ w ( Z T ) ] , \begin{align*}
2{\mathbb{E}\left[{w}({I_T})\right]} \ge {\mathbb{E}\left[{w}({{I^{\cup}}_T})\right]} = {\mathbb{E}\left[{w}({I_T})\right]} + {\mathbb{E}\left[{w}({Z_T})\right]},
\end{align*} 2 E [ w ( I T ) ] ≥ E [ w ( I ∪ T ) ] = E [ w ( I T ) ] + E [ w ( Z T ) ] , which in turn implies that
E [ w ( I T ) ] ≥ E [ w ( Z T ) ] . {\mathbb{E}\left[{w}({I_T})\right]} \ge {\mathbb{E}\left[{w}({Z_T})\right]}. E [ w ( I T ) ] ≥ E [ w ( Z T ) ] . Combining this and Equation (17) completes the proof:
E [ w ( I T \ D ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I T ) ] − ϵ 2 E [ w ( Z T ) ] . ≥ ( 1 − ϵ 2 ) E [ w ( I T ) ] − ϵ 2 E [ w ( I T ) ] ≥ ( 1 − 2 ϵ 2 ) E [ w ( I T ) ] . \begin{align*}
{\mathbb{E}\left[{w}({I_T}\backslash D)\right]}
& \ge (1-\epsilon_2){\mathbb{E}\left[{w}({I_T})\right]} - \epsilon_2 {\mathbb{E}\left[{w}({Z_T})\right]}.
\\&\ge (1-\epsilon_2){\mathbb{E}\left[{w}({I_T})\right]} - \epsilon_2 {\mathbb{E}\left[{w}({I_T})\right]}
\\& \ge (1-2\epsilon_2){\mathbb{E}\left[{w}({I_T})\right]}.
\end{align*} E [ w ( I T \ D ) ] ≥ ( 1 − ϵ 2 ) E [ w ( I T ) ] − ϵ 2 E [ w ( Z T ) ] . ≥ ( 1 − ϵ 2 ) E [ w ( I T ) ] − ϵ 2 E [ w ( I T ) ] ≥ ( 1 − 2 ϵ 2 ) E [ w ( I T ) ] . ◻
The next lemma bounds the weight of I T ∖ D I_T \setminus D I T ∖ D by its function value.
Lemma 28. The following holds: w ( I T ∖ D ) ≤ f ( I T ∖ D ) w(I_T \setminus D) \le f(I_T \setminus D) w ( I T ∖ D ) ≤ f ( I T ∖ D ) .
Proof. Let e 1 , e 2 , … , e ∣ I T ∖ D ∣ e_1, e_2, \ldots, e_{{\left|I_T \setminus D \right|}} e 1 , e 2 , … , e ∣ I T ∖ D ∣ denote the elements of I T ∖ D I_T \setminus D I T ∖ D in their processing order. We have
f ( I T ∖ D ) = ∑ i f ( e i ∣ { e 1 , e 2 , … , e i − 1 } ) . f(I_T \setminus D) = \sum_{i}{f(e_i | \{e_1, e_2, \ldots, e_{i - 1}\})}. f ( I T ∖ D ) = i ∑ f ( e i ∣ { e 1 , e 2 , … , e i − 1 }) . Let’s use I ∪ e i {I^{\cup}}_{e_i} I ∪ e i to denote the state of I ∪ {I^{\cup}} I ∪ right before processing element e i e_i e i . By definition we have
w ( I T ∖ D ) = ∑ i w ( e i ) = ∑ i f ( e i ∣ I ∪ e i ) , w(I_T \setminus D) = \sum_{i}{w(e_i)}
= \sum_{i}f(e_i | {I^{\cup}}_{e_i})
, w ( I T ∖ D ) = i ∑ w ( e i ) = i ∑ f ( e i ∣ I ∪ e i ) , where the second equality holds because of Lemmas 9 and 10 .
We know that { e 1 , e 2 , … , e i − 1 } ⊆ I ∪ e i \{e_1, e_2, \ldots, e_{i - 1}\} \subseteq {I^{\cup}}_{e_i} { e 1 , e 2 , … , e i − 1 } ⊆ I ∪ e i . Therefore, by submodularity of f f f we have
f ( e i ∣ I ∪ e i ) ≤ f ( e i ∣ { e 1 , e 2 , … , e i − 1 } ) , f(e_i | {I^{\cup}}_{e_i}) \le f(e_i | \{e_1, e_2, \ldots, e_{i - 1}\}), f ( e i ∣ I ∪ e i ) ≤ f ( e i ∣ { e 1 , e 2 , … , e i − 1 }) , which completes the proof. ◻
Finally, by combining the established results, we prove the approximation guarantee of our algorithm in the following theorem.
Theorem 29. There exists an instance I \mathcal{I} I produced by Algorithm alg:parallel such that E [ f ( I T ∖ D ) ] ≥ 1 4 ( 1 − ϵ 2 ) ( 1 − 2 ϵ 2 ) f ( I ∗ ) , \mathbb{E}[f(I_T \setminus D)] \ge \frac{1}{4}\left(1 - \frac{\epsilon}{2}\right)(1-2\epsilon_2) f(I^*), E [ f ( I T ∖ D )] ≥ 4 1 ( 1 − 2 ϵ ) ( 1 − 2 ϵ 2 ) f ( I ∗ ) , where I ∗ I^* I ∗ is the optimal independent set and the expectation is taken over the randomness of the algorithm. Equivalently, the algorithm achieves an expected ( 4 + O ( ϵ ) ) (4 + O(\epsilon)) ( 4 + O ( ϵ )) -approximation.
Proof. Lemma 15 guarantees the existence of an instance I \mathcal{I} I in Algorithm alg:parallel such that
1 4 ( 1 − ϵ 2 ) f ( I ∗ ) < w ( I T ) . \frac{1}{4}\left(1 - \frac{\epsilon}{2}\right) f(I^*) < w(I_T). 4 1 ( 1 − 2 ϵ ) f ( I ∗ ) < w ( I T ) . By Lemma 27 , we further have
( 1 − 2 ϵ 2 ) E [ w ( I T ) ] ≤ E [ w ( I T ∖ D ) ] , (1-2\epsilon_2) {\mathbb{E}\left[w(I_T)\right]} \le {\mathbb{E}\left[w(I_T \setminus D)\right]}, ( 1 − 2 ϵ 2 ) E [ w ( I T ) ] ≤ E [ w ( I T ∖ D ) ] , and by Lemma 28 ,
w ( I T ∖ D ) ≤ f ( I T ∖ D ) . w(I_T \setminus D) \le f(I_T \setminus D). w ( I T ∖ D ) ≤ f ( I T ∖ D ) . Combining these inequalities yields an instance for which the following final bound holds:
1 4 ( 1 − ϵ 2 ) ( 1 − 2 ϵ 2 ) f ( I ∗ ) ≤ E [ f ( I T ∖ D ) ] . \frac{1}{4}\left(1 - \frac{\epsilon}{2}\right) (1-2\epsilon_2) f(I^*) \le {\mathbb{E}\left[f(I_T \setminus D)\right]}. 4 1 ( 1 − 2 ϵ ) ( 1 − 2 ϵ 2 ) f ( I ∗ ) ≤ E [ f ( I T ∖ D ) ] . The proof is complete. ◻
Query Time
In this section, we analyze the query complexity of our algorithm.
We begin by introducing a potential-based framework to track the progress of elements across layers, which enables us to bound the number of layers.
Definition 30 (Potential). For any i ≥ 1 i \ge 1 i ≥ 1 , let E ‾ i \overline{E}_{i} E i denote ( E i ∪ A i ) (E_{i} \cup A_{i}) ( E i ∪ A i ) . For any element e ∈ E ‾ i e \in \overline{E}_{i} e ∈ E i , we define the potential of element e e e with respect to the layer i i i as: P ( e , i ) : = ⌊ log 1 + ϵ ( f ( e ∣ I ∪ i − 1 ) τ ) ⌋ + 1. P(e, i) := \left\lfloor\,\log_{1+\epsilon}(\frac{f(e | {I^{\cup}}_{i - 1})}{\tau})\,\right\rfloor + 1. P ( e , i ) := ⌊ log 1 + ϵ ( τ f ( e ∣ I ∪ i − 1 ) ) ⌋ + 1. For an element e ∉ E ‾ i e\notin \overline{E}_{i} e ∈ / E i , we define P ( e , i ) P(e, i) P ( e , i ) to be zero.
We also, define the potential of layer i i i as: P i : = ∑ e ∈ E ‾ i P ( e , i ) . P_i := \sum_{e\in \overline{E}_{i}} P(e, i). P i := ∑ e ∈ E i P ( e , i ) .
We then establish some fundamental properties of the potential function that will be used in our analysis.
Lemma 31. The followings hold: ∀ e ∈ E ‾ i : P ( e , i ) ∈ [ 1 , ⌈ log 1 + ϵ ( 4 k ϵ ) ⌉ ] ∣ E ‾ i ∣ ≤ P i ≤ ∣ E ‾ i ∣ ⋅ ⌈ log 1 + ϵ ( 4 k ϵ ) ⌉ P T + 1 = 0 \begin{aligned}
&\forall e \in \overline{E}_{i}: P(e, i)\in \left[1, {\left\lceil \log_{1+\epsilon}(\frac{4k}{\epsilon}) \right\rceil}\right]
\\&
|\overline{E}_i| \le P_i \le |\overline{E}_i| \cdot {\left\lceil \log_{1+\epsilon}(\frac{4k}{\epsilon}) \right\rceil}
\\&
P_{T + 1} = 0 % \quad\text{ and }\quad \forall i \le T: P_{i} > 0
\end{aligned} ∀ e ∈ E i : P ( e , i ) ∈ [ 1 , ⌈ log 1 + ϵ ( ϵ 4 k ) ⌉ ] ∣ E i ∣ ≤ P i ≤ ∣ E i ∣ ⋅ ⌈ log 1 + ϵ ( ϵ 4 k ) ⌉ P T + 1 = 0
Proof. For any element e ∈ E ‾ 1 e \in \overline{E}_{1} e ∈ E 1 , we know that τ ≤ f ( e ) < τ ⋅ 4 k ϵ \tau \le f(e) < \tau \cdot \frac{4k}{\epsilon} τ ≤ f ( e ) < τ ⋅ ϵ 4 k . Additionally, for any i > 1 i > 1 i > 1 , for any element e e e in either E i E_{i} E i or A i A_i A i , we know that \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_{i - 1}, \tau) \ne \textsc{Fail} . Hence, f ( e ∣ I ∪ i − 1 ) > τ . f(e | {I^{\cup}}_{i - 1}) > \tau. f ( e ∣ I ∪ i − 1 ) > τ . Therefore, the first property always holds.
The second property follows from the first one since P ( e , i ) = 0 P(e, i) = 0 P ( e , i ) = 0 for e ∉ E ^ 1 e\notin \hat{E}_{1} e ∈ / E ^ 1 .
We know by Lemma 6 that E T + 1 = ∅ E_{T + 1} = \emptyset E T + 1 = ∅ . Moreover, Lemma 7 implies that A T + 1 = ∅ A_{T + 1} = \emptyset A T + 1 = ∅ . Hence, E ‾ T + 1 = ∅ \overline{E}_{T + 1} = \emptyset E T + 1 = ∅ . Therefore, the third property also holds. ◻
Next, we show that the potential of an element is decreasing through the layers.
Lemma 32. For any i ∈ [ 1 , T ] i \in [1, T] i ∈ [ 1 , T ] , and any arbitrary element e e e , P ( e , i ) ≥ P ( e , i + 1 ) P(e, i) \ge P(e, i+1) P ( e , i ) ≥ P ( e , i + 1 ) and therefore, P i ≥ P i + 1 P_{i} \ge P_{i+1} P i ≥ P i + 1 .
Proof. If e ∉ E ‾ i + 1 e \notin \overline{E}_{i + 1} e ∈ / E i + 1 , the claim holds because P ( e , i + 1 ) = 0 P(e, i + 1) = 0 P ( e , i + 1 ) = 0 . It also holds for e ∈ E ‾ i + 1 e \in \overline{E}_{i + 1} e ∈ E i + 1 due to the submodularity of f f f and the fact that I ∪ i ⊆ I ∪ i + 1 {I^{\cup}}_i \subseteq {I^{\cup}}_{i + 1} I ∪ i ⊆ I ∪ i + 1 . ◻
The following is an auxiliary fact that will be used to bound the expected number of layers in our data structure.
Fact 33. Let X 0 , X 1 , … , X n {\mathbf{X}}_0, {\mathbf{X}}_1, \dots, {\mathbf{X}}_n X 0 , X 1 , … , X n be a sequence of integer positive variables such that X i ≤ X i − 1 {\mathbf{X}}_{i} \le {\mathbf{X}}_{i-1} X i ≤ X i − 1 and E [ X i ∣ X 1 = X 1 , … , X i − 1 = X i − 1 ] ≤ ( 1 − ϵ ′ ) X i − 1 . \begin{aligned}
{\mathbb{E}\left[{\mathbf{X}}_i \mid {\mathbf{X}}_1 = X_1, \dots, {\mathbf{X}}_{i-1} = X_{i-1}\right]}
\le
(1-\epsilon') {X_{i-1}}.
\end{aligned} E [ X i ∣ X 1 = X 1 , … , X i − 1 = X i − 1 ] ≤ ( 1 − ϵ ′ ) X i − 1 . Let T T T denote the first index i i i such that X T = 0 X_T = 0 X T = 0 and assume that X 0 = N {\mathbf{X}}_0=N X 0 = N for some fixed integer N N N . Then E [ T ] ≤ log ( N ) + 1 poly ( ϵ ′ ) {\mathbb{E}\left[{\mathbf{T}}\right]} \le \frac{\log(N) + 1}{\textnormal{poly}(\epsilon')} E [ T ] ≤ poly ( ϵ ′ ) l o g ( N ) + 1 .
The following two lemmas quantify the expected decrease in potential across consecutive layers, showing that, in expectation, a substantial fraction of the potential diminishes at each layer.
Lemma 34. For any value of i ≥ 1 i \ge 1 i ≥ 1 , the following holds: E [ P i − P i + 1 ∣ H < i s = H < i s ] ≥ ϵ sam 2 ⋅ ∣ B i ∣ ⋅ 1 [ s i ∈ Suit i ] . \begin{aligned}
{\mathbb{E}\left[P_{i} - {\mathbf{P}}_{i+1} \big| \mathbf{H}_{< i}^{\text{s}}=H_{< i}^{\text{s}}\right]} \ge
\frac{\epsilon_{\textnormal{sam}}}{2} \cdot {\left|B_{i} \right|} \cdot
{\mathds{1}\left[s_i \in \texttt{Suit}_i\right]}
.
\end{aligned} E [ P i − P i + 1 H < i s = H < i s ] ≥ 2 ϵ sam ⋅ ∣ B i ∣ ⋅ 1 [ s i ∈ Suit i ] .
Proof. We know that P ( e , i ) = 0 P(e, i) = 0 P ( e , i ) = 0 for any e ∉ E ‾ i e \notin \overline{E}_i e ∈ / E i . Hence,
P i − P i + 1 = ∑ e ∈ E ‾ i P ( e , i ) − P ( e , i + 1 ) ≥ ∑ e ∈ E ‾ i 1 [ P ( e , i ) − P ( e , i + 1 ) ≥ 1 ] = ∑ e ∈ B i 1 [ P ( e , i ) − P ( e , i + 1 ) ≥ 1 ] + ∑ e ∈ E ‾ i ∖ B i 1 [ P ( e , i ) − P ( e , i + 1 ) ≥ 1 ] ≥ ∑ e ∈ B i 1 [ P ( e , i ) − P ( e , i + 1 ) ≥ 1 ] . \begin{align*}
P_{i} - P_{i+1}
&= \sum_{e \in \overline{E}_{i}} P(e, i) - P(e, i + 1) \\
& \ge \sum_{e \in \overline{E}_{i}} {\mathds{1}\left[P(e, i) - P(e, i+1) \ge 1\right]}\\
&= \sum_{e \in B_{i}} {\mathds{1}\left[P(e, i) - P(e, i+1) \ge 1\right]}
+
\sum_{e \in \overline{E}_{i} \setminus B_{i}}
{\mathds{1}\left[P(e, i) - P(e, i+1) \ge 1\right]} \\
&\ge \sum_{e \in B_{i}} {\mathds{1}\left[P(e, i) - P(e, i+1) \ge 1\right]}. %\\
%& = \sum_{e \in \buck_i \setminus \setd} \ind{P(e, i) - P(e, i+1) \ge 1}.
\end{align*} P i − P i + 1 = e ∈ E i ∑ P ( e , i ) − P ( e , i + 1 ) ≥ e ∈ E i ∑ 1 [ P ( e , i ) − P ( e , i + 1 ) ≥ 1 ] = e ∈ B i ∑ 1 [ P ( e , i ) − P ( e , i + 1 ) ≥ 1 ] + e ∈ E i ∖ B i ∑ 1 [ P ( e , i ) − P ( e , i + 1 ) ≥ 1 ] ≥ e ∈ B i ∑ 1 [ P ( e , i ) − P ( e , i + 1 ) ≥ 1 ] . The inequality comes from the fact that P ( e , ℓ ) P(e, \ell) P ( e , ℓ ) is decreasing by Lemma 32 and an integer by definition, so P ( e , i ) − P ( e , i + 1 ) P(e, i) - P(e, i + 1) P ( e , i ) − P ( e , i + 1 ) is either 0 or it can be bounded by 1.
We know that if e ∈ B i e \in B_i e ∈ B i , then P ( e , i ) ≥ 1 P(e, i) \ge 1 P ( e , i ) ≥ 1 . We also know that if \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_i, \tau) = \textsc{Fail} , then e ∉ E ‾ i + 1 e \notin \overline{E}_{i + 1} e ∈ / E i + 1 , which means that P ( e , i + 1 ) = 0 P(e, i + 1) = 0 P ( e , i + 1 ) = 0 . Hence, for any e ∈ B i e \in B_i e ∈ B i such that \textsc{Inspect}(e, (I, {I^{\cup}}, \Delta)_i, \tau) = \textsc{Fail} , 1 [ P ( e , i ) − P ( e , i + 1 ) ≥ 1 ] = 1 {\mathds{1}\left[P(e, i) - P(e, i+1) \ge 1\right]} = 1 1 [ P ( e , i ) − P ( e , i + 1 ) ≥ 1 ] = 1 .
By Lemma 17 , we have assuming that s i ∈ Suit i s_i \in \texttt{Suit}_i s i ∈ Suit i , then
\ensuremath{\mathbb{E}\left[
{\left|\left\{\,e \in B_i: \textsc{Inspect}{}(e, (I, {I^{\cup}}, \Delta)_{i}, \tau) = \textsc{Fail}\,\right\} \right|}\right]} \ge (\frac{\epsilon_{\textnormal{sam}}}{2}){\left|B_i \right|}.
The proof is complete. ◻
Lemma 35. For any value of i ≥ 1 i \ge 1 i ≥ 1 , the following holds: E [ P i − P i + 1 ∣ H < i = H < i ] ≥ ( 1 − ϵ pr k 10 ) ⋅ ϵ sam 2 ⋅ ∣ B i ∣ ≥ ϵ sam 4 ⋅ ∣ B i ∣ . \begin{aligned}
{\mathbb{E}\left[P_{i} - {\mathbf{P}}_{i+1} \big| \mathbf{H}_{< i}=H_{< i}\right]} \ge
(1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}}) \cdot \frac{\epsilon_{\textnormal{sam}}}{2} \cdot {\left|B_{i} \right|} \ge
\frac{\epsilon_{\textnormal{sam}}}{4} \cdot {\left|B_{i} \right|}.
\end{aligned} E [ P i − P i + 1 H < i = H < i ] ≥ ( 1 − k 10 ϵ pr ) ⋅ 2 ϵ sam ⋅ ∣ B i ∣ ≥ 4 ϵ sam ⋅ ∣ B i ∣ .
Proof. By the law of iterated expectation and the previous Lemma, we have
E [ P i − P i + 1 ∣ H < i = H < i ] = E [ E [ P i − P i + 1 ∣ H < i s = H < i s ] ] ≥ E [ ϵ sam 2 ⋅ ∣ B i ∣ ⋅ 1 [ s i ∈ Suit i ] ] ≥ ( 1 − ϵ pr k 10 ) ⋅ ϵ sam 2 ⋅ ∣ B i ∣ \begin{align*}
{\mathbb{E}\left[P_{i} - {\mathbf{P}}_{i+1} \big| \mathbf{H}_{< i}=H_{< i}\right]}
&=
{\mathbb{E}\left[{\mathbb{E}\left[P_{i} - {\mathbf{P}}_{i+1} \big| \mathbf{H}_{< i}^{\text{s}}=H_{< i}^{\text{s}}\right]}\right]} \\
%\Ex{\Ex{P_{i} - \bP_{i+1} \big| \bhist{i}=\hist{i}, \bs_\ell }}
&\ge {\mathbb{E}\left[\frac{\epsilon_{\textnormal{sam}}}{2} \cdot {\left|B_{i} \right|} \cdot
{\mathds{1}\left[s_i \in \texttt{Suit}_i\right]}\right]}\\
&\ge
(1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}}) \cdot \frac{\epsilon_{\textnormal{sam}}}{2} \cdot {\left|B_{i} \right|}
\end{align*} E [ P i − P i + 1 H < i = H < i ] = E [ E [ P i − P i + 1 H < i s = H < i s ] ] ≥ E [ 2 ϵ sam ⋅ ∣ B i ∣ ⋅ 1 [ s i ∈ Suit i ] ] ≥ ( 1 − k 10 ϵ pr ) ⋅ 2 ϵ sam ⋅ ∣ B i ∣ The proof is complete. ◻
Using the above results, this lemma provides a polylogarithmic bound on the number of remaining layers.
Lemma 36. For any ℓ ≥ 1 \ell \ge 1 ℓ ≥ 1 , E [ T − i ∣ H < i = H < i ] ≤ poly ( log ( ∣ E ‾ i ∣ ) , log ( k ) , 1 ϵ ) . \begin{aligned}
{\mathbb{E}\left[{\mathbf{T}}- i \mid \mathbf{H}_{< i}=H_{< i}\right]} \le \textnormal{poly}(\log({\left|\overline{E}_i \right|}), \log(k) , \frac{1}{\epsilon}).
\end{aligned} E [ T − i ∣ H < i = H < i ] ≤ poly ( log ( E i ) , log ( k ) , ϵ 1 ) .
Proof. The elements of E i E_i E i are divided into ⌊ log ( 1 + ϵ ) ( 4 k ϵ ) ⌋ \left\lfloor\,\log_{(1+\epsilon)}(\frac{4k}{\epsilon})\,\right\rfloor ⌊ log ( 1 + ϵ ) ( ϵ 4 k ) ⌋ buckets, and B i B_i B i is the largest one among them. We also know from Lemma 7 that ∣ E ‾ i ∣ ≤ ( 1 + ϵ ins ) ∣ E i ∣ |\overline{E}_i| \leq (1 + \epsilon_{\textnormal{ins}}) |E_i| ∣ E i ∣ ≤ ( 1 + ϵ ins ) ∣ E i ∣ . Therefore,
∣ B i ∣ ≥ ∣ E i ∣ ⌊ log ( 1 + ϵ ) ( 4 k ϵ ) ⌋ ⋅ ∣ E ‾ i ∣ ∣ E i ∣ = ∣ E ‾ i ∣ ⌊ log ( 1 + ϵ ) ( 4 k ϵ ) ⌋ {\left|B_i \right|} \ge \frac{|E_i|}{\left\lfloor\,\log_{(1+\epsilon)}(\frac{4k}{\epsilon})\,\right\rfloor} \cdot \frac{|\overline{E}_i|}{|E_i|} = \frac{|\overline{E}_i|}{\left\lfloor\,\log_{(1+\epsilon)}(\frac{4k}{\epsilon})\,\right\rfloor} ∣ B i ∣ ≥ ⌊ log ( 1 + ϵ ) ( ϵ 4 k ) ⌋ ∣ E i ∣ ⋅ ∣ E i ∣ ∣ E i ∣ = ⌊ log ( 1 + ϵ ) ( ϵ 4 k ) ⌋ ∣ E i ∣ By Lemma 35 , we have
E [ P i − P i + 1 ∣ H < i = H < i ] ≥ ( 1 − ϵ pr k 10 ) ⋅ ϵ sam 2 ⋅ ∣ E ‾ i ∣ ⌊ log ( 1 + ϵ ) ( 4 k ϵ ) ⌋ {\mathbb{E}\left[P_{i} - {\mathbf{P}}_{i+1} \big| \mathbf{H}_{< i}=H_{< i}\right]} \ge (1 - \frac{\epsilon_{\textnormal{pr}}}{k^{10}}) \cdot \frac{\epsilon_{\textnormal{sam}}}{2} \cdot \frac{|\overline{E}_i|}{\left\lfloor\,\log_{(1+\epsilon)}(\frac{4k}{\epsilon})\,\right\rfloor} E [ P i − P i + 1 H < i = H < i ] ≥ ( 1 − k 10 ϵ pr ) ⋅ 2 ϵ sam ⋅ ⌊ log ( 1 + ϵ ) ( ϵ 4 k ) ⌋ ∣ E i ∣ This, the second property of Lemma 31 , and Fact 33 , completes the proof. ◻
We are now ready to bound the expected total number of layers.
Corollary 37. At any point in the stream, the expected number of layers E [ T ] {\mathbb{E}\left[{\mathbf{T}}\right]} E [ T ] is at most poly ( log ( n ) , log ( k ) , 1 ϵ ) \textnormal{poly}(\log(n), \log(k), \frac{1}{\epsilon}) poly ( log ( n ) , log ( k ) , ϵ 1 ) .
Proof. By Lemma 36 , we have
E [ T − 1 ] = E [ T − 1 ∣ H < 1 = H < 1 ] ≤ poly ( log ( n ) , 1 ϵ ) . {\mathbb{E}\left[{\mathbf{T}}- 1\right]} = {\mathbb{E}\left[T - 1 \mid \mathbf{H}_{< 1}=H_{< 1}\right]} \le \textnormal{poly}(\log(n), \frac{1}{\epsilon}). E [ T − 1 ] = E [ T − 1 ∣ H < 1 = H < 1 ] ≤ poly ( log ( n ) , ϵ 1 ) . Howevere note that, the expectation in the result above is over all of the randomness of the algorithm. Yet, since for each update u u u the value of T ) T) T ) after the execution update u u u is independent of the randomness of the algorithm during subsequent updates, the same holds for expectation over the randomness of the algorithm until the execution of u u u finishes. ◻
Given the upper bound on the number of layers, we now compute the query complexity of procedure {\textsc{LayerConstruct}} .
Lemma 38. Suppose the procedure {\textsc{LayerConstruct}}(i) is invoked. The expected number of queries made by calling {\textsc{LayerConstruct}}{}(i) is ∣ E ‾ i ∣ ⋅ poly ( log ( n ) , log ( k ) , 1 ϵ ) |\overline{E}_i| \cdot \textnormal{poly}(\log(n), \log(k), \frac{1}{\epsilon}) ∣ E i ∣ ⋅ poly ( log ( n ) , log ( k ) , ϵ 1 ) , where ∣ E ‾ i ∣ |\overline{E}_i| ∣ E i ∣ refers to the size of E ‾ i \overline{E}_i E i after the update, which is equal to E ^ i \hat{E}_i E ^ i right before executing {\textsc{LayerConstruct}}(i) , and the expectation is over the randomness of algorithm only during the execution of {\textsc{LayerConstruct}}(i) .
Proof. We know that conditioned on history up to level i i i , the expected number of leyers after i i i is polylogarithmic. The number of queries made during {\textsc{EstimateSampleSize}}(j \ge i) is bounded by ∣ E ‾ i ∣ ⋅ poly ( ( log ( n ) , log ( k ) , 1 ϵ ) ) {\left|\overline{E}_i \right|} \cdot \textnormal{poly}((\log(n), \log(k), \frac{1}{\epsilon})) E i ⋅ poly (( log ( n ) , log ( k ) , ϵ 1 )) . Hence, the number of total queries is bounded by ∣ E ‾ i ∣ ⋅ poly ( log ( n ) , log ( k ) , 1 ϵ ) |\overline{E}_i| \cdot \textnormal{poly}(\log(n), \log(k), \frac{1}{\epsilon}) ∣ E i ∣ ⋅ poly ( log ( n ) , log ( k ) , ϵ 1 ) . ◻
Finally, by combining the above results and introducing a charging scheme for the cost, we distribute the cost of each invocation of {\textsc{LayerConstruct}} across updates, thereby bounding the total query complexity of our algorithm per each update.
Theorem 39. The expected amortized update time of our entire algorithm is poly ( log ( n ) , log ( k ) , ϵ − 1 ) \textnormal{poly}(\log(n), \log(k), \epsilon^{-1}) poly ( log ( n ) , log ( k ) , ϵ − 1 ) .
Proof. Each update affects only log ( 4 k ϵ ) \log(\frac{4k}{\epsilon}) log ( ϵ 4 k ) instances of the main Algorithm. Hence, it suffices to bound the number of queries per update for a fixed instance of the Main Algorithm alg:main .
The number of query calls made directly via {\textsc{Insert}}(e) or {\textsc{Delete}}(e) is bounded by T T T , which by Corollary 37 is known to be polylogarithmic.
To upper bound the number of indirect query calls made per update through the procedure {\textsc{LayerConstruct}} , we employ the following charging scheme:
Let’s refer to the number of calls made during the execution of the procedure {\textsc{LayerConstruct}}(\ell) as its cost. Note that this cost also reflects the indirect queries that {\textsc{LayerConstruct}}(\ell) makes through {\textsc{LayerConstruct}}(\ell + 1) . We charge the cost of executing {\textsc{LayerConstruct}}{}(\ell) to all the updates that were responsible for triggering its invocation. In particular, if the procedure {\textsc{Insert}}(e) directly invokes {\textsc{LayerConstruct}}{}(\ell) (not through {\textsc{LayerConstruct}}{}(\ell - 1) ), we spread the cost of {\textsc{LayerConstruct}}{}(\ell) among the updates corresponding to the elements in A ℓ A_\ell A ℓ immediately before its execution. Likewise, if {\textsc{Delete}}(e) directly invokes {\textsc{LayerConstruct}}{}(\ell) , we charge its cost to all updates corresponding to the elements in B ℓ ∩ D B_{\ell} \cap D B ℓ ∩ D immediately before its execution.
For updates u u u and v v v and layer i i i , let Q u , i , v Q_{u, i, v} Q u , i , v denote the cost charged to u u u due to the invocation of {\textsc{LayerConstruct}}(i) during the execution of update v v v . Note that if {\textsc{LayerConstruct}}(i) was not invoked or if it was invoked indirectly through {\textsc{LayerConstruct}}(i - 1) , then Q u , i , v = 0 Q_{u, i, v} = 0 Q u , i , v = 0 .
Consider a fixed u u u and let T u T^u T u denote the number of levels right before update u u u . We have:
E [ Q u , i , v ] = E [ Q u , i , v ∣ Q u , i , v > 0 ] P [ Q u , i , v > 0 ] {\mathbb{E}\left[{\mathbf{Q}}_{u, i, v}\right]}
= {\mathbb{E}\left[{\mathbf{Q}}_{u, i, v} \mid {\mathbf{Q}}_{u, i, v} > 0\right]}{\mathbb{P}\left[{\mathbf{Q}}_{u, i, v} > 0\right]} E [ Q u , i , v ] = E [ Q u , i , v ∣ Q u , i , v > 0 ] P [ Q u , i , v > 0 ] Given Q u , i , v > 0 {\mathbf{Q}}_{u, i, v} > 0 Q u , i , v > 0 , we know that {\textsc{LayerConstruct}}(i) has been invoked during update v v v . By Lemma 38 we know that, the value of Q u , i , v {\mathbf{Q}}_{u, i, v} Q u , i , v is independent of the randomness of the algorithm before the execution of {\textsc{LayerConstruct}}(i) during update v v v and it is bounded by poly ( log ( n ) , log ( k ) , 1 ϵ ) \textnormal{poly}(\log(n), \log(k), \frac{1}{\epsilon}) poly ( log ( n ) , log ( k ) , ϵ 1 ) as the cost of {\textsc{LayerConstruct}}(i) has been spread bacross O ( ∣ E ‾ i ∣ . ϵ − 1 ) O({\left|\overline{E}_i \right|}.\epsilon^{-1}) O ( E i . ϵ − 1 ) different updates. We also note that whether Q u , i , v = 0 {\mathbf{Q}}_{u, i, v} = 0 Q u , i , v = 0 or not can be deterministically determined by the randomness of the algorithm up to starting the execution of update v v v . Therefore, to prove that ∑ i , v E [ Q u , i , v ] \sum_{i, v}{\mathbb{E}\left[{\mathbf{Q}}_{u, i, v} \right]} ∑ i , v E [ Q u , i , v ] is polylogarithmic, it only remains to show that
∑ i , v P [ Q u , i , v > 0 ] ≤ poly ( log ( n ) , log ( k ) , 1 ϵ ) \begin{align}
\sum_{i, v} {\mathbb{P}\left[{\mathbf{Q}}_{u, i, v} > 0 \right]} \le \textnormal{poly}(\log(n), \log(k), \frac{1}{\epsilon}) \tag*{(18)}
\end{align} i , v ∑ P [ Q u , i , v > 0 ] ≤ poly ( log ( n ) , log ( k ) , ϵ 1 ) (18) We know that the element corresponding to update u u u may only be involved in the invocation of {\textsc{LayerConstruct}}(i) during update v v v if update v v v is the first update since receiving update u u u that has caused a direct or indirect invocation of {\textsc{LayerConstruct}}(i) , since A i A_i A i and B i ∩ D B_{i} \cap D B i ∩ D would become empty each time {\textsc{LayerConstruct}}(i) is executed. The same reasoning also implies that Q u , i , v {\mathbf{Q}}_{u, i, v} Q u , i , v cannot be nonzero for any i > T u i > {\mathbf{T}}^u i > T u as the existence of such level can only be due to the execution of {\textsc{LayerConstruct}}(i) during or after update u u u . Therefore, we have:
E [ ∑ i , v 1 [ Q u , i , v > 0 ] ] ≤ E [ T u + 1 ] . {\mathbb{E}\left[\sum_{i, v} {\mathds{1}\left[{\mathbf{Q}}_{u, i, v} > 0\right]} \right]} \le {\mathbb{E}\left[{\mathbf{T}}^{u} + 1\right]}. E [ i , v ∑ 1 [ Q u , i , v > 0 ] ] ≤ E [ T u + 1 ] . Since E [ ∑ i , v 1 [ Q u , i , v > 0 ] ] = ∑ i , v P [ Q u , i , v > 0 ] {\mathbb{E}\left[\sum_{i, v} {\mathds{1}\left[{\mathbf{Q}}_{u, i, v} > 0\right]} \right]} = \sum_{i, v} {\mathbb{P}\left[{\mathbf{Q}}_{u, i, v} > 0 \right]} E [ ∑ i , v 1 [ Q u , i , v > 0 ] ] = ∑ i , v P [ Q u , i , v > 0 ] , Corollary 37 proves inequality (18) and completes the proof. ◻
Omitted proofs
Lemma 40. Given 0 ≤ i < j ≤ T 0 \leq i < j \leq T 0 ≤ i < j ≤ T , we have I ∪ i ⊆ I ∪ j {I^{\cup}}_i \subseteq {I^{\cup}}_j I ∪ i ⊆ I ∪ j .
Proof. We know from Lemma (?) that for all ℓ ∈ [ T ] \ell \in [T] ℓ ∈ [ T ] ,
(I, {I^{\cup}}, \Delta)_{\ell} = {\textsc{Expand}}(S_{\ell}, (I, {I^{\cup}}, \Delta)_{\ell-1}, \tau_{\ell}).
In the {\textsc{Expand}} procedure (Algorithm alg:expand ), the set I ∪ ℓ {I^{\cup}}_\ell I ∪ ℓ is initially set to I ∪ ℓ − 1 {I^{\cup}}_{\ell - 1} I ∪ ℓ − 1 and may be augmented during the sequence of {\textsc{Adjust}} operations on elements in S ℓ S_{\ell} S ℓ . However, no elements are removed from it during this process.
Therefore, we have I ∪ ℓ − 1 ⊆ I ∪ ℓ {I^{\cup}}_{\ell - 1} \subseteq {I^{\cup}}_\ell I ∪ ℓ − 1 ⊆ I ∪ ℓ for all ℓ ∈ [ T ] \ell \in [T] ℓ ∈ [ T ] , and by applying this inductively it follows that I ∪ i ⊆ I ∪ j {I^{\cup}}_i \subseteq {I^{\cup}}_j I ∪ i ⊆ I ∪ j for all 0 ≤ i < j ≤ T 0 \leq i < j \leq T 0 ≤ i < j ≤ T , as desired. ◻
Lemma 41. The family C \mathcal{C} C of circuits of a matroid ( N , I ) (\mathcal{N}, {\mathcal{I}}) ( N , I ) has the following properties:
(C 1 C1 C 1 ) ∅ ∉ C \emptyset \notin \mathcal{C} ∅ ∈ / C .
(C 2 C2 C 2 ) if C 1 C_1 C 1 , C 2 ∈ C C_2 \in \mathcal{C} C 2 ∈ C and C 1 ⊆ C 2 C_1 \subseteq C_2 C 1 ⊆ C 2 , then C 1 = C 2 C_1=C_2 C 1 = C 2 .
(C 3 C3 C 3 ) if C 1 C_1 C 1 , C 2 ∈ C C_2 \in \mathcal{C} C 2 ∈ C , C 1 ≠ C 2 C_1 \neq C_2 C 1 = C 2 and e ∈ C 1 ∩ C 2 e\in C_1 \cap C_2 e ∈ C 1 ∩ C 2 , then there exists C 3 ∈ C C_3 \in \mathcal{C} C 3 ∈ C such that C 3 ⊆ C 1 ∪ C 2 ∖ { e } C_3 \subseteq C_1 \cup C_2 \setminus \{e\} C 3 ⊆ C 1 ∪ C 2 ∖ { e } .
Lemma 42. Let e e e and I I I be an arbitrary element and independent set in M \mathcal{M} M . If I ∪ { e } ∉ I I \cup \{e\} \notin \mathcal{I} I ∪ { e } ∈ / I , then I ∪ { e } I \cup \{e\} I ∪ { e } contains a unique circuit C C C .
Proof. Starting with the dependent set I ∪ { e } I \cup \{e\} I ∪ { e } , one can iteratively remove an element that its removal preserves dependence. Since ∅ ∈ I \emptyset \in \mathcal{I} ∅ ∈ I , this process must terminate with a minimal dependent set, which is, by definition, a circuit. Therefore, there exists at least one circuit C ⊆ I ∪ { e } C \subseteq I \cup \{e\} C ⊆ I ∪ { e } .
Suppose, for contradiction, that there are two distinct circuits C 1 , C 2 ⊆ I ∪ { e } C_1, C_2 \subseteq I \cup \{e\} C 1 , C 2 ⊆ I ∪ { e } with C 1 ≠ C 2 C_1 \neq C_2 C 1 = C 2 . Since I I I is independent, neither C 1 C_1 C 1 nor C 2 C_2 C 2 can be fully contained in I I I . Thus, e ∈ C 1 ∩ C 2 e \in C_1 \cap C_2 e ∈ C 1 ∩ C 2 . By Lemma 41 there exists a circuit C 3 ⊆ ( C 1 ∪ C 2 ) ∖ { e } C_3 \subseteq (C_1 \cup C_2) \setminus \{e\} C 3 ⊆ ( C 1 ∪ C 2 ) ∖ { e } . However, ( C 1 ∪ C 2 ) ∖ { e } ⊆ I (C_1 \cup C_2) \setminus \{e\} \subseteq I ( C 1 ∪ C 2 ) ∖ { e } ⊆ I , implying C 3 ⊆ I C_3 \subseteq I C 3 ⊆ I , which is in contradiction with the independence of I I I .
Therefore, I ∪ { e } I \cup \{e\} I ∪ { e } contains exactly one circuit. ◻
Lemma 43. Let I ∈ I I \in {\mathcal{I}} I ∈ I be an independent set and e e e be an element such that I ∪ { e } ∉ I I \cup \{e\} \notin {\mathcal{I}} I ∪ { e } ∈ / I . Define C : = { e ′ : I + e − e ′ ∈ I } C := \{e': I + e - e' \in {\mathcal{I}}\} C := { e ′ : I + e − e ′ ∈ I } . Let w : I ∪ { e } → R ≥ 0 w : I \cup \{e\} \to \mathbb{R}^{\ge 0} w : I ∪ { e } → R ≥ 0 be an arbitrary weight function and define e ^ : = a r g m a x e ′ ∈ C w ( e ′ ) \hat{e} := \mathop{\mathrm{arg\,max}}_{e'\in C} w(e') e ^ := arg max e ′ ∈ C w ( e ′ ) . The element e ^ \hat{e} e ^ can be found using at most O ( log ( ∣ I ∣ ) ) O(\log(|I|)) O ( log ( ∣ I ∣ )) oracle queries.
Proof. Let e 1 , … , e ∣ I ∣ + 1 e_1, \dots, e_{|I| + 1} e 1 , … , e ∣ I ∣ + 1 denote an ordering of I ∪ { e } I \cup \{e\} I ∪ { e } such that w ( e 1 ) ≥ w ( e 2 ) ⋯ ≥ w ( e ∣ I ∣ + 1 ) w(e_1) \ge w(e_2) \dots \ge w(e_{|I| + 1}) w ( e 1 ) ≥ w ( e 2 ) ⋯ ≥ w ( e ∣ I ∣ + 1 ) . Let i i i denote the smallest index such that { e 1 , … , e i } ∉ I \{e_1, \dots, e_{i}\} \notin {\mathcal{I}} { e 1 , … , e i } ∈ / I . Such an index exists because { e 1 , … , e ∣ I ∣ + 1 } = I ∪ { e } ∉ I \{e_1, \dots, e_{|I| + 1}\} = I \cup \{e\} \notin {\mathcal{I}} { e 1 , … , e ∣ I ∣ + 1 } = I ∪ { e } ∈ / I . We claim that e ^ = e i \hat{e} = e_i e ^ = e i . We note that the element e i e_i e i can be found using a binary search over [ ∣ I ∣ + 1 ] [|I| + 1] [ ∣ I ∣ + 1 ] because for any j j j , if { e 1 , … , e j } ∉ I \{e_1, \dots, e_j\} \notin {\mathcal{I}} { e 1 , … , e j } ∈ / I , then { e 1 , … , e j + 1 } ∉ I \{e_1, \dots, e_{j+1}\} \notin {\mathcal{I}} { e 1 , … , e j + 1 } ∈ / I as well.
To prove this, we first claim that e i ∈ C e_i \in C e i ∈ C . To see why this holds, we first observe that since { e 1 , … , e i − 1 } \{e_1, \dots, e_{i-1}\} { e 1 , … , e i − 1 } is independent but { e 1 , … , e i } \{e_1, \dots, e_i\} { e 1 , … , e i } is not, we have e i ∈ Span ( { e 1 , … , e i − 1 } ) ⊆ Span ( I + e − e i ) e_i \in \texttt{Span}(\{e_1, \dots, e_{i-1}\}) \subseteq \texttt{Span}(I + e - e_i) e i ∈ Span ({ e 1 , … , e i − 1 }) ⊆ Span ( I + e − e i ) . Therefore, since e j ∈ Span ( I + e − e i ) e_j \in \texttt{Span}(I + e - e_i) e j ∈ Span ( I + e − e i ) for all j ≠ i j\ne i j = i , we have I + e ⊆ Span ( I + e − e i ) I + e \subseteq \texttt{Span}(I + e - e_i) I + e ⊆ Span ( I + e − e i ) , which implies
r a n k ( I + e − e i ) ≥ r a n k ( I + e ) ≥ r a n k ( I ) = ∣ I ∣ = ∣ I + e − e i ∣ , \begin{align*}
rank(I + e - e_i) \ge rank(I + e) \ge rank(I) = |I|
= |I+ e - e_i|,
\end{align*} r ank ( I + e − e i ) ≥ r ank ( I + e ) ≥ r ank ( I ) = ∣ I ∣ = ∣ I + e − e i ∣ , which implies I + e − e i ∈ I I + e - e_i \in {\mathcal{I}} I + e − e i ∈ I as claimed.
We need to show that for any e ′ ∈ C e' \in C e ′ ∈ C , we have w ( e i ) ≤ w ( e ′ ) w(e_i) \le w(e') w ( e i ) ≤ w ( e ′ ) . Assume for contradiction that w ( e ′ ) < w ( e i ) w(e') < w(e_i) w ( e ′ ) < w ( e i ) . It follows that e ′ = e j e' = e_j e ′ = e j for some j > i j > i j > i . By definition of C C C , we must have I + e − e j ∈ I I + e - e_j \in {\mathcal{I}} I + e − e j ∈ I , which implies { e 1 , … , e j − 1 } ∈ I \{e_1, \dots, e_{j-1}\} \in{\mathcal{I}} { e 1 , … , e j − 1 } ∈ I . Since i < j i < j i < j , this further implies { e 1 , … , e i } ∈ I \{e_1, \dots, e_i\} \in {\mathcal{I}} { e 1 , … , e i } ∈ I , which is not possible by definition of i i i . ◻