Before revision:  computing deepest-descent steps is NP-hard and inapproximable even for 0/ 1 linear programs with a unique optimum which are defined by a totally unimodular constraint matrix .
After revision:  computing deepest-descent steps is NP-hard and inapproximable even for 0/ 1 linear programs with a unique optimum . We provide a matching n-approximation .