Research Focus
|
Most of my research concerns Unique Sink Orientations (short USOs). USOs are a combinatorial abstraction of many geometric and algebraic optimization problems with real-world applications, like Linear Programming, P-Matrix Linear Complementarity, Minimum Enclosing Ball, or Quadratic Programming. A USO is an orientation of a hypercube graph, with the property that every sub-cube has a unique sink (read: a vertex with all adjacent edges pointing towards it). The algorithmic problem that is associated with a USO is the one of finding the unique global sink. Such an algorithm can make use of a vertex-evaluation oracle, which can be queried with a vertex and returns the directions of the adjacent edges. The complexity of the algorithm is measured in the number of performed oracle queries. |
|
I approach Unique Sink Orientations from three main directions:
Structure:
If we better understand the structure of USOs, we can design better Algorithms or come up with better instances to derive lower bounds. Here we focus on the structure of general USOs, but also of algebraically derived subclasses of USOs (e.g. those which arise from Linear Programming), and also on combinatorially defined subclasses.
We also want to link the theory of USOs to other combinatorial abstractions of the same source problems, in particular Oriented Matroids.
Constructions:
There exist many candidate algorithms for sink-finding in USOs. Many are simplex-type algorithms similar to algorithms for Linear Programming. The analysis of such algorithms is not simple, and often times their runtime can only be "sandwiched" between some lower and upper bound.
In some cases, like with the Random Facet algorithm, the lower and upper bound are far apart. To close this gap, better lower bounds could maybe be derived. Most lower bounds for sink-finding algorithms have historically been found using a series of concrete USOs, which can be shown to lead to high runtimes.
Sadly, the toolbox to create high-dimensional USOs is very limited. In this part of my research, I want to find more ways of creating larger USOs from smaller USOs, with the hopes of being able to use these new tools to obtain better lower bounds for some algorithms.
Algorithms:
Lastly, we want to harness the results from the other two research parts, and use them to come up with better algorithms for sink-finding, or to show that known algorithms are either fast or slow.
The "holy grail" of my research is to either find a subexponential algorithm for sink-finding in general USOs, or to show that sink-finding in a USO is strictly harder than solving the source problem leading to the USO.