Adaptive Robust Optimization with Nearly Submodular Structure
share
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 ϵ-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.
READ FULL TEXT