Unique Sink Orientations

A unique sink orientation is an orientation of the hypercube such that for each subcube, there exists a unique sink. It is originally proposed in order to study the linear complementarity problem, and later is proved to highly related to other classical optimization problems.

Understand the Structure

Ingo Schurr thoroughly inspect the structure of the USO through the phases in his Ph.D. Thesis

Bernd Gartner introduce USO of grids as digraph models and designed the randomized sink finding algorithm in Unique Sink Orientations of Grids

Yuan Gao shows that for each vertice in D-cube, the L-graph of it is acyclic in this draft

Relationship between Optimization Scheme

Bernd Gartner and Ingo Schur show that a canonical linear programming defines a USO and finding the unique sink in the hypercube solve the program in linear programming and unique sink orientations

Stickney and Watson (namely pioneer in this topic) show that a linear complementarirty problem can be reduce to USO sink finding in this paper

Martin Jagg shows that convex quadratic programming can also be reduced to the sink finding problem in his Ph.D. Thesis

Find the Sink

Ingo Schurr provides us an almost quadratic lower bound for the general case in this paper

Bernd Gartner provides us an expected subexponential upper bound for the acyclic case in this paper

Count the Number of USOs

Matousek count the number of USOs in general cases in The Number Of Unique-Sink Orientations of the Hypercube

Jan Fonio estimate the number of P-matrix USOs in Counting unique-sink orientations

USO Polytope

Yuda works on the USO polytope and shows that the polytope automorphism is composed of cube isomorphism and edge flippings for certain directions in USO Polytope