What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ IIRC, nothing was really improved after Eva Tardos' work in 1986: jstor.org/stable/170819 $\endgroup$– Dima PasechnikCommented Jun 13, 2018 at 16:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The best known general result is due to Eva Tardos' "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs", published in 1986.
Basically, it says that only bitsizes of coefficients in the constraints matrix $A$ need to be taken into account, whereas sizes of coefficients in the RHS $b$ and in the objective function $c$ don't matter, for the LP in the usual form $$\max_x \langle c,x\rangle \quad \text{subject to }Ax\leq b.$$
answered Jun 13, 2018 at 16:46