Optimization Online


SDP relaxations for some combinatorial optimization problems

Renata Sotirov (r.sotirov***at***uvt.nl)

Abstract: 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.

Keywords: semidefinite programming, quadratic assignment problem, traveling salesman problem, graph equipartition problem, bandwidth problem

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Combinatorial Optimization

Citation: CentER Discussion Paper Tilburg University, The Netherlands, July 2010.

Download: [PDF]

Entry Submitted: 07/20/2010
Entry Accepted: 07/20/2010
Entry Last Modified: 11/27/2010

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 Programming Society