Lower bounds for a subexponential optimization algorithm

DOI10.1002/rsa.3240050408zbMath0824.90094OpenAlexW2074044530MaRDI QIDQ4312749

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)

Related Items

A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations, The Random‐Facet simplex algorithm on combinatorial cubes, Linear programming, the simplex algorithm and simple polytopes, A subexponential bound for linear programming, Realizability makes a difference: a complexity gap for sink-finding in USOs, Helly’s theorem: New variations and applications, Unique sink orientations of grids, Random edge can be exponential on abstract cubes, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Unnamed Item

Cites Work

• Automatic average-case analysis of algorithms
• Small-dimensional linear programming and convex hulls made easy
• Polynomial algorithms in linear programming
• Unnamed Item