Robust Adaptive Submodular Maximization

Shaojie Tang ()
Additional contact information
Shaojie Tang: Naveen Jindal School of Management, The University of Texas at Dallas, Richardson, Texas 75080

INFORMS Journal on Computing, 2022, vol. 34, issue 6, 3277-3291

Abstract: The goal of a sequential decision-making problem is to design an interactive policy that adaptively selects a group of items, each selection is based on the feedback from the past, to maximize the expected utility of selected items. It has been shown that the utility functions of many real-world applications are adaptive submodular. However, most of existing studies on adaptive submodular optimization focus on the average-case, that is, their objective is to find a policy that maximizes the expected utility over a known distribution of realizations. Unfortunately, a policy that has a good average-case performance may have very poor performance under the worst-case realization. In this study, we propose to study two variants of adaptive submodular optimization problems, namely, worst-case adaptive submodular maximization and robust submodular maximization. The first problem aims to find a policy that maximizes the worst-case utility and the latter one aims to find a policy, if any, that achieves both near optimal average-case utility and worst-case utility simultaneously. We introduce a new class of stochastic functions, called worst-case submodular function . For the worst-case adaptive submodular maximization problem subject to a p -system constraint, we develop an adaptive worst-case greedy policy that achieves a 1 p + 1 approximation ratio against the optimal worst-case utility if the utility function is worst-case submodular. For the robust adaptive submodular maximization problem subject to cardinality constraints (respectively, partition matroid constraints), if the utility function is both worst-case submodular and adaptive submodular, we develop a hybrid adaptive policy that achieves an approximation close to 1 − e − 1 2 (respectively, 1/3) under both worst- and average-case settings simultaneously. We also describe several applications of our theoretical results, including pool-base active learning, stochastic submodular set cover, and adaptive viral marketing.

Keywords: submodular maximization; stochastic optimization; approximation algorithms (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1239 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:6:p:3277-3291

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().