The strong-duality polynomial-solvability conjecture for optimization problems
Statement
Let and be optimization problems such that one is the dual of the other, so that they exhibit strong duality. Strong-duality polynomial-solvability conjecture. Both and should be polynomially solvable. This conjecture is motivated by the canonical dual examples discussed in the paper, where strong duality and polynomial-time solution coexist; its general validity is not established here.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.