论文标题
关于最深度电路步骤的近似性的注释
A Note on the Approximability of Deepest-Descent Circuit Steps
论文作者
论文摘要
线性程序（LPS）可以通过沿电路方向多个移动来求解，从而改善了目标最深入的最深度步骤（DD-Steps）。计算这些步骤是NP-HARD（De Loera等，Arxiv，2019年），这是由于确定具有非唯一Optima的LPS上的最佳电路 - 邻居（OCNP）的硬度的结果。 我们证明OCNP在独特的Optima的承诺下很容易，但是已经$ O（n^{1- \ Varepsilon}）$ - 近似DD-Steps近似于完全单模型的$ n $ dimensional-demensional 0/1-lps，具有独特的最佳效果。我们提供匹配的$ n $ approximation。
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.
