Time complexity of standard semidefinite programming solvers

Asked Nov 18 '13 at 15:10

Active Dec 20 '13 at 06:42

Viewed 2,649 times

I am interested in exact scaling of the ellipsoid method and interior point methods for solving SDPs.

(I am not interested in algorithms like multiplicative weights updates method.)

edited Dec 20 '13 at 06:42

Sasho Nikolov

asked Nov 18 '13 at 15:10

postasaguest

1

See some related questions: http://cstheory.stackexchange.com/q/14770/1542 and http://cstheory.stackexchange.com/q/14548/1542 – Alessandro Cosentino Nov 18 '13 at 18:05
3

actually the ellipsoid method and combinatorial primal-dual algorithms are the only ways I know how to solve some exponential size mathematical programs. – Sasho Nikolov Nov 18 '13 at 18:36
2

combinatorial primal-dual is a large class :). do you count mult-weight-update in that class as well ? – Suresh Venkat Nov 18 '13 at 18:52
1

@Suresh, true :). I had multiplicative weights (or Plotkin-Shmoys-Tardos) and Edmonds' blossom algorithm in mind as examples. – Sasho Nikolov Nov 18 '13 at 22:29

0 Answers0