Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
From MaRDI portal
Publication:5454254
DOI10.1137/S0097539705447372zbMath1135.68019WikidataQ29030121 ScholiaQ29030121MaRDI QIDQ5454254
Elchanan Mossel, Subhash A. Khot, Guy Kindler, Ryan O'Donnell
Publication date: 28 March 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Query-Efficient Dictatorship Testing with Perfect Completeness, THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND, Cones of multipowers and combinatorial optimization problems, Improved approximation for orienting mixed graphs, Bounds on 2-query locally testable codes with affine tests, Standard simplices and pluralities are not the most noise stable, Complexity of approximating CSP with balance/hard constraints, Sparse approximation is provably hard under coherent dictionaries, Solution of the propeller conjecture in \(\mathbb R^3\), On judicious bisections of graphs, Angular synchronization by eigenvectors and semidefinite programming, The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions, Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope, Hard constraint satisfaction problems have hard gaps at location 1, PCPs via the low-degree long code and hardness for constrained hypergraph coloring, Noise stability of functions with low influences: invariance and optimality, Gaussian noise sensitivity and Fourier tails, Minimizing worst-case and average-case makespan over scenarios, Simple approximation algorithms for balanced MAX~2SAT, Maximally stable Gaussian partitions with discrete applications, Noise correlation bounds for uniform low degree functions, Approximation algorithms for connected maximum cut and related problems, Oblivious algorithms for the maximum directed cut problem, Speeding up a memetic algorithm for the max-bisection problem, Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix, Gaussian bounds for noise correlation of functions, On the approximability of digraph ordering, Large cuts with local algorithms on triangle-free graphs, Inapproximability ratios for crossing number, The maximum cut problem on blow-ups of multiprojective spaces, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Pricing loss leaders can be hard, Column subset selection problem is UG-hard, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Relaxations of Combinatorial Problems Via Association Schemes, Robustly Solvable Constraint Satisfaction Problems, Some applications of hypercontractive inequalities in quantum information theory, Grothendieck-Type Inequalities in Combinatorial Optimization, Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes, A priori TSP in the Scenario Model, On Khot’s unique games conjecture, Minimum Cell Connection in Line Segment Arrangements, Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, Max-Cut Under Graph Constraints, Approximability Distance in the Space of H-Colourability Problems, Approximate Kernel Clustering, Approximating CSPs Using LP Relaxation, Approximation Limits of Linear Programs (Beyond Hierarchies), Making the Long Code Shorter, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
Uses Software
