S-Space College of Engineering/Engineering Practice School (공과대학/대학원) Dept. of Industrial Engineering (산업공학과) Journal Papers (저널논문_산업공학과)
Rank of Handelman hierarchy for Max-Cut
- Park, Myoung-Ju; Hong, Sung Pil
- Issue Date
- ELSEVIER SCIENCE BV
- OPERATIONS RESEARCH LETTERS; Vol.39 5; 323-328
- Polynomial optimization; RLT; Max-Cut; Rank of hierarchical relaxation; Handelman hierarchy
- We consider a hierarchical relaxation, called Handelman hierarchy, for a class of polynomial optimization problems. We prove that the rank of Handelman hierarchy, if applied to a standard quadratic formulation of Max-Cut, is exactly the same as the number of nodes of the underlying graph. Also we give an error bound for Handelman hierarchy, in terms of its level, applied to the Max-Cut formulation. (C) 2011 Elsevier B.V. All rights reserved.
- Files in This Item: There are no files associated with this item.