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$ – Alessandro Cosentino Nov 18 '13 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$ – Sasho Nikolov Nov 18 '13 at 18:36
  • 2
    $\begingroup$ combinatorial primal-dual is a large class :). do you count mult-weight-update in that class as well ? $\endgroup$ – Suresh Venkat Nov 18 '13 at 18:52
  • 1
    $\begingroup$ @Suresh, true :). I had multiplicative weights (or Plotkin-Shmoys-Tardos) and Edmonds' blossom algorithm in mind as examples. $\endgroup$ – Sasho Nikolov Nov 18 '13 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.