Back to Search
Start Over
A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
- Source :
- STOC
- Publication Year :
- 2020
-
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 $\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-$\tau$ tree decomposition of a graph $G_A$ related to $A$, we show how to solve it in time $$\widetilde{O}(n \cdot \tau^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 \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.
- Subjects :
- FOS: Computer and information sciences
Vertex (graph theory)
Matching (graph theory)
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Tree decomposition
Treewidth
Optimization and Control (math.OC)
010201 computation theory & mathematics
Dual graph
Path (graph theory)
Computer Science - Data Structures and Algorithms
FOS: Mathematics
0202 electrical engineering, electronic engineering, information engineering
Rank (graph theory)
Data Structures and Algorithms (cs.DS)
020201 artificial intelligence & image processing
Algorithm
Time complexity
Mathematics - Optimization and Control
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- STOC
- Accession number :
- edsair.doi.dedup.....d974aca5dcd2633ddeabb154eae29582