Publications
Detailed Information
Rank of Handelman hierarchy for Max-Cut
Cited 3 time in
Web of Science
Cited 3 time in Scopus
- Authors
- Issue Date
- 2011-09
- Publisher
- ELSEVIER SCIENCE BV
- Citation
- OPERATIONS RESEARCH LETTERS; Vol.39 5; 323-328
- Keywords
- Polynomial optimization ; RLT ; Max-Cut ; Rank of hierarchical relaxation ; Handelman 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
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.