21-691 Topics in Optimization:

Semidefinite Programming for Combinatorial Optimization

This page will contain some of the material (syllabus, hws, etc.) that will be used in this course as well as some links that will be of interest to students taking it.

Course Materials

• Syllabus



Max-cut articles:

• M. X. Goemans and D. P. Williamson.
  "Improved Approxiamtion Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming",
  J. ACM, 42, pp. 1115-1145, 1995.
  ps-file (ftp)
• A. Frieze and M. Jerrum.
  "Improved approximation algorithms for MAX k-CUT and MAX BISECTION",
  IPCO IV Proc., LNCS 920, Springer 1995, pp. 1-13.
  ps.Z-file (http)
• D. Bertsimas and Y. Ye.
  "Semidefinite Relaxations, Multivariate Normal Distributions, and Order Statistics",
  Working Paper, Department of Management Sciences, The University of Iowa, IA, USA, November, 1997.
  ps-file (ftp) or dvi-file (ftp)

  Graph partitioning articles:

• H. Wolkowicz and Q. Zhao.
  "Semidefinite Programming Relaxations for the Graph Partitioning Problem",
  October 1996.
  ps.gz-file (ftp)
• S. E. Karisch, F. Rendl, and J. Clausen.
  "Solving graph bisection problems with semidefinite programming",
  Technical Report DIKU-TR-97/9, Department of Computer Science, University of Copenhagen, July 1997.
  ps-file (http)

  Quadratic Assignment Problem

• Q. Zhao, S. E. Karisch, F. Rendl, and H. Wolkowicz.
  "Semidefinite programming relaxations for the quadratic assignment poblem",
  CORR Report 95/27, University of Waterloo, September, 1996.
  ps.gz-file (ftp)
• C.-J. Lin and R. Saigal.
  "On Solving Large-Scale Semidefinite Programming Problems -- A Case Study of Quadratic Assignment Problem",
  Department of Industrial and Operations Engineering, University of Michigan, December 1997.
  ps-file (http)

Links

• Semidefinite Programming page maintained by C. Helmberg
• Michael Trick's Operations Research Page