Abstract | ||
---|---|---|
Some of the strongest polynomial-time relaxations to NP-hard combinatorial optimization problems are semidefinite programs (SDPs), but their solution complexity of up to O(n (6.5) L) time and O(n(4)) memory for L accurate digits limits their use in all but the smallest problems. Given that combinatorial SDP relaxations are often sparse, a technique known as chordal conversion can sometimes reduce complexity substantially. In this paper, we describe a modification of chordal conversion that allows any general-purpose interiorpoint method to solve a certain class of sparse SDPs with a guaranteed complexity of O(n(1.5) L) time and O(n) memory. To illustrate the use of this technique, we solve the MAX k-CUT relaxation and the Lovasz Theta problem on power system models with up to n = 13659 nodes in 5 minutes, using SeDuMi v1.32 on a 1.7 GHz CPU with 16 GB of RAM. The empirical time complexity for attaining L decimal digits of accuracy is approximate to 0.001n (1.1) L seconds. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1109/CDC.2018.8619478 | 2018 IEEE CONFERENCE ON DECISION AND CONTROL (CDC) |
Field | DocType | ISSN |
Sparse approximation,Algorithm,Time complexity,Semidefinite embedding,Mathematics | Conference | 0743-1546 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Richard Y. Zhang | 1 | 10 | 6.92 |
Javad Lavaei | 2 | 587 | 71.90 |