Abstract
Two-stage submodular maximization problems have been recently applied in machine learning, economics and engineering. In this paper, we consider a two-stage submodular problem subject to cardinality constraint and matroid constraint. Previous work for this problem usually assume that the objective functions are non-negative and monotone. Our focus in this work relaxes these assumptions by considering an objective function which is the expected difference of a non-negative monotone submodular function and a non-negative monotone modular function, and hence neither non-negative nor monotone. We present strong approximation guarantees by offering two bi-factor approximation algorithms for this problem. The first is a deterministic \(\left( \frac{1}{2}\left( 1-e^{-2}\right) , 1\right) \)-approximation algorithm, and the second is a randomized \(\left( \frac{1}{2}\left( 1-e^{-2}\right) -\epsilon , 1\right) \)-approximation algorithm with improved time efficiency. Moreover, we generalize the matroid constraint to k-matroid constraint and also give the corresponding approximation algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., Krause, A.: Streaming submodular maximization: massive data summarization on the fly. In: KDD, pp. 671–680 (2014)
Balkanski, E., Mirzasoleiman, B., Krause, A., Singer, Y.: Learning sparse combinatorial representations via two-stage submodular maximization. In: ICML, pp. 2207–2216 (2016)
El-Arini, K., Veda, G., Shahaf, D., Guestrin, C.: Turning down the noise in the blogosphere. In KDD, pp. 289–298 (2009)
Epasto, A., Mirrokni, V.S., Zadimoghaddam, M.: Bicriteria distributed submodular maximization in a few rounds. In: SPAA, pp. 25–33 (2017)
Feldman, M.: Guess free maximization of submodular and linear sums. In: Friggstad, Z., Sack, J.-R., Salavatipour, M.R. (eds.) WADS 2019. LNCS, vol. 11646, pp. 380–394. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-24766-9_28
Feldman, M., Harshaw, C., Karbasi, A.: Greed is good: near-optimal submodular maximization via greedy optimization. In: COLT, pp. 758–784 (2017)
Feldman, M., Karbasi, A., Kazemi, E.: Do less, get more: streaming submodular maximization with subsampling. CoRR, abs/1802.07098 (2018). http://arxiv.org/abs/1802.07098 maximization. In: FOCS, pp. 570–579 (2011)
Harshaw, C., Feldman, M., Ward, J., Karbasi, A.: Submodular maximization beyond non-negativity: guarantees, fast algorithms, and applications. In: ICML, pp. 2634–2643 (2019)
Kirchhoff, K., Bilmes, J.: Submodularity for data selection in statistical machine translation. In: EMNLP, pp. 131–141 (2014)
Krause, A., Gomes, R.G.: Budgeted nonparametric learning from data streams. In: ICML, pp. 391–398 (2010)
Kempe, D., Kleinberg, J.M., Tardos, á: Maximizing the spread of influence through a social network. In: KDD, pp. 137–146 (2003)
Krause, A., Guestrin, C.: Near-optimal nonmyopic value of information in graphical models. In: UAI, pp. 324–331 (2005)
Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in MapReduce and streaming. TOPC 2(3), 141–1422 (2015)
Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J. Discrete Math. 23(4), 2053–2078 (2010)
Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondraák, J., Krause, A.: Lazier than lazy greedy. In: AAAI, pp. 1812–1818 (2015)
Mirzasoleiman, B., Karbasi, A., Badanidiyuru, A., Krause, A.: Distributed submodular cover: succinctly summarizing massive data. In: NIPS, pp. 2881–2889 (2015)
Mirzasoleiman, B., Karbasi, A., Sarkar, R., Krause, A.: Distributed submodular maximization: identifying representative elements in massive data. In: NIPS, pp. 2049–2057 (2013)
Mitrovic, M., Kazemi, E., Zadimoghaddam, M., Karbasi, A.: Data summarization at scale: a two-stage submodular approach. In: ICML, pp. 3593–3602 (2018)
Lin, H., Bilmes, J.A.: Multi-document summarization via budgeted maximization of submodular functions. In: HLT-NAACL, pp. 912–920 (2010)
Schrijver, A.: Combinatorial Optimization-Polyhedra and Efficiency. Springer, Berlin (2003)
Singla, A., Bogunovic, I., Bartok, G., Karbasi, A., Krause, A.: Near-optimally teaching the crowd to classify. In: ICML, pp. 154–162 (2014)
Stan, S., Zadimoghaddam, M., Krause, A., Karbasi, A.: Probabilistic submodular maximization in sub-linear time. In: ICML, pp. 3241–3250 (2017)
Sviridenko, M., Vondrák, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4), 1197–1218 (2017)
Acknowledgements
This research is supported or partially supported by the National Natural Science Foundation of China (Grant Nos. 11871280, 11501171, 11771251, 11971349, 11771386 and 11728104), the Natural Sciences and Engineering Research Council of Canada (NSERC) Grant 06446 and Qinglan Project.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Liu, Z., Chang, H., Ma, R., Du, D., Zhang, X. (2020). Two-Stage Submodular Maximization Problem Beyond Non-negative and Monotone. In: Chen, J., Feng, Q., Xu, J. (eds) Theory and Applications of Models of Computation. TAMC 2020. Lecture Notes in Computer Science(), vol 12337. Springer, Cham. https://doi.org/10.1007/978-3-030-59267-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-59267-7_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-59266-0
Online ISBN: 978-3-030-59267-7
eBook Packages: Computer ScienceComputer Science (R0)