论文标题
具有小树宽的线性程序的近乎线性时间算法：可靠的中央路径的多尺度表示
A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
论文作者
论文摘要
由结构图理论引起的，树宽已成为各个社区中固定参数可拖动算法的研究重点，包括组合，整数线性编程和数值分析。众所周知，许多NP-硬质问题可在$ \ widetilde {o}（n \ cdot 2^{o（\ mathrm {tw}）}）$时间中解决，其中$ \ mathrm {tw} $是输入图的树宽。类似地，P中的许多问题应在$ \ widetilde {o}（n \ cdot \ mathrm {tw}^{o（1）}）$ time中解决。但是，由于缺乏适当的工具，目前仅知道一些这样的结果。 [FOM+18]猜想这与所有线性程序一样广泛；在我们的论文中，我们证明这是真的： 给定形式的线性程序$ \ min_ {ax = b，\ ell \ el \ leq x \ leq U} c^{\ top} x $，以及一个与$ a $相关的图形$ g_a $的width- $τ$树的分解（1/\ varepsilon）），$$，其中$ n $是变量的数量，$ \ varepsilon $是相对精度。结合最新的顶点流动流[BGS21]中的技术，这导致了使用$ \ widetilde {o}（n^{1+o（1）} \ cdot \ cdot \ mathrm {tw}^2^2 \ log（1/\ varepsilon）$ RUNTIPE的算法。除了是同类产品中的第一个外，我们的算法还具有运行时几乎匹配了解决子问题$ ax = b $的最快运行时（在没有使用快速矩阵乘法的假设下）。 我们通过将内点方法（IPM），素描和在多尺度基础类似于小波的基础上的溶液表示新颖的表示中来获得这些结果。
Arising from structural graph theory, treewidth has become a focus of study in fixed-parameter tractable algorithms in various communities including combinatorics, integer-linear programming, and numerical analysis. Many NP-hard problems are known to be solvable in $\widetilde{O}(n \cdot 2^{O(\mathrm{tw})})$ time, where $\mathrm{tw}$ is the treewidth of the input graph. Analogously, many problems in P should be solvable in $\widetilde{O}(n \cdot \mathrm{tw}^{O(1)})$ time; however, due to the lack of appropriate tools, only a few such results are currently known. [Fom+18] conjectured this to hold as broadly as all linear programs; in our paper, we show this is true: Given a linear program of the form $\min_{Ax=b,\ell \leq x\leq u} c^{\top} x$, and a width-$τ$ tree decomposition of a graph $G_A$ related to $A$, we show how to solve it in time $$\widetilde{O}(n \cdot τ^2 \log (1/\varepsilon)),$$ where $n$ is the number of variables and $\varepsilon$ is the relative accuracy. Combined with recent techniques in vertex-capacitated flow [BGS21], this leads to an algorithm with $\widetilde{O}(n^{1+o(1)} \cdot \mathrm{tw}^2 \log (1/\varepsilon))$ run-time. Besides being the first of its kind, our algorithm has run-time nearly matching the fastest run-time for solving the sub-problem $Ax=b$ (under the assumption that no fast matrix multiplication is used). We obtain these results by combining recent techniques in interior-point methods (IPMs), sketching, and a novel representation of the solution under a multiscale basis similar to the wavelet basis.
