A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path

DOI10.1145/3406325.3451056arXiv2011.05365OpenAlexW3167765036MaRDI QIDQ6065294

Author name not available (Why is that?)

Publication date: 14 November 2023

Published in: (Search for Journal in Brave)

Abstract: 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 $widetildeO(ncdot{2}^{O(mathrmtw)})$ time, where $mathrmtw$ is the treewidth of the input graph. Analogously, many problems in P should be solvable in $widetildeO(ncdotmathrm{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 $mi{n}_{Ax=b,ellleqxlequ}{c}^{op}x$, and a width-$au$ tree decomposition of a graph $G_A$ related to $A$, we show how to solve it in time ${\displaystyle }$widetilde{O}(n cdot au^2 log (1/varepsilon)),${\displaystyle }$ 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 $widetildeO(ncdotmathrm{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.

Full work available at URL: https://arxiv.org/abs/2011.05365

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path

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