Optimal approximation for submodular and supermodular optimization with bounded curvature

DOI10.1137/1.9781611973730.76MaRDI QIDQ6829534zbMATH OpenFDO

Authors Maxim Sviridenko, Jan Vondrák, Justin Ward

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 http://qmro.qmul.ac.uk/xmlui/handle/123456789/25585

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Cited in

(4)

• Submodular + supermodular function maximization with knapsack constraint
• Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
• Maximizing the difference of DR-submodular function on the integer lattice
• Budget and profit approximations for spanning tree interdiction

This page was built for publication: Optimal approximation for submodular and supermodular optimization with bounded curvature

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6829534)