Approximating Robust Parameterized Submodular Function Maximization in Large-Scales

Ruiqi Yang (), Dachuan Xu (), Yanjun Jiang (), Yishui Wang () and Dongmei Zhang
Additional contact information
Ruiqi Yang: Department of Operations Research and Scientific Computing, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing 100124, P. R. China
Dachuan Xu: Department of Operations Research and Scientific Computing, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing 100124, P. R. China
Yanjun Jiang: School of Mathematics and Statistics Science, Ludong University, 186 Hongqi Middle Road, Zhifu District, Yantai, Shandong 264025, P. R. China
Yishui Wang: Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, P. R. China
Dongmei Zhang: School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2019, vol. 36, issue 04, 1-24

Abstract: We study a robust parameterized submodular function maximization inspired by [Mitrović, S, I Bogunovic, A Norouzi-Fard and 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 τ 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 →∞. In the end, we empirically demonstrate the performance of our algorithm on deletion robust support selection problem.

Keywords: Submodular function; robust; stream; approximation algorithm (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595919500222
Access to full text is restricted to subscribers

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:wsi:apjorx:v:36:y:2019:i:04:n:s0217595919500222

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595919500222

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().