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.
- 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.
- 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.
- D. Bertsimas and Y. Ye.
"Semidefinite Relaxations, Multivariate Normal Distributions, and
Working Paper, Department of Management Sciences, The University of Iowa, IA, USA, November, 1997.
ps-file (ftp) or
Graph partitioning articles:
- H. Wolkowicz and Q. Zhao.
"Semidefinite Programming Relaxations for the Graph Partitioning Problem",
- 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.
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.
- 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.