Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization

DOI10.1137/1.9781611973730.77zbMath1372.68283arXiv1410.0773OpenAlexW2952201503MaRDI QIDQ5363100

Roy Schwartz, Moran Feldman, Niv Buchbinder

Publication date: 5 October 2017

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

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

zbMATH Keywords

approximation algorithmmatroidsubmodular maximization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Structured Robust Submodular Maximization: Offline and Online Algorithms, The Power of Subsampling in Submodular Maximization, Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid, Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time, Unnamed Item, Online submodular maximization: beating 1/2 made simple, Guess free maximization of submodular and linear sums, An almost optimal approximation algorithm for monotone submodular multiple knapsack