scientific article; zbMATH DE number 7205047
From MaRDI portal
Publication:5111758
DOI10.4230/LIPIcs.ESA.2017.69zbMath1442.68185arXiv1706.09380MaRDI QIDQ5111758
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1706.09380
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- Randomized simplex algorithms on Klee-Minty cubes
- Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
- A subexponential bound for linear programming
- Counting unique-sink orientations
- The number of unique-sink orientations of the hypercube
- Random edge can be exponential on abstract cubes
- The Complexity of Recognizing Unique Sink Orientations
- A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
- Jumping Doesn’t Help in Abstract Cubes
- Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
- Theoretical Properties of the Network Simplex Method
- Lower bounds for a subexponential optimization algorithm
- The Random‐Facet simplex algorithm on combinatorial cubes
- Random-Edge Is Slower Than Random-Facet on Abstract Cubes
- The Niceness of Unique Sink Orientations
- A Subexponential Algorithm for Abstract Optimization Problems
- The Klee–Minty random edge chain moves with linear speed
- Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
