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