Linear programs (LPs) can be solved through a polynomial number of so-called deepest-descent circuit steps, each step following a circuit direction to a new feasible solution of most-improved objective function value. A computation of deepest-descent steps has recently been shown to be NP-hard  De Loera et al., arXiv, 2019 . This is a consequence of the hardness of what we call the optimal circuit-neighbor problem (OCNP) for LPs with non-unique optima. However, the non-uniqueness assumption is crucial to the hardness of OCNP, because we show that OCNP for LPs with a unique optimum is solvable in polynomial time. Moreover, in practical applications one is usually only interested in finding some optimum of an LP, in which case a simple perturbation of the objective yields an instance with a unique optimum. It is thus natural to ask whether deepest-descent steps are also easy to compute for LPs with unique optima, or whether this problem is hard despite OCNP being easy. We show that deepest-descent steps can be efficiently approximated within a factor of n, where n is the dimension of the polyhedron at hand, but not within a factor of O(n^{1- \epsilon }) for any \epsilon > 0. While we prove that OCNP can be solved efficiently for LPs with a unique optimum, our different hardness approach allows us to show strong negative results: 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 .
Linear programs (LPs) can be solved by polynomially many moves along the circuit direction improving the objective the most, so-called deepest-descent steps (dd-steps). Computing these steps is NP-hard ( De Loera et al., arXiv, 2019 ), a consequence of the hardness of deciding the existence of an optimal circuit-neighbor (OCNP) on LPs with non-unique optima. We prove OCNP is easy under the promise of unique optima, but already O(n^{1- \varepsilon }) -approximating dd-steps remains hard even for totally unimodular n-dimensional 0/ 1-LPs with a unique optimum . We provide a matching n-approximation .
R
through a polynomial number of
by polynomially many moves along the circuit direction improving the objective the most,
D
deepest-descent circuit steps, each step following a circuit direction to a new feasible solution of most-improved objective function value. A computation of
R
has recently been shown to be
(dd-steps). Computing these steps is
A
(
R
. This is
),
R
what we call the
deciding the existence of an
D
problem
R
for
on
R
However, the non-uniqueness assumption is crucial to the hardness of OCNP, because we show that OCNP for LPs with a unique optimum is solvable in polynomial time. Moreover, in practical applications one is usually only interested in finding some optimum of an LP, in which case a simple perturbation of the objective yields an instance with a unique optimum. It is thus natural to ask whether deepest-descent steps are also easy to compute for LPs with unique optima, or whether this problem is hard despite OCNP being easy. We show that deepest-descent steps can be efficiently approximated within a factor of n, where n is the dimension of the polyhedron at hand, but not within a factor of
We prove OCNP is easy under the promise of unique optima, but already
R
\epsilon
\varepsilon
R
for any \epsilon > 0. While we prove that OCNP can be solved efficiently for LPs with a unique optimum, our different hardness approach allows us to show strong negative results: computing deepest-descent steps is NP-hard and inapproximable even for
-approximating dd-steps remains hard even for totally unimodular n-dimensional
R
1 linear programs
1-LPs
R
which are defined by a totally unimodular constraint matrix
. We provide a matching n-approximation