SDP relaxations for some combinatorial optimization problems
Renata Sotirov (r.sotirovuvt.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.
Entry Submitted: 07/20/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|