SDP relaxations for some combinatorial optimization problems

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

Download

View SDP relaxations for some combinatorial optimization problems