Unique sink orientations of cubes

No abstract is available for this paper.

• Publication year

  2001

• Venue

  Proceedings IEEE International Conference on Cluster Computing

• Publication date

  2001-10-14

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFCS.2001.959931
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Cube Tiling of Dimension Eight with No Facesharing

  2002cited by this paper
• ON LP-ORIENTATIONS OF CUBES AND CROSSPOLYTOPES

  2002cited by this paper
• The Random‐Facet simplex algorithm on combinatorial cubes

  2002cited by this paper
• Finding the Sink Takes Some Time

  2002cited by this paper
• Theoretical Aspects of Computer Science

  2002cited by this paper
• Randomized pivot algorithms for P-matrix linear complementarity problems

  2002cited by this paper
• Explicit and Implicit Enforcing - Randomized Optimization

  2001cited by this paper
• Discrete Mathematics and its applications

  2000influential reference
• A proof of the strict monotone 4-step conjecture

  1998cited by this paper
• Abstract objective function graphs on the 3-cube

  1998cited by this paper
• Combinatorial Linear Programming: Geometry Can Help

  1998cited by this paper
• Linear programming, the simplex algorithm and simple polytopes

  1997cited by this paper
• Deformed products and maximal shadows of polytopes

  1996cited by this paper
• Linear Programming - Randomization and Abstract Frameworks

  1996cited by this paper
• Lectures on Polytopes

  1994cited by this paper
• Randomized Simplex Algorithms on Klee-Minty Cubes

  1994cited by this paper
• Cube Tilings as Contributions of Algebra to Geometry

  1993cited by this paper
• A subexponential algorithm for abstract optimization problems

  1992cited by this paper
• Keller’s cube-tiling conjecture is false in high dimensions

  1992cited by this paper
• A subexponential bound for linear programming

  1992cited by this paper
• Construction Of Asymptotically Good Low-rate Error-correcting Codes Through Pseudo-random Graphs

  1991cited by this paper
• On Total Functions, Existence Theorems and Computational Complexity

  1991cited by this paper
• From Linear Separability to Unimodality: A Hierarchy of Pseudo-Boolean Functions

  1988cited by this paper
• Completely unimodal numberings of a simple polytope

  1988cited by this paper
• Polynomial Algorithms for Linear Programming

  1988cited by this paper
• The Mathematics Of Nonlinear Programming

  1988cited by this paper
• What is the Worst Case Behavior of the Simplex Algorithm

  1980cited by this paper
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem

  1978cited by this paper
• Long Monotone Paths in Abstract Polytopes

  1976influential reference
• HOW GOOD IS THE SIMPLEX ALGORITHM

  1970cited by this paper
• A partition theorem for Euclidean $n$-space

  1958cited by this paper
• Bibliography

  1898cited by this paper
• Über die lückenlose Erfüllung des Raumes mit Würfeln.

  year unknowncited by this paper

• On Flipping Edge Sets in Unique Sink Orientations

  2025cites this paper
• Greed is slow on sparse graphs of oriented valued constraints

  2025cites this paper
• An unconditional lower bound for the active-set method on the hypercube

  2025cites this paper
• Realizability in Matoušek Unique Sink Orientations: Characterization and Complexity Gap

  2025influential citation
• Lower bounds for ranking-based pivot rules

  2025cites this paper
• Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents

  2024cites this paper
• When is local search both effective and efficient?

  2024cites this paper
• Non-Promise Version of Unique Sink Orientations

  2024influential citation
• On Phases of Unique Sink Orientations

  2023cites this paper
• On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem

  2023cites this paper
• A unified worst case for classical simplex and policy iteration pivot rules

  2023cites this paper
• Realizability Makes a Difference: A Complexity Gap for Sink-Finding in USOs

  2022influential citation
• A Universal Construction for Unique Sink Orientations

  2022influential citation
• Generation of Proper Families of Functions

  2022cites this paper
• A Characterization of the Realizable Matoušek Unique Sink Orientations

  2021influential citation
• On the computational equivalence of co-NP refutations of a matrix being a P-matrix

  2021influential citation
• A New Combinatorial Property of Geometric Unique Sink Orientations

  2020influential citation
• Unique sink orientations for homogeneous linear inequalities and their alternative systems

  2019cites this paper
• A Tighter Analysis of Randomised Policy Iteration

  2019cites this paper
• Computational Complexity as an Ultimate Constraint on Evolution

  2019cites this paper
• Lecture Series in IRIF : Games on Graphs and Linear Programming Abstractions

  2019influential citation
• The Complexity of Optimization on Grids

  2019cites this paper
• A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games

  2019cites this paper
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes

  2018influential citation
• End of Potential Line

  2018cites this paper
• Unique End of Potential Line

  2018influential citation
