Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

DOI10.1287/moor.2016.0842zbMath1386.90129arXiv1311.4728MaRDI QIDQ4595963

Jan Vondrák, M. I. Sviridenko, Justin Ward

Publication date: 7 December 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/1311.4728

zbMATH Keywords

curvature; local search; matroids; submodular maximization; maximum entropy sampling; continuous greedy; supermodular minimization; column-subset selection

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68W25: Approximation algorithms