Unique sink orientations of grids
From MaRDI portal
Publication:930596
DOI10.1007/S00453-007-9090-XzbMATH Open1203.68124OpenAlexW2070970096MaRDI QIDQ930596FDOQ930596
Walter Morris, Leo Rüst, B. 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
Recommendations
linear programminggeneralized linear complementarity problemHolt-Klee conditionsink finding algorithmunique sink orientation
Cites Work
- THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lectures on Polytopes
- Title not available (Why is that?)
- Polynomial algorithms in linear programming
- Automata, logics, and infinite games. A guide to current research
- Las Vegas algorithms for linear and integer programming when the dimension is small
- A Linear Complementarity Problem with a P-Matrix
- A subexponential bound for linear programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linear programming — Randomization and abstract frameworks
- A simple way to tell a simple polytope from its graph
- Signable posets and partitionable simplicial complexes
- Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
- A subexponential randomized algorithm for the simple stochastic game problem
- A generalization of the linear complementarity problem
- Puzzles and polytope isomorphisms
- A quasi-polynomial bound for the diameter\\of graphs of polyhedra
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- Fundamentals of Computation Theory
- Lower bounds for a subexponential optimization algorithm
- Small-dimensional linear programming and convex hulls made easy
- Linear programming, the simplex algorithm and simple polytopes
- Linear programming and unique sink orientations
- LP-orientations of cubes and crosspolytopes
- The Random‐Facet simplex algorithm on combinatorial cubes
- Mathematical Foundations of Computer Science 2004
- Existence theory and \(Q\)-matrix characterization for the generalized linear complementarity problem: Revisited
- Existence theory and \(Q\)-matrix characterization for the generalized linear complementarity problem
- Completely unimodal numberings of a simple polytope
- Long Monotone Paths in Abstract Polytopes
- Title not available (Why is that?)
- Grid orientations, \((d,d+2)\)-polytopes, and arrangements of pseudolines
- Jumping Doesn’t Help in Abstract Cubes
- One line and n points
Cited In (16)
- The complexity of optimization on grids
- Realizability makes a difference: a complexity gap for sink-finding in USOs
- Deterministic Algorithms for Unique Sink Orientations of Grids
- Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
- Pivoting in linear complementarity: Two polynomial-time cases
- Counting unique-sink orientations
- A Mihalisin-Klee theorem for fans
- Enumeration of PLCP-orientations of the 4-cube
- Efficient computation of a canonical form for a matrix with the generalized P-property
- Unique Sink Orientations of Grids
- Mathematical Foundations of Computer Science 2004
- On the Holt-Klee property for oriented matroid programming
- Directed random walks on polytopes with few facets
- Title not available (Why is that?)
- Improved bound on the worst case complexity of policy iteration
- Random Walks on Polytopes of Constant Corank
Uses Software
This page was built for publication: Unique sink orientations of grids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q930596)
