TY - JOUR
T1 - On semidefinite programming bounds for graph bandwidth
AU - de Klerk, E.
AU - Nagy, M.
AU - Sotirov, R.
N1 - Special Issue in Honour of Professor Kess Roos' 70th Birthday
PY - 2013
Y1 - 2013
N2 - In this paper, 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 reported in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoret. Comput. Sci. 235(1) (2000), pp. 25–42; J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM J. Optim. 18(1) (2007), pp. 223–241].
AB - In this paper, 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 reported in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoret. Comput. Sci. 235(1) (2000), pp. 25–42; J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM J. Optim. 18(1) (2007), pp. 223–241].
M3 - Article
SN - 1055-6788
VL - 28
SP - 485
EP - 500
JO - Optimization Methods & Software
JF - Optimization Methods & Software
IS - 3
ER -