Thursday, August 9, 2018 - 4:00pm
Location:Traffic21 Classroom 6501 Gates Hillman Centers
Speaker:DAVID WAJC, Ph.D. Student http://www.cs.cmu.edu/~dwajc/
Matching Algorithms Under Uncertainty, and Matching Lower Bounds
Uncertainty is all around us. Constantly-changing circumstances make pre- diction of future events difficult, if not impossible. On the other hand, lack of exact information (and even spread of disinformation) make attaining a com- plete picture of the present a near-unattainable goal. This uncertainty makes optimizing for all eventualities a seemingly paradoxical objective. Nonethe- less, we should strive to overcome the challenges presented by this incomplete information, to the best of our abilities. The goal of this thesis is to tackle uncertainty for various problems, many of which stem from matching theory – a field of graph theory that has in- spired many fundamental techniques and approaches of algorithm design. One such fundamental contribution of matching theory is a side-note in the seminal work of Edmonds in 1965. In his paper presenting the first polynomial-time maximum matching algorithm
for general graphs, Edmonds (in a section titled “digression”) advocated for polynomial-time computability as a notion of effi- ciency of algorithms in the classic full-certainty model of computation. Under uncertainty, polynomial-time computability remains an important measure of efficiency, but by no means the only one – many such measures of efficiency are pertinent when attempting to quantify the cost which uncertainty must in- evitably incur. In this thesis I will strive to obtain efficient, and ideally optimal, algorithms for multiple models of computation under uncertainty, including on- line algorithms and dynamic algorithms, among others.
Cliff Stein (Columbia University)
Ola Svensson (École polytechnique fédérale de Lausanne)