A Deterministic Linear Program Solver in Current Matrix Multiplication Time

DOI10.1137/1.9781611975994.16MaRDI QIDQ5146781zbMATH OpenOpenAlexFDO

Authors Jan van Den Brand

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Solving linear programs in the current matrix multiplication time
• Solving Linear Programs in the Current Matrix Multiplication Time
• A Deterministic ${\operatorname{Poly}}(\log \log N)$-TimeN-Processor Algorithm for Linear Programming in Fixed Dimension
• Improved deterministic algorithms for linear programming in low dimensions
• Improved deterministic algorithms for linear programming in low dimensions
• scientific article; zbMATH DE number 4068606
• A fast simplex algorithm for linear programming
• A new polynomial-time algorithm for linear programming
• scientific article; zbMATH DE number 4121753
• Solving tall dense linear programs in nearly linear time

Cited in

(19)

• Small one-dimensional Euclidean preference profiles
• Solving Linear Programs in the Current Matrix Multiplication Time
• Solving tall dense linear programs in nearly linear time
• A Deterministic ${\operatorname{Poly}}(\log \log N)$-TimeN-Processor Algorithm for Linear Programming in Fixed Dimension
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• A simple approach for quantizing neural networks
• Efficient use of quantum linear system algorithms in inexact infeasible IPMs for linear optimization
• Assigning stationary distributions to sparse stochastic matrices
• Accuracy certificates for convex minimization with inexact oracle
• The bit complexity of dynamic algebraic formulas and their determinants
• Training multi-layer over-parametrized neural network in subquadratic time
• Interior point methods are not worse than simplex
• On matrix multiplication and polynomial identity testing
• Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
• Negative-weight single-source shortest paths in near-linear time
• Box filtration
• Barriers for rectangular matrix multiplication
• Faster min-cost flow and approximate tree decomposition on bounded treewidth graphs
• Acceleration meets inverse maintenance: faster _-regression

This page was built for publication: A Deterministic Linear Program Solver in Current Matrix Multiplication Time

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