Symmetry and Approximability of Submodular Maximization Problems
From MaRDI portal
Publication:2839179
DOI10.1137/110832318zbMath1292.90261arXiv1110.4860OpenAlexW2038938388MaRDI QIDQ2839179
Publication date: 4 July 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.4860
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 (23)
The Limitations of Optimization from Samples ⋮ Streaming Algorithms for Submodular Function Maximization ⋮ Maximizing Symmetric Submodular Functions ⋮ Measured continuous greedy with differential privacy ⋮ Robust Monotone Submodular Function Maximization ⋮ Unnamed Item ⋮ The Power of Subsampling in Submodular Maximization ⋮ Online risk-averse submodular maximization ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ On maximizing sums of non-monotone submodular and linear functions ⋮ Unnamed Item ⋮ Submodular Optimization with Contention Resolution Extensions. ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ Weakly Submodular Function Maximization Using Local Submodularity Ratio. ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ Robust monotone submodular function maximization ⋮ Online Submodular Maximization with Preemption ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ Approximation algorithms for vertex happiness ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
This page was built for publication: Symmetry and Approximability of Submodular Maximization Problems
