Submodular functions, which are a natural discrete analog of convex/concave functions, strike a sweet spot between generality and structure: they model an immense variety of applications in computer science and beyond, but, at the same time, are sufficiently well behaved that they can be optimized very effectively in theory and in practice. Optimization tasks involving submodular functions have classically been studied in settings of complete information, i.e. where the entire input is knownupfront. However, such perfect, full-information access to the input is unrealistic in many applications, and indeed designing algorithms under uncertainty has become an important trend in modern computer science.

In this thesis, we study algorithms for submodular optimization in scenarios with incomplete information. We study three different kinds of uncertain environments:

(a) Online settings where problem constraints are revealed piecemeal and the al- gorithm must commit to irrevocable decisions as it maintains feasibility. The challenge is to make decisions that are robust to the final realization of the problem, even with limited information.

(b) Dynamic settings where constraints can not only be added but also removed over time. The goal is to design algorithms that maintain feasible, near optimal solutions at every stage that are stable, in the sense that they change as little as possible between time steps.

(c) Streaming settings where the input is too large to hold in memory all at once.The algorithm must adequately solve problems with only limited memory after one (or few) sequential passes over the data.

Prior to our work, no algorithms were known for several important instances of submodular optimization in uncertain environments; we improve known algorithms for others. In a few cases we apply insights from these submodular optimization algorithms to problems that are not on their surface related to submodularity. We hope that the techniques we develop find uses elsewhere.

175 pages

Thesis Committee:
Anupam Gupta (Chair)
R. Ravi
David Woodruff
Chandra Chekuri (University of Illinois, Urbana-Champaign)
Joseph (Seffi) Naor (Technion)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu