Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Optimal randomized strategies for unique sink orientations of the 3-cube

Optimal randomized strategies for unique sink orientations of the 3-cube

Abstract.

The optimal randomized strategy for finding a sink in a unique sink orientation can be modeled as a two-player zero-sum game, which can then be solved as a linear programming problem. I describe how I had to simplify the problem so that the computer could find an optimal strategy on the 3d-cube.

Resources.