Online Submodular Maximization with Preemption

DOI10.1137/1.9781611973730.80zbMath1371.68328OpenAlexW2952359104MaRDI QIDQ5363102

Niv Buchbinder, Roy Schwartz, Moran Feldman

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.80

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

Related Items (24)

Streaming Algorithms for Submodular Function Maximization ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice ⋮ Streaming algorithms for maximizing DR-submodular functions with \(d\)-knapsack constraints ⋮ Unnamed Item ⋮ The Power of Subsampling in Submodular Maximization ⋮ An optimal streaming algorithm for non-submodular functions maximization on the integer lattice ⋮ Streaming submodular maximization under \(d\)-knapsack constraints ⋮ On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice ⋮ Proportional cost buyback problem with weight bounds ⋮ On maximizing sums of non-monotone submodular and linear functions ⋮ Unnamed Item ⋮ Online algorithms for BP functions maximization ⋮ Buyback problem with discrete concave valuation functions ⋮ Proportional Cost Buyback Problem with Weight Bounds ⋮ Approximating Robust Parameterized Submodular Function Maximization in Large-Scales ⋮ Online BP functions maximization ⋮ Non-submodular streaming maximization with minimum memory and low adaptive complexity ⋮ Relaxing the irrevocability requirement for online graph algorithms ⋮ Non-submodular maximization on massive data streams ⋮ Online Submodular Maximization Problem with Vector Packing Constraint. ⋮ Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice ⋮ Two approximation algorithms for maximizing nonnegative weakly monotonic set functions ⋮ Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice

This page was built for publication: Online Submodular Maximization with Preemption