Abstract
We investigate a non-submodular maximization problem subject to a p-independence system constraint, where the non-submodularity of the utility function is characterized by a series of parameters, such as submodularity (supmodularity) ratio, generalized curvature, and zero order approximate submodularity coefficient, etc. Inspired by Feldman et al. [15] who consider a non-monotone submodular maximization with a p-independence system constraint, we extend their Repeat-Greedy algorithm to non-submodular setting. While there is no general reduction to convert algorithms for submodular optimization problems to non-submodular optimization problems, we are able to show the extended Repeat-Greedy algorithm has an almost constant approximation ratio for non-monotone non-submodular maximization.
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: 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 671–680. ACM (2014)
Bian, A.-A., Buhmann, J.-M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. In: 34th International Conference on Machine Learning, pp. 498–507. JMLR (2017)
Bogunovic, I., Zhao, J., Cevher, V.: Robust maximization of non-submodular objectives. In: 21st International Conference on Artificial Intelligence and Statistics, pp. 890–899. Playa Blanca, Lanzarote (2018)
Buchbinder, N., Feldman, M.: Constrained submodular maximization via a non-symmetric technique arXiv:1611.03253 (2016)
Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms 14(3), 32 (2018)
Buchbinder, N., Feldman, M., Naor, J.-S., Schwartz, R.: Submodular maximization with cardinality constraints. In: 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1433–1452. Society for Industrial and Applied Mathematics (2014)
Buchbinder, N., Feldman, M., Seffi, J., Schwartz, R.: A tight linear time \(1/2\)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5), 1384–1402 (2015)
Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740–1766 (2011)
Chen, W., Zhang, H.: Complete submodularity characterization in the comparative independent cascade model. Theor. Comput. Sci. (2018)
Conforti, M., Cornuéjols, G.: Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math. 7(3), 251–274 (1984)
Das, A., Kempe, D.: Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: 28th International Conference on Machine Learning, pp. 1057–1064. Omnipress (2011)
El-Arini, K., Veda, G., Shahaf, D., Guestrin, C.: Turning down the noise in the blogosphere, In: 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 289–298. ACM (2009)
Feige, U.: A threshold of \(\ln n\) for approximating set cover. J. ACM 45(4), 634–652 (1998)
Feige, U., Mirrokni, V.-S., Vondrák, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133–1153 (2011)
Feldman, M., Harshaw, C., Karbasi, A.: Greed is good: near-optimal submodular maximization via greedy optimization. In: 30th Annual Conference on Learning Theory, pp. 758–784. Springer (2017)
Gomes, R., Krause, A.: Budgeted nonparametric learning from data streams. In: 27th International Conference on Machine Learning, pp. 391–398. Omnipress (2010)
Gupta, A., Roth, A., Schoenebeck, G., Talwar, K.: Constrained non-monotone submodular maximization: offline and secretary algorithms. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 246–257. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17572-5_20
Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146. ACM (2003)
Lee, J., Sviridenko, M., Vondrák, J.: Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4), 795–806 (2010)
Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, vol. 1, pp, 510–520. Association for Computational Linguistics (2011)
Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A.: Fast constrained submodular maximization: personalized data summarization. In: 33rd International Conference on Machine Learning, pp. 1358–1366. JMLR (2016)
Nemhauser, G.-L., Wolsey, L.-A., Fisher, M.-L.: An analysis of approximations for maximizing submodular set functions–I. Math. Program. 14(1), 265–294 (1978)
Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41–43 (2004)
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)
Acknowledgments
The first two authors are supported by Natural Science Foundation of China (Nos. 11531014, 11871081). The third author is supported by Natural Sciences and Engineering Research Council of Canada (No. 283106). The fourth author is supported by China Postdoctoral Science Foundation funded project (No. 2018M643233) and Natural Science Foundation of China (No. 61433012). The fifth author is supported by Natural Science Foundation of Shanxi province (No. 201801D121022).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Yang, R., Xu, D., Du, D., Xu, Y., Yan, X. (2019). Maximization of Constrained Non-submodular Functions. In: Du, DZ., Duan, Z., Tian, C. (eds) Computing and Combinatorics. COCOON 2019. Lecture Notes in Computer Science(), vol 11653. Springer, Cham. https://doi.org/10.1007/978-3-030-26176-4_51
Download citation
DOI: https://doi.org/10.1007/978-3-030-26176-4_51
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-26175-7
Online ISBN: 978-3-030-26176-4
eBook Packages: Computer ScienceComputer Science (R0)