• Improved Strong Worst-case Upper Bounds for MDP Planning

  2017cites this paper
• A Linear Algorithm for Finding the Sink of Unique Sink Orientations on Grids

  2017influential citation
• Directed Random Walks on Polytopes with Few Facets

  2017influential citation
• Pseudo Unique Sink Orientations

  2017cites this paper
• Exponential Lower Bounds for History-Based Simplex Pivot Rules on Abstract Cubes

  2017influential citation
• 49 LINEAR PROGRAMMING

  2017cites this paper
• Redundancy in Linear Systems: Combinatorics, Algorithms and Analysis

  2017cites this paper
• A Quantum Approach to the Unique Sink Orientation Problem

  2016cites this paper
• Random-Edge Is Slower Than Random-Facet on Abstract Cubes

  2016cites this paper
• The Niceness of Unique Sink Orientations

  2016cites this paper
• Batch-Switching Policy Iteration

  2016influential citation
• 50 LINEAR PROGRAMMING

  2016cites this paper
• The Complexity of All-switches Strategy Improvement

  2015cites this paper
• Articles and Scheduling for Student Seminar in Combinatorics: Linear Complementarity

  2015cites this paper
• Random Sampling with Removal

  2015cites this paper
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm

  2015cites this paper
• Classical and Quantum Algorithms for USO Recognition

  2015influential citation
• The Complexity of Recognizing Unique Sink Orientations

  2015cites this paper
• Classical and Quantum Algorithms for USO Recognition

  2015influential citation
• Errata for: A subexponential lower bound for the Random Facet algorithm for Parity Games

  2014cites this paper
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes

  2014influential citation
• Improved bound on the worst case complexity of Policy Iteration

  2014cites this paper
• A complexity analysis of Policy Iteration through combinatorial matrices arising from Unique Sink Orientations

  2014cites this paper
• Random-Facet and Random-Bland require subexponential time even for shortest paths

  2014cites this paper
• Enumeration of PLCP-orientations of the 4-cube

  2013influential citation
• Complexity of evolutionary equilibria in static fitness landscapes

  2013cites this paper
• An exponential lower bound for Cunningham’s rule

  2013cites this paper
• Conflict-Free Graph Orientations with Parity Constraints

  2012cites this paper
• A fresh look at the complexity of pivoting in linear complementarity

  2012cites this paper
• Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs

  2011cites this paper
• Worst-case Behaviour of History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes

  2011cites this paper
• Families of polytopal digraphs that do not satisfy the shelling property

  2011cites this paper
• On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes

  2011influential citation
• Counting unique-sink orientations

  2010cites this paper
• Finding a Simple Polytope from Its Graph in Polynomial Time

  2009cites this paper
• A family of polytopal digraphs that do not satisfy the shelling property

  2009cites this paper
• Approximating Smallest Enclosing Balls with Applications to Machine Learning

  2009cites this paper
• A Simple P-Matrix Linear Complementarity Problem for Discounted Games

  2008cites this paper
• On Combinatorial Properties of Linear Program Digraphs

  2008cites this paper
• Pivoting in Linear Complementarity: Two Polynomial-Time Cases

  2008cites this paper
• Violator spaces: Structure and algorithms

  2008cites this paper
• Complexity and infinite games on finite graphs

  2007cites this paper
• Abstract Models of Optimization Problems

  2007cites this paper
• Finding a Polytope from Its Graph in Polynomial Time

  2007cites this paper
• Removing Degeneracy May Require a Large Dimension Increase

  2007cites this paper
• The Holt-Klee condition for oriented matroids

  2006influential citation
• Violator spaces: Structure and algorithms

  2006cites this paper
• Linear programming and unique sink orientations

  2006cites this paper
• Smallest enclosing balls of balls

  2005influential citation
• Jumping Doesn't Help in Abstract Cubes

  2005cites this paper
• Combinatorial Optimization for Infinite Games on Graphs

  2005cites this paper
• Unique Sink Orientations of Grids

  2005influential citation
• The Arrangement Method for Linear Programming

  2005cites this paper
• Random edge can be exponential on abstract cubes

  2004cites this paper
• Approximating Smallest Enclosing Balls

  2004cites this paper
• Unique sink orientations of cubes

  2004influential citation
• Finding the Sink Takes Some Time: An Almost Quadratic Lower Bound for Finding the Sink of Unique Sink Oriented Cubes

  2004cites this paper
• LP-related Properties of Polytopes with Few Facets

  2003cites this paper
• The smallest enclosing ball of balls: combinatorial structure and algorithms

  2003cites this paper
• Finding the Sink Takes Some Time

  2002cites this paper
• Some Algorithmic Problems in Polytope Theory

  2002cites this paper
• Pivoting in Linear Complementarity Two Polynomial-Time Cases

  year unknowncites this paper