Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

School of Mathematics and Statistics, Ningbo University, Ningbo 315211, China

Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China

Show Author Information
Hide Author Information

Abstract

In this paper, we mainly investigate the optimization model that minimizes the cost function such that the cover function exceeds a required threshold in the set cover problem, where the cost function is additive linear, and the cover function is non-monotone approximately submodular. We study the problem under streaming model and propose three bicriteria approximation algorithms. Firstly, we provide an intuitive streaming algorithm under the assumption of known optimal objective value. The intuitive streaming algorithm returns a solution such that its cover function value is no less than $\alpha \mathsf{}\mathrm{(}\mathrm{1}\mathrm{-}\u03f5\mathrm{)}$ times threshold, and the cost function is no more than ${\mathrm{(}\mathrm{2}\mathrm{+}\u03f5\mathrm{)}}^{\mathrm{2}}\mathrm{/}\mathrm{(}{\u03f5}^{\mathrm{2}}\mathsf{}{\omega}^{\mathrm{2}}\mathrm{)}\mathrm{\cdot}\kappa $, where $\kappa $ is a value that we suppose for the optimal solution and $\alpha $ is the approximation ratio of an algorithm for unconstrained maximization problem that we can call directly. Next we present a bicriteria streaming algorithm scanning the ground set multi-pass to weak the assumption that we guess the optimal objective value in advance, and maintain the same bicriteria approximation ratio. Finally we modify the multi-pass streaming algorithm to a single-pass one without compromising the performance ratio. Additionally, we also propose some numerical experiments to test our algorithm’s performance comparing with some existing methods.

No abstract is available for this article. Click the button above to view the PDF directly.

References

[1]

E. J. Barezi, I. D. Wood, P. Fung, and H. R. Rabiee, A submodular feature-aware framework for label subset selection in extreme classification problems, in Proc. 2019 Conf. North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Minneapolis, MN, USA, 2019, pp. 1009–1018.

J. Xu, L. Mukherjee, Y. Li, J. Warner, J. M. Rehg, and V. Singh, Gaze-enabled egocentric video summarization via constrained submodular maximization, in Proc. 2015 IEEE Conf. Computer Vision and Pattern Recognition, Boston, MA, USA, 2015, pp. 2235–2244.

A. Das and D. Kempe, Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection, in Proc. 28^{th} Int. Conf. Int. Conf. Machine Learning, Bellevue, WA, USA, 2011, pp. 1057–1064.

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, Cost-effective outbreak detection in networks, in Proc. 13^{th} ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Jose, CA, USA, 2007, pp. 420–429.

D. Kempe, J. Kleinberg, and É. Tardos, Maximizing the spread of influence through a social network, in Proc. 9^{th} ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Washington, DC, USA, 2003, pp. 137–146.

V. G. Crawford, A. Kuhnle, and M. T. Thai, Submodular cost submodular cover with an approximate oracle, in Proc. 36^{th} Int. Conf. Machine Learning, Long Beach, CA, USA, 2019, pp. 1426–1435.

P. J. Wan, D. Z. Du, P. Pardalos, and W. Wu, Greedy approximations for minimum submodular cover with submodular cost, Comput. Optim. Appl., vol. 45, no. 2, pp. 463–474, 2010.

R. Iyer and J. Bilmes, Submodular optimization with submodular cover and submodular knapsack constraints, in Proc. of the 26th International Conference on Neural Information Processing Systems, Lake Tahoe, UV, USA, pp. 2436–2444, 2013.

A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek, Guarantees for greedy maximization of non-submodular functions with applications, in Proc. 34^{th} Int. Conf. Machine Learning, Sydney, Australia, 2017, pp. 498–507.

T. Friedrich, A. Göbel, F. Neumann, F. Quinzan, and R. Rothenberger, Greedy maximization of functions with bounded curvature under partition matroid constraints, in Proc. 33^{rd} AAAI Conf. Artificial Intelligence, Honolulu, HI, USA, 2019, p. 281.

S. Gong, Q. Nong, W. Liu, and Q. Fang, Parametric monotone function maximization with matroid constraints, J. Glob. Optim., vol. 75, no. 3, pp. 833–849, 2019.

A. Kuhnle, J. D. Smith, V. G. Crawford, and M. T. Thai, Fast maximization of non-submodular, monotonic functions on the integer lattice, in Proc. 35^{th} Int. Conf. Machine Learning, Stockholm, Sweden, 2018, pp. 2791–2800.

C. Harshaw, M. Feldman, J. Ward, and A. Karbasi, Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications, in Proc. 36^{th} Int. Conf. Machine Learning, Long Beach, CA, USA, 2019, pp. 2634–2643.

C. Qian, Multi-objective evolutionary algorithms are still good: Maximizing monotone approximately submodular minus modular functions, arXiv preprint arXiv: 1910.05492, 2019.

A. Norouzi-Fard, A. Bazzi, M. El Halabi, I. Bogunovic, Y. P. Hsieh, and V. Cevher, An efficient streaming algorithm for the submodular cover problem, in Proc. 30^{th} Int. Conf. on Neural Information Processing Systems, Barcelona, Spain, 2016, pp. 4500–4508.

B. Lehmann, D. Lehmann, and N. Nisan, Combinatorial auctions with decreasing marginal utilities, Games Econ. Behav., vol. 55, no. 2, pp. 270–296, 2006.

Y. Wang, D. Du, D, Y. Jiang, and X. Zhang, Non-submodular maximization with matroid and knapsack constraints, Asia-Pacific Journal of Operational Research, vol. 38, no, 5, p. 2140001, 2021.

Wang Y, Yang X, Zhang H, et al. Bicriteria Algorithms for Approximately Submodular Cover Under Streaming Model. Tsinghua Science and Technology, 2023, 28(6): 1030-1040. https://doi.org/10.26599/TST.2022.9010061

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).