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

DOI10.4230/LIPICS.ESA.2017.69zbMATH Open1442.68185arXiv1706.09380MaRDI QIDQ5111758FDOQ5111758

Antonis Thomas

Publication date: 27 May 2020

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

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

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)

Cites Work

• Title not available (Why is that?)
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• A subexponential bound for linear programming
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
• Lower bounds for a subexponential optimization algorithm
• Theoretical Properties of the Network Simplex Method
• Counting unique-sink orientations
• What is the worst case behavior of the simplex algorithm?
• The Random‐Facet simplex algorithm on combinatorial cubes
• 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
• A Subexponential Algorithm for Abstract Optimization Problems
• Randomized simplex algorithms on Klee-Minty cubes
• The number of unique-sink orientations of the hypercube
• Random edge can be exponential on abstract cubes
• Jumping Doesn’t Help in Abstract Cubes
• 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
• The Complexity of Recognizing Unique Sink Orientations
• The Klee–Minty random edge chain moves with linear speed
• Random-Edge Is Slower Than Random-Facet on Abstract Cubes
• The Niceness of Unique Sink Orientations

Cited In (2)

• Unique end of potential line
• An exponential lower bound for Zadeh's pivot rule

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)