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

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

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

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

Cited in

(15)

• Linear programming, the simplex algorithm and simple polytopes
• 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
• Random edge can be exponential on abstract cubes
• Helly’s theorem: New variations and applications
• scientific article; zbMATH DE number 1256684 (Why is no real title available?)
• Optimization of the temple lower bound
• The Random‐Facet simplex algorithm on combinatorial cubes
• A Subexponential Algorithm for Abstract Optimization Problems
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Realizability makes a difference: a complexity gap for sink-finding in USOs
• Realizability in Matoušek unique sink orientations: characterization and complexity gap
• Unique sink orientations of grids

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)