Symmetry and Approximability of Submodular Maximization Problems
From MaRDI portal
Publication:5171225
DOI10.1109/FOCS.2009.24zbMath1292.90262MaRDI QIDQ5171225
Publication date: 25 July 2014
Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)
Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (13)
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ Sell or hold: A simple two-stage stochastic combinatorial optimization problem ⋮ Inequalities on submodular functions via term rewriting ⋮ Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm ⋮ Submodular Cost Allocation Problem and Applications ⋮ Maximizing a submodular function with viability constraints ⋮ Non-monotone submodular function maximization under \(k\)-system constraint ⋮ Limitations of randomized mechanisms for combinatorial auctions ⋮ Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract) ⋮ A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints ⋮ Unnamed Item
This page was built for publication: Symmetry and Approximability of Submodular Maximization Problems
