Improved deterministic algorithms for linear programming in low dimensions

DOI10.1145/3155312MaRDI QIDQ4554358zbMATH OpenOpenAlexWikidataFDO

Authors Timothy M. Chan

Publication date 13 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

computational geometryderandomizationepsilon-netslinear programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20) Linear programming (90C05)

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

(19)

• Strict monotonicity in Todd's low-complexity algorithm for linear programming
• A strictly improving linear programming Phase I algorithm
• The \(\varepsilon\)-\(t\)-net problem
• Improved complexity results on solving real-number linear feasibility problems
• scientific article; zbMATH DE number 437553 (Why is no real title available?)
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• An improved targeted climbing algorithm for linear programs
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• Improved deterministic algorithms for linear programming in low dimensions
• Solving tall dense linear programs in nearly linear time
• A Deterministic Linear Program Solver in Current Matrix Multiplication Time
• Low-Dimensional Linear Programming with Violations
• A Deterministic ${\operatorname{Poly}}(\log \log N)$-TimeN-Processor Algorithm for Linear Programming in Fixed Dimension
• Zarankiewicz's problem via -t-nets
• On the efficiency of algebraic simplex algorithms for solving MDPs
• The computational complexity of the weak gravity conjecture
• Simple multi-pass streaming algorithms for skyline points and extreme points
• Hitting and covering affine families of convex polyhedra, with applications to robust optimization
• Polychromatic coloring of tuples in hypergraphs

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 Q4554358)