Indexed by:
Abstract:
We study a robust parameterized submodular function maximization inspired by [Mitrovic, S, I Bogunovic, A Norouzi-Fardand Jakub Tarnawski (2017). Streaming robust submodular maximization: A partitioned thresholding approach. In Proc. NIPS, pp. 4560-4569] and [Bogunovic, I, J Zhao and V Cevher (2018). Robust maximization of nonsubmodular objectives. In Proc. AISTATS, pp. 890-899]. In our setting, given a parameterized set function, there are two additional twists. One is that elements arrive in a streaming style, and the other is that there are at most tau items deleted from the algorithm's memory when the stream is finished. The goal is to choose a robust set from the stream such that the robust ratio is maximized. We propose a two-phase algorithm for maximizing a normalized monotone robust parameterized submodular function with a cardinality constraint and show the robust ratio is close to a constant as k -> infinity. In the end, we empirically demonstrate the performance of our algorithm on deletion robust support selection problem.
Keyword:
Reprint Author's Address:
Email:
Source :
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH
ISSN: 0217-5959
Year: 2019
Issue: 4
Volume: 36
1 . 4 0 0
JCR@2022
ESI Discipline: ENGINEERING;
ESI HC Threshold:136
Cited Count:
WoS CC Cited Count: 10
SCOPUS Cited Count: 10
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 5
Affiliated Colleges: