RefWkly16-06-24.pdf

Abstract

This thesis improves upon existing lower and upper bounds for questions in the paradigm of combinatorial optimization under uncertainty. We address problems in two distinct areas. Firstly, we consider the query complexity of submodular function minimization: given oracle access to an unknown submodular \(f: \mathcal{P}([n]) \rightarrow \mathbb{R}\), what is the minimum number of queries needed to deterministically compute \(\min_{S} f(S)\) and some element of \(\arg \min_{S} f(S)\)? In the case that \(f\) is symmetric, the previous best lower bound for non-trivial minimization was \(n\) queries due to Harvey; we improve this to \({\sim} 1.5n\) via a novel concept we call the cut dimension. We secondly consider questions in the area of prophet inequalities, focusing on problems that arise when feasibility constraints are given by a matroid or an intersection of matroids --- a very important and well-studied setting in the literature. In the case of bipartite matching (an example of feasibility constraints given by the intersection of two matroids), we improve the previous lower bound of 2.25 for the best possible competitive ratio (due to Gravin and Wang) to \(7/3\). When feasibility constraints are given by matroids of large girth, we resolve the previously open question of the best possible competitive ratio by showing that it is precisely 2. And finally, in the case where feasibility constraints are given by an intersection of \(p\) partition matroids (generalizing bipartite matching), we provide an algorithm which is \((p+1)\)-competitive, improving on the previously best-known \(({\sim} ep)\)-competitive algorithm due to Feldman, Svensson, and Zenklusen.