Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids

DOI10.1137/1.9781611974782.78zbMath1409.68339arXiv1610.07770OpenAlexW2952790532MaRDI QIDQ4575820

No author found.

Publication date: 16 July 2018

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

Full work available at URL: https://arxiv.org/abs/1610.07770

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (6)

Non-submodular streaming maximization with minimum memory and low adaptive complexity ⋮ Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ Online Submodular Maximization Problem with Vector Packing Constraint. ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

This page was built for publication: Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids