Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
From MaRDI portal
Publication:5454254
DOI10.1137/S0097539705447372zbMath1135.68019WikidataQ29030121 ScholiaQ29030121MaRDI QIDQ5454254
Guy Kindler, Subhash A. Khot, Elchanan Mossel, 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
Three candidate plurality is stablest for small correlations, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Biased halfspaces, noise sensitivity, and local Chernoff inequalities, THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND, Cones of multipowers and combinatorial optimization problems, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Coreness of cooperative games with truncated submodular profit functions, Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, Approximating the Noise Sensitivity of a Monotone Boolean Function, Unnamed Item, A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis, Pseudorandom sets in Grassmann graph have near-perfect expansion, Max-Cut via Kuramoto-Type Oscillators, On the complexity of binary polynomial optimization over acyclic hypergraphs, Recent Theoretical Advances in Non-Convex Optimization, Proof Complexity Meets Algebra, Unnamed Item, Query-Efficient Dictatorship Testing with Perfect Completeness, Unnamed Item, Unnamed Item, Online Submodular Maximization with Preemption, Fundamental Domains for Symmetric Optimization: Construction and Search, The Quest for Strong Inapproximability Results with Perfect Completeness, Disordered systems insights on computational hardness, Fast Distributed Approximation for Max-Cut, Constrained Assortment Optimization Under the Paired Combinatorial Logit Model, Probabilistic view of voting, paradoxes, and manipulation, Half-Spaces with Influential Variable, Constrained Submodular Maximization via a Nonsymmetric Technique, ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network, Approximation Algorithms for CSPs, Approximating Unique Games Using Low Diameter Graph Decomposition, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, Parameterized Complexity of Multi-Node Hubs, Computational topology and the Unique Games Conjecture, Dimension Reduction for Polynomials over Gaussian Space and Applications, Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem, UG-hardness to NP-hardness by losing half, A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints, Simultaneous max-cut is harder to approximate than max-cut, 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, Boolean functions: influence, threshold and noise, Gaussian noise sensitivity and Fourier tails, Towards a characterization of constant-factor approximable finite-valued CSPs, Minimizing worst-case and average-case makespan over scenarios, Affine reductions for LPs and SDPs, Simple approximation algorithms for balanced MAX~2SAT, Maximally stable Gaussian partitions with discrete applications, Complexity and approximation of finding the longest vector sum, \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel, Approximating graph-constrained max-cut, A priori TSP in the scenario model, Noise correlation bounds for uniform low degree functions, Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds, Approximation algorithms for balancing signed graphs, The structure of Gaussian minimal bubbles, Parameterized complexity of multi-node hubs, Classical symmetries and the quantum approximate optimization algorithm, Empirical performance bounds for quantum approximate optimization, A tight \(\sqrt{2} \)-approximation for linear 3-cut, Towards a proof of the Fourier-entropy conjecture?, Approximating max-cut under graph-MSO constraints, Gaussian bounds for noise correlation of resilient functions, Approximation algorithms for connected maximum cut and related problems, Complexity results on planar multifacility location problems with forbidden regions, Hypergraph cuts above the average, 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 \), From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, Pricing loss leaders can be hard, Column subset selection problem is UG-hard, Computing the largest bond and the maximum connected cut of a graph, Low correlation noise stability of symmetric sets, Hypercontractivity via tensor calculus, 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
