Mixed linear and semidefinite programming for combinatorial and quadratic optimization

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