Publication at Faculty of Mathematics and Physics |
2021
Abstract
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. (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-epsilon))-approximating dd-steps remains hard even for totally unimodular n-dimensional 0/1-LPs with a unique optimum. We provide a matching n-approximation. (C) 2021 Elsevier B.V.
All rights reserved.