Publication at Faculty of Mathematics and Physics |
2006
Abstract
The n-cube is considered as a graph (with vertex set {0,1}^n. Unique-sink orientations are orientations of the edges of the n-cube such that every face has exactly one sink (directed cycles are allowed).
We estimate their number. Such orientations arise, e.g., from linear programs, from certain linear complementarity problems, and from certain convex programs.