We present a dual-scaling interior-point algorithm and show how it exploits the structure and sparsity of some large-scale problems. We solve the positive semidefinite relaxation of combinatorial and quadratic optimization problems subject to boolean constraints. We report the first computational results of interior-point algorithms for approximating maximum cut semidefinite programs with dimension up to 3,000.
No takes yet. Share an insight, caveat, or question.
Benson et al. (2000) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: