On semidefinite programming bounds for graph bandwidth
Etienne De Klerk (e.deklerkuvt.nl)
Abstract: We propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoretical Computer Science, 235(1):25-42, 2000], and [J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM Journal on Optimization, 18(1):223-241, 2007].
Keywords: Graph bandwidth, cyclic bandwidth, semidefinite programming, quadratic assignment problem
Category 1: Linear, Cone and Semidefinite Programming
Category 2: Combinatorial Optimization
Citation: Working paper, Tilburg University, The Netherlands, May 2010.
Entry Submitted: 06/06/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|