A Note on the Approximability of Deepest-Descent Circuit Steps

DOI10.1016/J.ORL.2021.02.003MaRDI QIDQ6351860arXivFDO

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

Publication date 21 October 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.ORL.2021.02.003

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

arXiv classification

cs.DSmath.OC

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.

This page was built for publication: A Note on the Approximability of Deepest-Descent Circuit Steps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6351860)