scientific article; zbMATH DE number 7053286
Publication:5743407
zbMath1423.68202arXiv1110.1360MaRDI QIDQ5743407
Yuan Zhou, Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1110.1360
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (19)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Global Optimization with Polynomials and the Problem of Moments
- Convex Relaxations and Integrality Gaps
- Public-key cryptography from different assumptions
- Detecting high log-densities
- Graph expansion and the unique games conjecture
- Local Global Tradeoffs in Metric Embeddings
- A PCP characterization of NP with optimal amortized query complexity
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Relations between average case complexity and approximation complexity
- Local versus global properties of metric spaces
- Optimal Sherali-Adams Gaps from Pairwise Independence
- Cones of Matrices and Set-Functions and 0–1 Optimization
- SDP Integrality Gaps with Local ell_1-Embeddability
- Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
- Integrality gaps for Sherali-Adams relaxations
- CSP gaps and reductions in the lasserre hierarchy
- Gowers Uniformity, Influence of Variables, and PCPs
- Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems
- Probability Inequalities for Sums of Bounded Random Variables
- Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- The dense \(k\)-subgraph problem
This page was built for publication: