Exponential lower bounds for history-based simplex pivot rules on abstract cubes

DOI10.4230/LIPICS.ESA.2017.69MaRDI QIDQ5111758zbMATH OpenFDO

Authors Antonis Thomas

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1706.09380

zbMATH Keywords

lower boundexponentialpivot ruleunique sink orientation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The Complexity of Zadeh's Pivot Rule
• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• An exponential lower bound for Cunningham's rule
• On Friedmann's subexponential lower bound for Zadeh's pivot rule

Cites work

• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• A Subexponential Algorithm for Abstract Optimization Problems
• A subexponential bound for linear programming
• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• An exponential lower bound for Cunningham's rule
• Counting unique-sink orientations
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
• Jumping Doesn’t Help in Abstract Cubes
• Lower bounds for a subexponential optimization algorithm
• On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes
• Random edge can be exponential on abstract cubes
• Random-Edge Is Slower Than Random-Facet on Abstract Cubes
• Randomized simplex algorithms on Klee-Minty cubes
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• The Klee–Minty random edge chain moves with linear speed
• The Random‐Facet simplex algorithm on combinatorial cubes
• The complexity of recognizing unique sink orientations
• The niceness of unique sink orientations
• The number of unique-sink orientations of the hypercube
• Theoretical Properties of the Network Simplex Method
• What is the worst case behavior of the simplex algorithm?

Cited in

(6)

• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• Unique end of potential line
• An exponential lower bound for Zadeh's pivot rule
• On Friedmann's subexponential lower bound for Zadeh's pivot rule
• An exponential lower bound for Cunningham's rule
• On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes

This page was built for publication: Exponential lower bounds for history-based simplex pivot rules on abstract cubes

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