Robust Algorithms under Adversarial Injections

1 Introduction

• Random-order algorithms can rely on early samples or representative fixed partitions, making them sensitive to noise and motivating the search for guarantees robust to input distortions.The introduction highlights these techniques as vulnerable when the random-order assumption is weakened.Source: §1 · pp. 2–3

1.1 The Adversarial Injections Model

• In the adversarial-injections model, an adversary chooses elements and their order, then good elements are uniformly randomly permuted among themselves; algorithms are evaluated against the optimum on good elements.Equivalently, the adversary injects elements at chosen positions without knowing the original stream’s random permutation.Source: §1.1 · p. 3

1.2 Related Models

• Unlike entropy-based or stochastic/adversarial hybrid models [21], [8], the Byzantine model [3] exposes timestamps, whereas adversarial injections withholds them and is strictly harder, including for online bipartite matching [16].The paper says the Byzantine model still permits early-sample and partitioning techniques that adversarial injections is designed to prevent.Source: §1.2 · pp. 3–4

1.3 Our Results

• 1/2 + γ approximation in expectation is achievable for maximum matching under adversarial injections with a semi-streaming algorithm.Here γ > 0 is an absolute constant.Source: §1.3 · p. 5
• No adversarial-injections online algorithm achieves competitive ratio 1/2 + ε for any ε > 0, even for bipartite matching.The paper notes that the construction proving Theorem 3 in [14] also implies this hardness.Source: §1.3 · p. 5

2.1 Streaming Setting

• The streaming algorithm improves on the trivial 1/2 approximation by making the greedy approach robust to adversarial injections.The section establishes that the greedy algorithm can achieve a constant improvement over 1/2.Source: §2.1 · p. 7

2.1.1 The Algorithm

• Match runs two algorithms in parallel and returns the better output: a greedy maximal matching and a greedy matching stopped at |M*|(1/2 − ε), then augmented along 3-augmenting paths.The algorithm assumes |M*| is known; geometric guessing removes this assumption at an arbitrarily small loss in approximation ratio.Source: §2.1.1 · p. 7

2.1.2 Overview of the Analysis

• The analysis uses the first constant fraction of Eopt: either the greedy matching is near 1/2 and can be augmented, or it yields a constant improvement over |M*|/2.The two cases depend on the order of Eopt, so the proof shows greedy is robust to small stream changes: its early solution is large for all permutations or small for all permutations.Source: §2.1.2 · pp. 7–8

2.2 Online Setting

• The competitive ratio of 1/2 is optimal online, even for bipartite graphs, as the construction from [14] also works under adversarial injections.The construction forces an algorithm to take edges outside the optimum before the final round, when optimal-matching edges arrive; their internal order does not affect the proof.Source: §2.2 · p. 8

3.2 The Algorithm

• The algorithm maintains a height-at-most-k tree, adding a child for each new distinct marginal increase at a node, then returns the best leaf.Nodes represent partial solutions; retaining only one child per increase limits the number of children to |I|.Source: §3.2 · p. 9

3.3 Overview of the Analysis

• The analysis selects a leaf using a strategy the algorithm need not compute and that may rely on Eopt and Enoise; the tree algorithm is 1/2-approximate even under adversarial order.The main proof uses a more involved leaf-selection strategy to combine two approaches.Source: §3.3 · pp. 9–11

3.4 Analysis

• The recurrence analysis sets t = 0.8 and proves the lower bound for every positive k.The recurrence bounds the expected value of the selected solution relative to OPT.Source: §3.4 · pp. 12–13
• 0.5506: with t = 0.8, the analysis proves R(k, k) ≥ 0.5506 for every positive k, yielding a 0.55-approximation.The recurrence lower-bounds the expected value of the analyzed solution relative to OPT.Source: §3.4 · pp. 12–13

4 Conclusion and Open Problems

• The adversarial-injections model aims to eliminate algorithms that overfit to random-order streams while remaining easier than adversarial-order streams.The paper studies matching and cardinality-constrained monotone submodular maximization in this model.Source: §4 · p. 13
• Streaming unweighted matching beats 1/2, while the paper observes that online matching cannot beat 1/2 [14], separating the two settings.Source: §4 · p. 14
• For cardinality-constrained monotone submodular maximization, the algorithm achieves a 0.55 approximation using huge memory independent of universe size n.Open questions ask whether n-independent memory can achieve 1 - 1/e and whether this algorithm does; [29] achieves 1/2 + ε for very small ε with poly(k) elements, raising the question of whether poly(k) space can significantly beat 1/2 or reach 1 - 1/e.Source: §4 · p. 14

A Analysis of the streaming algorithm for maximum matching

