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.)

  • 1
    $\begingroup$ See some related questions: cstheory.stackexchange.com/q/14770/1542 and cstheory.stackexchange.com/q/14548/1542 $\endgroup$ Nov 18, 2013 at 18:05
  • 3
    $\begingroup$ actually the ellipsoid method and combinatorial primal-dual algorithms are the only ways I know how to solve some exponential size mathematical programs. $\endgroup$ Nov 18, 2013 at 18:36
  • 2
    $\begingroup$ combinatorial primal-dual is a large class :). do you count mult-weight-update in that class as well ? $\endgroup$ Nov 18, 2013 at 18:52
  • 1
    $\begingroup$ @Suresh, true :). I had multiplicative weights (or Plotkin-Shmoys-Tardos) and Edmonds' blossom algorithm in mind as examples. $\endgroup$ Nov 18, 2013 at 22:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.