Online submodular maximization with preemption
From MaRDI portal
Abstract: 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 -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 elements in its solution.
Recommendations
Cites work
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- A threshold of ln n for approximating set cover
- A tight linear time (1/2)-approximation for unconstrained submodular maximization
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- An 0. 828-approximation algorithm for the uncapacitated facility location problem
- An analysis of approximations for maximizing submodular set functions—I
- An efficient approximation for the generalized assignment problem
- Approximating the least core value and least core of cooperative games with supermodular costs
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization
- Buyback problem -- approximate matroid intersection with cancellation costs
- Combinatorial approximation algorithms for the maximum directed cut problem
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- Gadgets, Approximation, and Linear Programming
- scientific article; zbMATH DE number 3559283 (Why is no real title available?)
- scientific article; zbMATH DE number 1305386 (Why is no real title available?)
- scientific article; zbMATH DE number 7051298 (Why is no real title available?)
- scientific article; zbMATH DE number 2086630 (Why is no real title available?)
- scientific article; zbMATH DE number 2086914 (Why is no real title available?)
- scientific article; zbMATH DE number 1833408 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved bounds for randomized preemptive online matching
- Improved competitive ratios for submodular secretary problems (extended abstract)
- Lower and upper bounds on FIFO buffer management in QoS switches
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing Non-monotone Submodular Functions
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Noise stability of functions with low influences: invariance and optimality
- Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
- Oblivious algorithms for the maximum directed cut problem
- Online maximum directed cut
- Online scheduling with preemption or non-completion penalties
- Online unweighted knapsack problem with removal cost
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Reducibility among combinatorial problems
- Revenue submodularity
- Some optimal inapproximability results
- Submodular Max-SAT
- Submodular maximization by simulated annealing
- Submodular maximization with cardinality constraints
- Submodular secretary problem and extensions
- Symmetry and approximability of submodular maximization problems
- Tight approximation algorithms for maximum general assignment problems
Cited in
(22)- Online budgeted maximum coverage
- Online multistage subset maximization problems
- Online algorithms for the maximum \(k\)-interval coverage problem
- A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions
- Online algorithms for BP functions maximization
- Online risk-averse submodular maximization
- Submodular maximization over data streams with differential privacy noise
- Online prediction under submodular constraints
- Online Submodular Maximization with Free Disposal
- scientific article; zbMATH DE number 7525448 (Why is no real title available?)
- Online Submodular Maximization Problem with Vector Packing Constraint.
- Online submodular maximization with preemption
- Online submodular minimization
- An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
- Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions
- Efficient algorithms for k-submodular function maximization with p-system and d-knapsack constraint
- Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
- Optimal streaming algorithms for submodular maximization with cardinality constraints
- On maximizing k-submodular functions under p-system and d-knapsack constraints
- Separating coverage and submodular: maximization subject to a cardinality constraint
- Dynamic algorithms for submodular maximization with a p-matchoid constraint
- Online happiness maximization queries
This page was built for publication: Online submodular maximization with preemption
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972676)
