A faster algorithm for solving general LPs

DOI10.1145/3406325.3451058MaRDI QIDQ6087047zbMATH OpenOpenAlexFDO

Authors Shunhua Jiang, Zhao Song, O. Weinstein, Hengjie Zhang

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3406325.3451058

zbMATH Keywords

convex optimizationdynamic data-structurelinear programming

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(11)

• A general method to speed up fixed-parameter-tractable algorithms
• A dynamic programming solution to a generalized LCS problem
• Approximating the shortest path problem with scenarios
• Reasoning in OWL 2 EL with hierarchical concrete domains
• Quantum speedups for linear programming via interior point methods
• The bit complexity of dynamic algebraic formulas and their determinants
• On matrix multiplication and polynomial identity testing
• Computing smallest convex intersecting polygons
• On approximability of _2² min-sum clustering
• Almost optimal superconstant-pass streaming lower bounds for reachability
• Acceleration meets inverse maintenance: faster _-regression

This page was built for publication: A faster algorithm for solving general LPs

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