Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
From MaRDI portal
Publication:5495027
DOI10.1109/FOCS.2011.36zbMath1292.90222MaRDI QIDQ5495027
Ali Kemal Sinop, Venkatesan Guruswami
Publication date: 30 July 2014
Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)
Integer programming (90C10) Quadratic programming (90C20) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (22)
Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ Simultaneous Approximation of Constraint Satisfaction Problems ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ On semidefinite programming bounds for graph bandwidth ⋮ New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover ⋮ A unified view of graph regularity via matrix decompositions ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Unnamed Item ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Graph Clustering using Effective Resistance ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks ⋮ Lift-and-project methods for set cover and knapsack ⋮ Optimal Column-Based Low-Rank Matrix Reconstruction ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
