Thesis Title:

Resource Allocation and Subset Selection: New Approaches at the Interface between Discrete and Continuous Optimization.

Advisors:

Dr. Mohit Singh, Dr. Sebastian Pokutta, and Dr. Alejandro Toriello.

Committee Members:

Dr. Shabbir Ahmed

Dr. Santosh Vempala (School of Computer Science)

Date and Time: Friday, April 26, 2019, 10:00am

Location: 226A

Abstract:

Resource allocation and subset selection are two of the most relevant classes of problems in the core of Combinatorial Optimization. Over the past decade, there has been an increased interest in these areas due to their significant impact on real-world applications. Online advertising, sharing-economy systems, and kidney exchange are a few examples of the applicability of resource allocation models. On the other hand, data summarization, influence modeling in social networks, and sensor location have extensively motivated the study of subset selection. In this Thesis, we propose new approaches to two classical problems of these areas:  the online bipartite matching problem and the constrained submodular function maximization problem. Our main objectives are: (1) to develop new models and algorithms that provide theoretical guarantees, and (2) to present computational studies that empirically support our theoretical results.

In the first chapter of this Thesis, we present the theoretical background that is needed to understand our results in both problems. We describe the notion of approximation algorithms, competitive analysis and regret analysis. Later we motivate the online bipartite matching and introduce the model considered in this Thesis. Finally, we motivate the constrained submodular maximization problem, we present  some of the previous approaches in the related literature and their corresponding guarantees.

In the second chapter of this Thesis, we present a novel polyhedral approach to the i.i.d. online bipartite matching problem. In this online version one side of the bipartition is fixed and known in advance, while nodes from the other side appear one at a time as i.i.d. realizations of a uniform distribution, and must immediately be matched or discarded. We consider various static relaxations of the polyhedral set of achievable probabilities,  introduce valid inequalities, and discuss when they are facet-defining. We also show how several of these relaxations correspond to ranking policies and their time-dependent generalizations. We finally provide a computational study of these relaxations and policies to determine their empirical performance.

In the third chapter of this Thesis, we focus on dynamic polyhedral relaxations of the i.i.d. online bipartite matching problem. We show how they theoretically dominate the static relaxations from the previous part, and perform a polyhedral study to theoretically examine the strength of the new relaxations. We also discuss how to derive heuristic policies from the dual prices of the relaxations, in a similar fashion to dynamic resource prices used in network revenue management. We demonstrate the empirical quality of these new relaxations and policies via computational experiments.

In the fourth chapter of this Thesis, we consider the robust submodular maximization problem with structured combinatorial constraints. Our approach is applicable to constraints defined by single or multiple matroids, knapsack as well as distributionally robust criteria. We consider both the offline setting where the data defining the problem is known in advance as well as the online setting where the input data is revealed over time. For the offline setting, we give a nearly optimal bi-criteria approximation algorithm that relies on new extensions of the classical greedy algorithm. Later, we provide an efficient version of this algorithm that theoretically performs less function calls than the previous one, at the cost of adding a few more elements to the final solution. We assess the performance of our offline algorithms in three real-world applications. Finally, in a similar manner than the offline setting, for the online variant of the problem we present an algorithm that returns a bi-criteria solution with sub-linear regret.

In the last chapter of this Thesis, we explore the concept of sharpness in submodular maximization. Empirical studies have shown that the performance of the greedy algorithm is substantially better in practice, even though its 1-1/e worst-case guarantee. This raises a natural question of explaining this improved performance of the greedy algorithm. Our goal is to define sharpness for submodular functions as a candidate explanation for this phenomenon. The sharpness criterion is inspired by the concept of strong convexity in convex optimization and its objective is to measure the behavior of the objective function around the set of optimal solutions. We show that the  greedy algorithm provably performs better as the sharpness of the submodular function increases. This improvement ties closely to the faster convergence of the first order methods for strongly convex functions. Lastly, we present an exhaustive computational study to support this theoretical improvement.