In this chapter we present recent developments on solving various combinatorial optimization problems by using semidefinite programming (SDP). We present several SDP relaxations of the quadratic assignment problem and the traveling salesman problem. Further, we show the equivalence of several known SDP relaxations of the graph equipartition problem, and present recent results on the bandwidth problem.
Citation
CentER Discussion Paper Tilburg University, The Netherlands, July 2010.
Article
View SDP relaxations for some combinatorial optimization problems