Submodular optimization in massive datasets
Abstract/Contents
- Abstract
- In this thesis, we study the problem of submodular maximization in various ``massive data" models, namely the MapReduce, streaming, and adaptive models. For the MapReduce model, we give a simple $O(1/\varepsilon)$-round algorithm for maximizing a monotone submodular function with respect to a cardinality constraint. This algorithm achieves an optimal $1-1/e$ approximation ratio, is simple to implement in practice, and removes the data duplication issue of prior works obtaining the same approximation ratio. For the streaming model, we study both the random order and the adversarial order settings. In both settings, we give the first multi-pass approximation algorithm for maximizing monotone submodular functions with respect to a matroid constraint. Our algorithms achieve $1-1/e-\eps$ approximations in $poly(1/\eps)$ passes. For the adversarial case, it is known that our algorithm is tight -- it is impossible to achieve better than a $1/2$ approximation in a single pass, and anything better than $1-1/e$ requires linearly many passes. Our techniques also allows us to develop single pass and multi-pass algorithms for the $p$-matchoid constraint, which generalizes the popular matroid ($p=1$) and intersection-of-matroids constraint ($p=2$). In the adaptive model, we study the problem of maximizing an unconstrained non-monotone submodular function. We show the following: for any problem instance, and every $\delta > 0$, either we obtain a $(1/2-\delta)$-approximation in 1 round, or a $(1/2 + \Omega(\delta^2))$-approximation in $\Omega(1/\delta^2)$ rounds. In particular (and in contrast to known lower bounds for the monotone cardinality constrained case), there cannot be an instance where (i) it is impossible to achieve an approximation factor better than $1/2$ regardless of the number of rounds, and (ii) it takes $r$ rounds to achieve a factor of $1/2-O(1/r)$.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Liu, Paul |
|---|---|
| Degree supervisor | Charikar, Moses |
| Degree supervisor | Vondrak, Ján, (Mathematician) |
| Thesis advisor | Charikar, Moses |
| Thesis advisor | Vondrak, Ján, (Mathematician) |
| Thesis advisor | Rubinstein, Aviad |
| Degree committee member | Rubinstein, Aviad |
| Associated with | Stanford University, Computer Science Department |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Paul Liu. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/vw164nb4193 |
Access conditions
- Copyright
- © 2022 by Paul Liu
- License
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
Also listed in
Loading usage metrics...