Browse

Rank of Handelman hierarchy for Max-Cut

Cited 3 time in Web of Science Cited 3 time in Scopus
Authors
Park, Myoung-Ju; Hong, Sung Pil
Issue Date
2011-09
Publisher
ELSEVIER SCIENCE BV
Citation
OPERATIONS RESEARCH LETTERS; Vol.39 5; 323-328
Keywords
Polynomial optimizationRLTMax-CutRank of hierarchical relaxationHandelman hierarchy
Abstract
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.
ISSN
0167-6377
Language
English
URI
https://hdl.handle.net/10371/74910
DOI
https://doi.org/10.1016/j.orl.2011.07.006
Files in This Item:
There are no files associated with this item.
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse