Symmetry and Approximability of Submodular Maximization Problems

DOI10.1109/FOCS.2009.24MaRDI QIDQ5171225zbMATH OpenFDO

Authors Jan Vondrák

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2009.24

Mathematics Subject Classification ID

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

Cited in

(14)

• A note on the minimization of symmetric and general submodular functions
• Non-monotone submodular function maximization under k-system constraint
• Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
• Inequalities on submodular functions via term rewriting
• Limitations of randomized mechanisms for combinatorial auctions
• Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
• Submodular Cost Allocation Problem and Applications
• Improved competitive ratios for submodular secretary problems (extended abstract)
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Sell or hold: A simple two-stage stochastic combinatorial optimization problem
• Submodular functions: learnability, structure, and optimization
• A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
• Submodular functions are noise stable
• Correlated stochastic knapsack with a submodular objective

This page was built for publication: Symmetry and Approximability of Submodular Maximization Problems

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