A Note on the Approximability of Deepest-Descent Circuit Steps

Steffen Borgwardt, Cornelius Brand, Andreas Emil Feldmann, Martin Koutecký

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., 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.
BibTeX
@article{borgwardt2021note,
  author = {Steffen Borgwardt and Cornelius Brand and Andreas Emil Feldmann and Martin Koutecký},
  title = {{A Note on the Approximability of Deepest-Descent Circuit Steps}},
  journal = {Oper. Res. Lett.},
  year = {2021},
  doi = {10.1016/j.orl.2021.02.003},
}

Loading related content...

Figure