Publications

Detailed Information

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:

Altmetrics

Item View & Download Count

  • mendeley

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

Share