Is there a fast way (polynomial complexity) of testing whether a given vertex for a linear program is optimal, without assuming non-degeneracy?

I can find the optimal vertex in worst-case polynomial time if I can find a way to test optimality of a vertex. This is not like Simplex where I would move from that vertex, I just need a checker to accept or reject the vertex.

Thanks in advance

  • $\begingroup$ I might be misunderstanding but this is a standard step in the simplex method to check if you are done. Essentially you check the Kuhn Tucker conditions. $\endgroup$ – ericf Dec 27 '18 at 5:12

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.