Given a primal LP and an optimum solution thereof, it is well-known that complementary slackness conditions [1] can be used in non-degenerate cases to produce a dual optimum solution.

For instance, if we have an LP of the form $\max c^Tx, Ax\le b, x \ge 0$ with $m$ constraints and $n$ variables, and we are given a vertex optimum solution such that at least $m$ primal slack values and primal optimum coordinates are strictly positive, then it is easy to use Gaussian elimination to produce the optimum solution of the dual.

However, many degenerate cases can happen: an optimum vertex can be placed on many more constraints, or many variables can be set to 0, meaning that in such degenerate cases, complementary slackness does not seem to lead to a fast way of getting a dual optimum solution.

Is there an argument showing that the problem of computing any dual solution in such degenerate cases, while knowing the optimum, is equivalent (in complexity) to solving LP from scratch?


Yes, in some sense at least. See the following paper:

Megiddo, Nimrod. "On finding primal-and dual-optimal bases." ORSA Journal on Computing 3.1 (1991): 63-65. PDF available here.

It shows that:

if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for one of the problems, then there exists a strongly polynomial algorithm for the general linear programming problem.

(Note the details of the result though: it is about finding an optimal basis and deals with strongly polynomial-time algorithms.)

  • $\begingroup$ Looking at the paper more carefully, my impression is that the techniques in this paper can be used to give a yes answer to the OP's questions. But right now, I don't want to take the time to do it. $\endgroup$ – Peter Shor Apr 22 '15 at 15:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.