Optimization Online


On semidefinite programming bounds for graph bandwidth

Etienne De Klerk (e.deklerk***at***uvt.nl)
Marianna E.-Nagy (m.nagy***at***uvt.nl)
Renata Sotirov (r.sotirov***at***uvt.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.

Download: [PDF]

Entry Submitted: 06/06/2011
Entry Accepted: 06/06/2011
Entry Last Modified: 06/17/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society