标题： 电路不平衡度量和线性规划 显示英文标题

标题： Circuit imbalance measures and linear programming

摘要： 我们研究与线性空间相关的各种电路不平衡度量的性质和应用。这些度量描述了该空间中支持最小的非零向量的非零条目之间的可能比率。分数电路不平衡度量在在线性规划的背景下被证明是一个关键参数，两种整数变体可以用来描述相关多面体的整数性质。我们概述了这些度量的性质，并调查了经典和最近的应用，特别是对于仅依赖于约束矩阵运行时间的线性规划算法，以及电路增强算法。我们还以分数电路不平衡度量为基准，给出了多面体的直径和电路直径的新界限。 显示英文摘要

摘要： We study properties and applications of various circuit imbalance measures associated with linear spaces. These measures describe possible ratios between nonzero entries of support-minimal nonzero vectors of the space. The fractional circuit imbalance measure turns out to be a crucial parameter in the context of linear programming, and two integer variants can be used to describe integrality properties of associated polyhedra. We give an overview of the properties of these measures, and survey classical and recent applications, in particular, for linear programming algorithms with running time dependence on the constraint matrix only, and for circuit augmentation algorithms. We also present new bounds on the diameter and circuit diameter of polyhedra in terms of the fractional circuit imbalance measure.