Randomized Algorithms to Locate the Sink in Low Dimensional Unique Sink Orientations of Cubes
OPEN ACCESS
Author / Producer
Date
2004-09-18
Publication Type
Student Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
An orientation of the edges of an n-dimensional cube graph such that
every face has a unique sink is called a unique sink
orientation. These orientations provide a powerful framework for
optimization problems, since, for instance, linear and strictly-convex
quadratic programming, as well as many other problems, can be reduced
to the problem of finding the unique sink of a unique sink
orientation. We assume the orientation is implicitly available by
evaluating vertices, that is an algorithm can access the orientations
by choosing vertices for which the orientation of the incident edges
is disclosed. In this setting, an algorithm requiring a polynomial
amount of vertex evaluations (in the dimension n) for finding the sink
could be used for solving linear programs with running time polynomial
in the dimension and in the number of constraints, hence solving a
challenging, and up to now still open, problem.
On the other hand, game theory, and more precisely, the theory of
zero- sum games, provides very powerful tools for the analysis of
randomized algorithms. Making use of this machinery, some relevant
results about optimal randomized algorithms for finding sinks can be
shown, and some insight into this problem can be gained. For instance,
through the use of these techniques, Rote managed to reveal the
existence of a randomized algorithm which requires 1.438^n expected
vertex evaluations in the worst case.
This semester project is an independent verification of Rote’s result,
which is stated above. We formalize the game-theoretic approach for
modeling the problem of finding the sink of a unique sink
orientation. In particular, we prove some properties, mainly related
to symmetries, for optimal algorithms in any dimension, making use of
the sequence form of zero-sum two-player games. These findings allow
us to obtain a linear program, whose solutions are the optimal
algorithms for finding the sink in 3-dimensional cubes. This LP is
much smaller than the one provided by Rote. Moreover, we represent two
distinct optimal strategies, hence showing that the optimal strategy
for finding the sink is not unique. A computer program generating the
LP has also been implemented.
Permanent link
Publication status
published
External links
Editor
Contributors
Examiner : Szabó, Tibor
Examiner : Schurr, Ingo
Book title
Journal / series
Volume
Pages / Article No.
Publisher
ETH Zurich
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
unique sink orientation; optimization; randomized algorithms; zero-sum games
Organisational unit
02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science