A Note on the Approximability of Deepest-Descent Circuit Steps
Lists
Only you see this
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...