Online Submodular Maximization with Preemption

By Niv Buchbinder, Moran Feldman, Roy Schwartz. 2015

128 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Information-theoretic Online Memory Selection for Continual Learning (2022, neutral): “Online submodular maximization (Buchbinder et al., 2014; Lavania et al., 2021) selects a memory buffer online to maximize a submodular criterion.”
Streaming Weak Submodularity: Interpreting Neural Networks on the Fly (2017, background): “Thus, a natural question is whether recent results on streaming algorithms for maximizing submodular functions [Badanidiyuru et al., 2014; Buchbinder et al., 2015; Chekuri et al., 2015] extend to the weakly submodular setting.”
A Practical Online Framework for Extracting Running Video Summaries under a Fixed Memory Budget (2021, methodology): “Buchbinder et al. [2] suggest setting the threshold for each given time t as C f ( S t ) K , where C is a constant.”
Very Fast Streaming Submodular Function Maximization (2020, methodology): “PremptionStreaming has the following properties (Buchbinder et al., 2019):”