Handelman's hierarchy for the maximum stable set problem

DOI10.1007/s10898-013-0123-5zbMath1326.90073arXiv1305.7319OpenAlexW2141784444MaRDI QIDQ480821

Monique Laurent, Zhao Sun

Publication date: 11 December 2014

Published in: Journal of Global Optimization (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationlinear programming relaxationpolynomial optimizationHandelman hierarchymaximum stable set problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

A new algorithm for concave quadratic programming, A MAX-CUT formulation of 0/1 programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rank of Handelman hierarchy for Max-Cut
• The strong perfect graph theorem
• Representing polynomials by positive linear functions on compact convex polyhedra
• Stable sets and polynomials
• The stable set problem and the lift-and-project ranks of graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• A one-to-one correspondence between colorings and stable sets
• A characterization of perfect graphs
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• Approximation of the Stability Number of a Graph via Copositive Programming
• Theta Bodies for Polynomial Ideals
• Error Bounds for Some Semidefinite Programming Approaches to Polynomial Minimization on the Hypercube
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Equivalence of Algebraic Approaches to the Minimization of Forms on the Simplex
• Neural networks, error-correcting codes, and polynomials over the binary n-cube
• Properties of vertex packing and independence system polyhedra
• Reducibility among Combinatorial Problems
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• Semidefinite Programming vs. LP Relaxations for Polynomial Programming
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming