Improved deterministic algorithms for linear programming in low dimensions

DOI10.1137/1.9781611974331.CH84MaRDI QIDQ4575665zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan

Publication date 16 July 2018

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

Full work available at URL https://doi.org/10.1137/1.9781611974331.ch84

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Improved deterministic algorithms for linear programming in low dimensions
• scientific article; zbMATH DE number 437553
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• A randomized algorithm for fixed-dimensional linear programming
• Small-dimensional linear programming and convex hulls made easy

Cited in

(13)

• The complexity of optimization on grids
• An improved targeted climbing algorithm for linear programs
• Low-Dimensional Linear Programming with Violations
• A Deterministic Linear Program Solver in Current Matrix Multiplication Time
• A strictly improving linear programming Phase I algorithm
• 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 Algorithms For Linear Inequalities with Two Variables Per Inequality
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• Solving tall dense linear programs in nearly linear time
• Deterministic algorithms for unique sink orientations of grids
• scientific article; zbMATH DE number 437553 (Why is no real title available?)

This page was built for publication: Improved deterministic algorithms for linear programming in low dimensions

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