• Match runs greedy and a second algorithm that switches from greedy to collecting 3-augmenting paths, then outputs the better solution.The second algorithm's initial greedy stage is Phase 1.Source: A Analysis of the streaming algorithm… · p. 16
• M* denotes a maximum matching, while M1 is updated by the first algorithm and M2 is produced by the second.Source: A Analysis of the streaming algorithm… · p. 16
• M(1)2 denotes the second algorithm's matching immediately after Phase 1 ends.Source: A Analysis of the streaming algorithm… · p. 16

A.1 Removing assumption that |M ∗| is known

• Parallel copies use powers of 1 + δ to guess |M*| within a factor of 1 + δ from |M1|, with copies started or stopped as their estimates become invalid.|M1| is a lower bound on |M*|; new copies initialize with the current matching M1.Source: §A.1 · p. 16

• Match achieves an expected approximation ratio of at least 1/2 + γ for some fixed γ > 0.Source: §A.2 · p. 16
• Deleting one edge from a stream changes the size of the greedy matching by at most 1.The proof argues that the symmetric difference has at most one nonzero-length alternating path, which must contain the deleted edge.Source: §A.2 · pp. 16–17
• When the greedy prefix matching is large, the proof uses 3-augmenting paths in the remaining stream to improve it.The analysis counts many augmentable edges, accounts for paths disrupted by prefix edges, and applies the algorithm's path-finding phases.Source: §A.2 · pp. 17–18
• When some permutation gives a low greedy prefix matching, stream robustness yields a lower bound on greedy's expected selection of optimum edges.The proof uses the at-most-1 matching-size change under a single deletion to bound changes across prefixes; each unarrived optimum edge is selected with probability at least 2ε − 4k/|M*|.Source: §A.2 · p. 18

B Omitted proofs for submodular function maximization

• The algorithm returns the best leaf in a tree of height at most k, where each root-to-node path represents a solution.The root initially stores the empty set, and nodes correspond to solutions with as many elements as their height.Source: B Omitted proofs for submodular… · p. 19
• An arriving element becomes a child of a node only if no existing child has the same marginal value for that node’s path solution.Each node has at most |I| children, where I is the set of possible increments.Source: B Omitted proofs for submodular… · p. 19
• The algorithm chooses an increment set I of size O(k), initially assuming OPT is known; it removes that assumption with a small increase in space.Source: B Omitted proofs for submodular… · p. 19

B.1 Assumption that OPT is known

• For any guess g ≤ OPT, the algorithm returns value at least 0.5506g; a guess with g ≤ OPT ≤ (1 + δ)g loses at most a factor of (1 + δ) in approximation.The algorithm runs in parallel for multiple guesses to avoid requiring OPT in advance.Source: §B.1 · p. 19
• As the stream advances, guesses are adapted using the maximum observed element, and newly added guesses start executions from the current stream position.Any subset of at most k elements among the first i stream elements has value between m_i and k · m_i.Source: §B.1 · p. 19
• The correct guess remains available, and elements of the optimum arriving before its execution starts contribute at most gδ in value.Removing that early-arriving subset bounds the loss from late initialization.Source: §B.1 · p. 19

B.2 Bounding the number of increases

• Because the tree algorithm stores roughly |I|k elements, bounding |I| by O(k) keeps the number of possible increases small and limits memory use.I is the set of increases f(e | S) for S ⊆ E with |S| < k and e ∈ E.Source: §B.2 · pp. 19–20
• With OPT known, the method divides the range from 0 to OPT into k/δ buckets, each of size δ·OPT/k.Each bucket represents a range of possible increases of f.Source: §B.2 · p. 20
• k·O(δ/k) OPT bounds the expected-value loss from bucketing, which can be made arbitrarily small by choosing δ > 0 appropriately.Each selected element may differ in value by at most OPT·δ/k from the value promised by the analysis, and the recursion has depth k.Source: §B.2 · p. 20

B.3 Analysis of recursion function

• The proof’s key simplification is that, for a threshold t and sufficiently large k, the minimum of three recursion terms reduces to the first term.This reduction is the basis for lower-bounding R(k,h), which measures the solution’s approximation ratio against OPT over submodular functions, streams, and optimal elements.Source: §B.3 · p. 20
• For t = 0.8, k ≥ 1000, and h ≤ k, Lemma 11 establishes that the recursion follows its first rule, so Claim 10’s closed form applies.When the first rule applies through height h, Claim 10 gives R(k,h) = 1 − (1 − t/k)^h.Source: §B.3 · p. 21
• R(k,k) ≥ 0.5506 for every positive integer k, giving the recursion’s lower bound used to establish the algorithm’s 0.55 competitiveness.For k > 1000, the proof uses Lemma 11 and Claim 10; for k ≤ 1000, it reports computer-assisted verification.Source: §B.3 · pp. 24–25