Geometric Optimization and Unique Sink Orientations of Cubes
METADATA ONLY
Loading...
Author / Producer
Date
2004
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
There is an ongoing attempt of designing a provably fast method for solving Linear Programs and related geometric optimization problems by combinatorial methods in the unit cost model (as opposed to the bit-model, where polynomial methods are known). Among others, this research has brought forth randomized methods with subexponential running time, but also a number of interesting combinatorial models like Oriented Matroids, Abstract Objective Functions (AOF), Unimodal Numberings, LP-type Problems, Abstract Optimization Problems (AOP), Unique Sink Orientations of Cubes (USO), et cetera. Although many of these models are quite general, so far there has been little success in showing good lower bounds even in these generalized abstractions. As for the simplex method, there are a number of open questions concerning several pivoting rules, notably randomized ones.
After a general introduction, we will focus on one particular model: unique sink orientations of cubes (USO). To this end consider (the edge graph of) an n-dimensional hypercube with its edges oriented so that every face has a unique sink. Such an orientation is called a unique sink orientation, and we are interested in finding the unique sink of the whole cube when the orientation is given implicitly. The basic operation available is the so-called vertex evaluation, where we can access an arbitrary vertex of the cube, for which we obtain the orientations of the incident edges.
Unique sink orientations occur when the edges of a deformed geometric n-dimensional cube (i.e., a polytope with the combinatorial structure of a cube) are oriented according to some generic linear function. These orientations are easily seen to be acyclic. The main motivation for studying unique sink orientations are certain linear complementarity problems, which allow this combinatorial abstraction (due to Alan Stickney and Layne Watson), where orientations with cycles can arise. Similarly, linear programming and some quadratic optimization problems, like computing the smallest enclosing ball of a finite point set, are polynomial time reducible (in the unit cost model) to finding a sink in a unique sink orientation (possibly with cycles).
The talk surveys some results concerning upper and lower bounds for algorithms finding the sink in a USO (acyclic or possibly with cycles).
Permanent link
Publication status
published
External links
Book title
Mathematical Foundations of Computer Science 2004. MFCS 2004
Journal / series
Volume
3153
Pages / Article No.
176 - 176
Publisher
Springer
Event
29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004)