Semidefinite programming and integer programming

Monique Laurent (moniquecwi.nl)
Franz Rendl (franz.rendluni-klu.ac.at)

Abstract: We survey how semidefinite programming can be used for finding good approximative solutions to hard combinatorial optimization problems.

Keywords: combinatorial optimization, linear programming, semidefinite programming, approximative algorithm

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Preliminary version appeared as Report PNA-R0210, CWI, Amsterdam, April 2002. To appear as Chapter in the Handbook on Discrete Optimization, K. Aardal, G. Nemhauser, R. Weismantel, eds., Elsevier Publishers.

Download: [Postscript]

Entry Submitted: 12/19/2002
Entry Accepted: 12/19/2002
Entry Last Modified: 09/26/2003

Modify/Update this entry