Name
Abstract | ||
|---|---|---|
Constrained submodular maximization has been extensively studied in the recent years. In this paper, we study adaptive robust optimization with nearly submodular structure (ARONSS). Our objective is to randomly select a subset of items that maximizes the worst-case value of several reward functions simultaneously. Our work differs from existing studies in two ways: (1) we study the robust optimization problem under the adaptive setting, i.e., one needs to adaptively select items based on the feedback collected from picked items, and (2) our results apply to a broad range of reward functions characterized by $\epsilon$-nearly submodular function. We first analyze the adaptvity gap of ARONSS and show that the gap between the best adaptive solution and the best non-adaptive solution is bounded. Then we propose two algorithms that achieve bounded approximation ratios. |
Year | Venue | DocType |
|---|---|---|
2019 | arXiv: Learning | Journal |
Volume | Citations | PageRank |
abs/1905.05339 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tang Shaojie | 1 | 2224 | 157.73 |
| Jing Yuan | 2 | 237 | 11.92 |