Mixed Linear and Semidefinite Programming for Combinatorial and
Quadratic Optimization
S. Benson, Y. Ye and X. Zhang
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 3000.
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.
Check http://dollar.biz.uiowa.edu/col/
for free SDP software.
Working Paper, Applied Mathematics and Computational Sciences,
University of Iowa, Iowa City, IA 52242, February, 1998.
Contact: [email protected]