PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Submodular Maximization with Preemption

Niv Buchbinder, Moran Feldman, Roy Schwartz

arXiv:1501.05801v1cs.DS

TL;DR

Online submodular maximization asks how to maintain a feasible solution as elements arrive sequentially, with preemption allowed. The paper studies unconstrained and cardinality-constrained cases, giving a 1/e-competitive algorithm for the former and constant-competitive guarantees for the latter.

  • Problem

    The problem is to maximize a non-negative submodular function online as elements arrive, while maintaining a feasible solution under the chosen constraint.

    Source: §1 · p. 2

  • Method

    The paper studies adversarial arrivals with preemption in the unconstrained and cardinality-constrained models.

    Source: §1 · p. 2, §1.1 · p. 2

  • Results

    The unconstrained model admits a 1/e-competitive algorithm, and the cardinality-model admits a randomized 56/627 ≈ 0.0893-competitive algorithm plus a deterministic 1/4-approximation for monotone objectives.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    Preemption enables a 1/e guarantee for the unconstrained model, beyond the 1/4 + ε ceiling for algorithms without preemption.

    Source: §1.1 · p. 3

    The estimation error cannot be made dependent on n because the algorithm does not know n when calculating the estimates.

    Source: §3.1 · p. 8

Abstract

from arXiv · show

Submodular function maximization has been studied extensively in recent years under various constraints and models. The problem plays a major role in various disciplines. We study a natural online variant of this problem in which elements arrive one-by-one and the algorithm has to maintain a solution obeying certain constraints at all times. Upon arrival of an element, the algorithm has to decide whether to accept the element into its solution and may preempt previously chosen elements. The goal is to maximize a submodular function over the set of elements in the solution. We study two special cases of this general problem and derive upper and lower bounds on the competitive ratio. Specifically, we design a $1/e$-competitive algorithm for the unconstrained case in which the algorithm may hold any subset of the elements, and constant competitive ratio algorithms for the case where the algorithm may hold at most $k$ elements in its solution.

1 Introduction

The paper studies online submodular maximization, where elements arrive sequentially and accepted elements may be preempted. It gives competitive algorithms and hardness bounds for unconstrained and cardinality-constrained settings.

1 Introduction

  • Elements arrive one at a time, and the algorithm may accept each one or preempt previously accepted elements while maintaining a feasible solution.The model allows adversarial arrivals; without preemption, no constant competitive ratio is possible even under a simple cardinality constraint.Source: §1 · p. 2

1.1 Our Results

  • No-preemption algorithms cannot exceed a 1/4 + ε competitive ratio even for weighted directed cut functions, and cardinality-model algorithms cannot exceed 1/2 + ε.For monotone cardinality objectives, randomized and deterministic algorithms cannot exceed 3/4 + ε and 1/2 + ε, respectively.Source: §1.1 · pp. 3–4
  • A 1/e-competitive algorithm is given for the unconstrained model, while the dicut-model has a polynomial-time 0.438-competitive algorithm.The dicut-model is a special case of the unconstrained model with additional algorithmic power.Source: §1.1 · p. 3
  • 56/627 ≈ 0.0893 is achievable for the cardinality-model; for monotone objectives, a polynomial-time deterministic 1/4-approximation is available.The randomized algorithm can be implemented in polynomial time with an arbitrarily small ε loss in its competitive ratio.Source: §1.1 · p. 3
  • The cardinality-model algorithms can also be implemented in the streaming model, including for general non-negative submodular objectives.The paper also notes that the monotone-objective 1/4 result builds on earlier streaming work.Source: §1.1 · p. 4

1.2 Related Work

  • Prior work gives a 1 − 1/e approximation for monotone submodular maximization under cardinality constraints, while non-monotone results include a 1/e − o(1) approximation.The cited overview also notes a 1/2-approximation algorithm and a polynomial-time hardness bound of 0.491 for unconstrained non-monotone maximization.Source: §1.2 · pp. 4–5

2 Preliminaries

The preliminaries define an online process over a down-monotone family of feasible sets. After each arrival, the algorithm may choose any feasible subset of its previous solution together with the new element.

2 Preliminaries

  • The instance has an unknown ground set, a non-negative submodular objective, and a down-monotone family of feasible sets.The algorithm creates feasible solutions S0 through Sn, with S0 equal to the empty set.Source: §2 · p. 5
  • Down-monotonicity means every subset of a feasible set is also feasible.If A is a subset of B and B is feasible, then A is feasible.Source: §2 · p. 5
  • After each element arrives, the algorithm may choose any feasible subset of its previous solution together with that element; the total number of arrivals is unknown in advance.The input may end after any element from the algorithm’s perspective.Source: §2 · p. 6

3 The unconstrained-model and the dicut-model

The section gives competitive algorithms for the unconstrained and dicut models, then proves lower bounds for dicut algorithms using adversarially revealed graph instances. The guarantees are 1/e and 0.483, while the dicut lower bounds differ for deterministic and randomized algorithms.

