Skip navigation
Please use this identifier to cite or link to this item:
Title: Two Problems In Combinatorial Optimization Under Uncertainty
Authors: Pollner, Tristan
Advisors: Weinberg, Matt
Alon, Noga
Department: Mathematics
Class Year: 2020
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.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File Description SizeFormat 
POLLNER-TRISTAN-THESIS.pdf563.51 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.