Rank of Handelman hierarchy for Max-Cut

DOI10.1016/J.ORL.2011.07.006MaRDI QIDQ408389zbMATH OpenOpenAlexFDO

Authors Myoung-Ju Park, Sung-Pil Hong

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

polynomial optimizationmax-cutHandelman hierarchyrank of hierarchical relaxationRLT

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Recommendations

• scientific article; zbMATH DE number 1786136
• On the rank of disjunctive cuts
• Handelman's hierarchy for the maximum stable set problem
• scientific article; zbMATH DE number 3906193
• Combinatorial properties and the complexity of a max-cut approximation
• On the approximability of Max-Cut
• Maximal graphs with respect to rank
• On maximum rank aggregation problems
• Max-Cut and containment relations in graphs
• scientific article; zbMATH DE number 1496855

Cites work

• scientific article; zbMATH DE number 527343 (Why is no real title available?)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• 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
• Computation of the Lasserre Ranks of Some Polytopes
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube
• Integrality gaps for Sherali-Adams relaxations
• On Lovász--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP
• On a representation of the matching polytope via semidefinite liftings
• On the matrix-cut rank of polyhedra.
• Representing polynomials by positive linear functions on compact convex polyhedra
• Semidefinite Programming vs. LP Relaxations for Polynomial Programming
• Sums of squares, moment matrices and optimization over polynomials
• The K-moment problem for compact semi-algebraic sets
• Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra

Cited in

(3)

• Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications
• Handelman's hierarchy for the maximum stable set problem
• Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization

This page was built for publication: Rank of Handelman hierarchy for Max-Cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q408389)