Random edge can be exponential on abstract cubes

DOI10.1016/J.AIM.2005.05.021MaRDI QIDQ2496719zbMATH OpenOpenAlexFDO

Authors Tibor Szabó, Jiří Matoušek

Publication date 20 July 2006

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aim.2005.05.021

zbMATH Keywords

abstract objective functionlinear programmingrandomized algorithmsimplex algorithmunique sink orientation

Mathematics Subject Classification ID

Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Recommendations

• Random-Edge Is Slower Than Random-Facet on Abstract Cubes
• Two New Bounds for the Random‐Edge Simplex‐Algorithm
• The Random‐Facet simplex algorithm on combinatorial cubes
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
• Randomized simplex algorithms on Klee-Minty cubes

Cites work

• A combinatorial bound for linear programming and related problems
• A simple way to tell a simple polytope from its graph
• A Subexponential Algorithm for Abstract Optimization Problems
• A subexponential bound for linear programming
• Completely unimodal numberings of a simple polytope
• Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3614497 (Why is no real title available?)
• scientific article; zbMATH DE number 1241841 (Why is no real title available?)
• scientific article; zbMATH DE number 1301965 (Why is no real title available?)
• scientific article; zbMATH DE number 653033 (Why is no real title available?)
• scientific article; zbMATH DE number 1082101 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Jumping Doesn’t Help in Abstract Cubes
• Linear programming — Randomization and abstract frameworks
• Lower bounds for a subexponential optimization algorithm
• Minimization algorithms and random walk on the d-cube
• One line and \(n\) points
• Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
• Randomized simplex algorithms on Klee-Minty cubes
• The Klee–Minty random edge chain moves with linear speed
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The worst-case running time of the random simplex algorithm is exponential in the height

Cited in

(13)

• The complexity of optimization on grids
• A hybrid gradient and feasible direction pivotal solution algorithm for general linear programs
• Jumping Doesn’t Help in Abstract Cubes
• Random-Edge Is Slower Than Random-Facet on Abstract Cubes
• Unique End of Potential Line
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• Random walks on polytopes of constant corank
• The Klee–Minty random edge chain moves with linear speed
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
• Two New Bounds for the Random‐Edge Simplex‐Algorithm
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• An exponential lower bound for Zadeh's pivot rule
• An efficient algorithm for vertex enumeration of arrangement

This page was built for publication: Random edge can be exponential on abstract cubes

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