Committee:
Prof. Shuchi Chawla (advisor)
Prof. Eric Bach
Prof. Jin-Yi Cai
Prof. Marzena Rostek
Prof. Jason Hartline (Northwestern university)
Abstract: The focus of this thesis is optimization in the presence of uncertain inputs. In a broad class of algorithmic problems, uncertainty is modeled as input being drawn from one among a large known universe of distributions, however the specific distribution is unknown to the algorithm. The goal then is to develop a single algorithm that for every distribution in this universe, performs approximately as well as the optimal algorithm tailored for that specific distribution. Such algorithms are robust to assumptions on prior distributions.
Prior robust optimization retains the robustness of worst-case analysis while going beyond the pessimistic impossibility results of worst-case analysis. Apart from this theoretical appeal, the ability to use the same algorithm for every prior distribution makes prior robust algorithms well-suited for deployment in real systems. Indeed, most prior robust algorithms in literature are simple to implement and some of them have been observed to perform well in large-scale systems.
In this thesis, we design and analyze prior robust algorithms in two distinct areas of research: online algorithms and mechanism design. In online algorithms, we use a hybrid argument to develop near optimal online algorithms for a general framework of problems, called the resource allocation framework, with several well motivated applications to Internet ad serving. In mechanism design, we use sampling and supply limitation techniques to develop prior robust truthful approximately revenue optimal auctions, and the first prior robust
truthful mechanisms for approximate makespan minimization in machine
scheduling.