It is well known that you can use the algorithm for finding the equilibrium of a Zero-sum game to solve a linear program. In particular, you can take a LP and reduce it to a zero-sum game, and use the famous algorithm for zero sum games proposed by Grigoriadis and Khachiyan.

Is this equivalence used in practice, or the simplex algorithm (or any interior point methods) is always preferable? Why?

Notably, the approach of zero sum games offers an approximate solution in polynomial time, and converges in $O(1/\epsilon^2)$ iterations, contrary to the simplex algorithm which find the optimal solution in (worst-case) exponential time.

  • $\begingroup$ The statement is not correct. We do not actually know that interior point methods are linear in the size of the problem, and we know that the simplex algorithm is linear in the size of the problem "most of the time". $\endgroup$ – Wolfgang Bangerth May 25 at 14:56
  • $\begingroup$ I beg your pardon, but I don't see which statement is wrong. There are three paragraph here: in none of them I say that the IP methods are linear, and in none I say that the simplex it NOT efficient "most of the time" (i.e. i write WORST-CASE exponential time). $\endgroup$ – asdf May 26 at 4:01
  • $\begingroup$ Fair enough -- I took your statement "polynomial time" as implying "linear" because that's the only interesting case. But we don't know that interior point methods are polynomial in time. In any case: The way I read your last paragraph was as suggesting that interior point methods are fast (because it's polynomial) and the simplex algorithm is slow (exponential), but that is overly simplistic. $\endgroup$ – Wolfgang Bangerth May 26 at 15:09

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.