Research indexJournal article
Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
Benson, Ye, Zhang
SIAM Journal on Optimization1 Jan 2000
NobleIDark:/48914/w1/20260515/AA31287DDOI10.1137/s1052623497328008
Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
Benson, Ye, Zhang · SIAM Journal on Optimization · 2000 · Subscription
NobleIDark:/48914/w1/20260515/AA31287DDOI10.1137/s1052623497328008
The full text is at the publisher
You can read the abstract here, or open it at the publisher.
Abstract
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.