A note on the approximability of deepest-descent circuit steps

Abstrakt

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.

Klíčová slova

• Circuits
• Linear programming
• Deepest-descent steps
• Complexity theory