Rank of Handelman hierarchy for Max-Cut

DOI10.1016/j.orl.2011.07.006zbMath1235.90154MaRDI QIDQ408389

Sung-Pil Hong, Myoung-Ju Park

Publication date: 5 April 2012

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2011.07.006

zbMATH Keywords

RLT; polynomial optimization; max-cut; Handelman hierarchy; rank of hierarchical relaxation

Mathematics Subject Classification ID

90C30: Nonlinear programming

Related Items

Handelman's hierarchy for the maximum stable set problem, Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications, Improved Convergence Rates for Lasserre-Type Hierarchies of Upper Bounds for Box-Constrained Polynomial Optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Representing polynomials by positive linear functions on compact convex polyhedra
• The \(K\)-moment problem for compact semi-algebraic sets
• A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
• On a Representation of the Matching Polytope Via Semidefinite Liftings
• On the Matrix-Cut Rank of Polyhedra
• 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
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Integrality gaps for Sherali-Adams relaxations
• Computation of the Lasserre Ranks of Some Polytopes
• On Lovász--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP
• Semidefinite Programming vs. LP Relaxations for Polynomial Programming
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming