Lower bounds for a subexponential optimization algorithm

DOI10.1002/RSA.3240050408MaRDI QIDQ4312749zbMATH OpenOpenAlexFDO

Authors Jiří Matoušek

Publication date 8 November 1994

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://refubium.fu-berlin.de/handle/fub188/19365

zbMATH Keywords

randomized algorithmSharir-Welzl algorithmsubexponential bound for the expected running time

Mathematics Subject Classification ID

Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Recommendations

• A subexponential bound for linear programming
• A Subexponential Algorithm for Abstract Optimization Problems
• The worst-case running time of the random simplex algorithm is exponential in the height
• scientific article; zbMATH DE number 1256684
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Automatic average-case analysis of algorithms
• Polynomial algorithms in linear programming
• Small-dimensional linear programming and convex hulls made easy

Cited in

(14)

• Realizability makes a difference: a complexity gap for sink-finding in USOs
• Realizability in Matoušek unique sink orientations: characterization and complexity gap
• Optimization of the temple lower bound
• A Subexponential Algorithm for Abstract Optimization Problems
• Unique sink orientations of grids
• Lower bound on complexity of optimization of continuous functions
• A subexponential bound for linear programming
• A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations
• The Random‐Facet simplex algorithm on combinatorial cubes
• Random edge can be exponential on abstract cubes
• Helly’s theorem: New variations and applications
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• Linear programming, the simplex algorithm and simple polytopes
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes

This page was built for publication: Lower bounds for a subexponential optimization algorithm

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