Workshop Semidefinite Programming: Applications and Algorithms
ZIB-Berlin, November 15-17, 1998


Yinyu Ye

"Mixed Linear and Semidefinite Programming for Combinatorial and Quadratic Optimization"

We use the semidefinite relaxation to approximate combinatorial and quadratic optimization problems subject to linear, quadratic, as well as boolean constraints. We present a dual potential reduction algorithm and show how to exploit the sparse structure of various problems. Coupled with randomized and heuristic methods, we report computational results for approximating graph-partition and quadratic problems with dimension up to 9000. This finding, to the best of our knowledge, is the first computational evidence of the effectiveness of these approximation algorithms for solving large-scale problems.


helmberg@zib.de
Last Update: September 28, 1998