Unique sink orientations of grids
From MaRDI portal
Publication:930596
DOI10.1007/s00453-007-9090-xzbMath1203.68124OpenAlexW2070970096MaRDI QIDQ930596
Walter D. jun. Morris, Leo Rüst, Bernd Gärtner
Publication date: 1 July 2008
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/20.500.11850/14390
linear programminggeneralized linear complementarity problemHolt-Klee conditionsink finding algorithmunique sink orientation
Related Items
A Mihalisin-Klee theorem for fans ⋮ Pivoting in linear complementarity: Two polynomial-time cases ⋮ Directed random walks on polytopes with few facets ⋮ Realizability makes a difference: a complexity gap for sink-finding in USOs ⋮ Counting unique-sink orientations ⋮ Enumeration of PLCP-orientations of the 4-cube ⋮ Unnamed Item ⋮ Random Walks on Polytopes of Constant Corank ⋮ Improved bound on the worst case complexity of policy iteration ⋮ Efficient computation of a canonical form for a matrix with the generalized P-property ⋮ Deterministic Algorithms for Unique Sink Orientations of Grids ⋮ On the Holt-Klee property for oriented matroid programming ⋮ The complexity of optimization on grids
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Existence theory and \(Q\)-matrix characterization for the generalized linear complementarity problem: Revisited
- Puzzles and polytope isomorphisms
- Completely unimodal numberings of a simple polytope
- A simple way to tell a simple polytope from its graph
- Small-dimensional linear programming and convex hulls made easy
- Linear programming, the simplex algorithm and simple polytopes
- Automata, logics, and infinite games. A guide to current research
- A subexponential randomized algorithm for the simple stochastic game problem
- Existence theory and \(Q\)-matrix characterization for the generalized linear complementarity problem
- Signable posets and partitionable simplicial complexes
- A subexponential bound for linear programming
- Grid orientations, \((d,d+2)\)-polytopes, and arrangements of pseudolines
- Linear programming and unique sink orientations
- Jumping Doesn’t Help in Abstract Cubes
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- Long Monotone Paths in Abstract Polytopes
- Polynomial algorithms in linear programming
- A quasi-polynomial bound for the diameter\\of graphs of polyhedra
- Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
- Lower bounds for a subexponential optimization algorithm
- Lectures on Polytopes
- Las Vegas algorithms for linear and integer programming when the dimension is small
- One line and n points
- The Random‐Facet simplex algorithm on combinatorial cubes
- Linear programming — Randomization and abstract frameworks
- A Linear Complementarity Problem with a P-Matrix
- LP-orientations of cubes and crosspolytopes
- THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS
- Mathematical Foundations of Computer Science 2004
- Fundamentals of Computation Theory
- A generalization of the linear complementarity problem
