scientific article; zbMATH DE number 7053285

zbMath1422.68312arXiv1110.1064MaRDI QIDQ5743406

Ning Tan, Prasad Raghavendra

Publication date: 10 May 2019

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix, Quantum de Finetti theorems under local measurements with applications, Simultaneous Approximation of Constraint Satisfaction Problems, On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy, Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials, Complexity of approximating CSP with balance/hard constraints, Information-theoretic thresholds from the cavity method, An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding, Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation, A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis, Computing densest \(k\)-subgraph with structural parameters, Lower tails via relative entropy, Unnamed Item, Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems, Bethe states of random factor graphs, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance, Unnamed Item, Product-state approximations to quantum states, Lift-and-project methods for set cover and knapsack, A bounded-error quantum polynomial-time algorithm for two graph bisection problems, Sherali-adams strikes back, The Cut Metric for Probability Distributions, A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies, The rank of sparse random matrices, Speeding up a memetic algorithm for the max-bisection problem, An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Maximally stable Gaussian partitions with discrete applications
• Graph expansion and the unique games conjecture
• A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Gadgets, Approximation, and Linear Programming
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• SDP Integrality Gaps with Local ell_1-Embeddability
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• How to Round Any CSP
• CSP gaps and reductions in the lasserre hierarchy
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• The RPR2 rounding technique for semidefinite programs
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• Expander flows, geometric embeddings and graph partitioning