Improved inapproximability for submodular maximization

DOI10.1007/978-3-642-15369-3_2MaRDI QIDQ3588396zbMATH OpenOpenAlexFDO

Authors Per Austrin

Publication date 10 September 2010

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.3777

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27)

Abstract: We show that it is Unique Games-hard to approximate the maximum of a submodular function to within a factor 0.695, and that it is Unique Games-hard to approximate the maximum of a symmetric submodular function to within a factor 0.739. These results slightly improve previous results by Feige, Mirrokni and Vondr'ak (FOCS 2007) who showed that these problems are NP-hard to approximate to within $3/4+epsilonapprox0.750$ and $5/6+epsilonapprox0.833$, respectively.

Recommendations

• Symmetry and approximability of submodular maximization problems
• Maximizing Non-monotone Submodular Functions
• Submodular Max-SAT
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Submodular maximization by simulated annealing

Cited in

(4)

• Symmetry and approximability of submodular maximization problems
• Hardness of submodular cost allocation: lattice matching and a simplex coloring conjecture
• Simultaneous approximation of multi-criteria submodular function maximization
• From query complexity to computational complexity

This page was built for publication: Improved inapproximability for submodular maximization

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