3.1 Algorithms for the unconstrained-model and the dicut-model

  • Marginal Choice sets each element's inclusion threshold where its marginal derivative along the uniform vector changes sign, then includes elements independently with probability y_u.The expected value of the final set is F(y).Source: §3.1 · pp. 6–7
  • The unconstrained-model algorithm achieves a competitive ratio of at least 1/e.The analysis bounds the expected value of its final solution against the optimum.Source: §3.1 · pp. 7–8
  • Degrees Ratio Choice achieves a competitive ratio of at least 0.483, using a function h independent of G and computable in constant time.The result follows by matching the algorithm's vector to the vector in the guarantee for F(y).Source: §3.1 · p. 9

3.2 Hardness results for the dicut-model

  • For the dicut lower bounds, an adversary fixes a graph and iteratively reveals nodes based on algorithm decisions or, for randomized algorithms, their probabilities.The hard instance uses the nodes revealed by the adversary, in the same order.Source: §3.2 · p. 10
  • No deterministic dicut-model algorithm has competitive ratio better than (5 - sqrt(17))/2.The proof constructs a fixed weighted graph and adaptively reveals its nodes based on the algorithm's decisions.Source: §3.2 · p. 10
  • No randomized dicut-model algorithm has competitive ratio better than 4/5.The adversary first reveals u1 and u2, then may reveal w1 based on the algorithm's probabilities.Source: §3.2 · p. 11

4 The cardinality-model

The cardinality-model section develops algorithms for monotone and general submodular objectives, then establishes limits on achievable competitive ratios. Its positive results include a randomized guarantee for the general case and a 1/4 guarantee for monotone objectives; its hardness results rule out stronger ratios in stated settings.

4.1 Algorithms for the cardinality-model

  • 1/4 is the competitive ratio of the monotone-objective algorithm, which starts by accepting k elements and then makes threshold-qualified swaps.The parameterized guarantee is at least c/(c+1)^2; c = 1 gives 1/4.Source: §4.1 · pp. 12–13
  • 56/627 is the guarantee for the general cardinality-model algorithm after rounding, with polynomial-time implementation available at an arbitrarily small ε loss.The analysis uses c = 7/4 and p = 3; rounding converts the modified algorithm's guarantee into a feasible online solution.Source: §4.1 · pp. 14–16
  • Online rounding selects one random place from each block of p positions, yielding a feasible cardinality-model solution whose expected value is at least g(S_n).The modified algorithm analyzes g(S_n), and Lemma 4.10 relates that value to the rounded solution.Source: §4.1 · p. 15

4.2 Hardness results for the cardinality-model

  • For monotone objectives, no deterministic algorithm can exceed 1/2 + ε, and no randomized algorithm can exceed 3/4 + ε in the cardinality-model.For general objectives, no online algorithm can exceed 1/2 + ε.Source: §4.2 · pp. 16–17

A Proof of Theorem 1.1

This proof rules out a no-preemption algorithm with competitive ratio 1/4 + ε, even for weighted directed-graph cut functions. An adversary constructs the instance online, using a potential argument to contradict the assumed guarantee.

A Proof of Theorem 1.1

  • An adversary proves that no algorithm without preemption can be (1/4 + ε)-competitive, even when the objective is a weighted directed-graph cut function.The proof assumes such an algorithm exists and constructs an instance with a ground-set size depending on ε.Source: A Proof of Theorem 1.1 · p. 21
  • The adversary chooses each revealed element's outgoing arcs based on the algorithm's behavior so far, defining the objective as the resulting graph's weighted cut function.Queries made before an element arrives do not depend on that element's outgoing arc set.Source: A Proof of Theorem 1.1 · p. 21
  • The adversary never switches from mode A to mode B: switching would leave the algorithm's cut below (1/4 + ε/2) times an available single-element optimum.In mode A, revealed elements have arcs to previously revealed elements; in mode B, they have no exiting arcs.Source: A Proof of Theorem 1.1 · pp. 21–22
  • A potential Φ decreases by at least ε/(4i) per step, forcing Φ(n) ≤ Φ(n0) − 2 and contradicting its range [0, 1].The bound follows from the per-step inequality and Corollary A.4.Source: A Proof of Theorem 1.1 · p. 23

B A Polynomial Time Implementation of Algorithm 1

Algorithm 5 gives a polynomial-time implementation of Algorithm 1 for the unconstrained model, with competitive ratio at least e^-1 - ε. It estimates marginal values from samples and uses estimated marginal thresholds to determine element inclusion.

B A Polynomial Time Implementation of Algorithm 1

C A Polynomial Time Implementation of Algorithm 3 for the Objective g(S)

Algorithm 6 is a polynomial-time implementation of Algorithm 3 for the objective g(S). With c = 7/4 and p = 3, it guarantees g(S_n) ≥ (56/627 − ε) · f(OPT).

C A Polynomial Time Implementation of Algorithm 3 for the Objective g(S)

Loading 1501.05801v1…