scientific article; zbMATH DE number 7053286

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.

Mathematics Subject Classification ID

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

BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints, On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy, Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, Finding a collective set of items: from proportional multirepresentation to group recommendation, Finding connected \(k\)-subgraphs with high density, On the approximability of the minimum rainbow subgraph problem and other related problems, An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem, Orienteering for electioneering, Sum of Squares Bounds for the Empty Integral Hull Problem, Sum-of-squares hierarchy lower bounds for symmetric formulations, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Unnamed Item, Unnamed Item, Approximation and hardness of shift-Bribery, Testing for Dense Subsets in a Graph via the Partition Function, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, An approximation algorithm for network flow interdiction with unit costs and two capacities, Superlinear Integrality Gaps for the Minimum Majority Problem, An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item