University of Waterloo
Eigenvalue, Quadratic Programming and Semidefinite Programming Bounds for Graph Partitioning Problems
Abstract
dc:description.abstractThe Graph Partitioning problems are hard combinatorial optimization problems. We are interested in both lower bounds and upper bounds. We introduce several methods including basic eigenvalue and projected eigenvalue techniques, convex quadratic programming techniques, and semidefinite programming (SDP). In particular, we show that the SDP relaxation is equivalent to and arises from the Lagrangian relaxation for a particular quadratically constrained quadratic model. Moreover, the bounds obtained by the eigenvalue techniques are good and cheap.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2014
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Wang, Ningchuan
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/8760