Journal Home > Volume 28 , Issue 6

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 α(1-ϵ) times threshold, and the cost function is no more than (2+ϵ)2/(ϵ2ω2)κ, where κ is a value that we suppose for the optimal solution and α 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.


menu
Abstract
Full text
Outline
About this article

Bicriteria Algorithms for Approximately Submodular Cover Under Streaming Model

Show Author's information Yijing Wang1Xiaoguang Yang1( )Hongyang Zhang2Yapu Zhang3
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

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 α(1-ϵ) times threshold, and the cost function is no more than (2+ϵ)2/(ϵ2ω2)κ, where κ is a value that we suppose for the optimal solution and α 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.

Keywords: streaming model, approximately submodular, linear additive, bicriteria algorithm

References(20)

[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.
[2]
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.
[3]
A. Das and D. Kempe, Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection, in Proc. 28th Int. Conf. Int. Conf. Machine Learning, Bellevue, WA, USA, 2011, pp. 1057–1064.
[4]
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, Cost-effective outbreak detection in networks, in Proc. 13th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Jose, CA, USA, 2007, pp. 420–429.
[5]
D. Kempe, J. Kleinberg, and É. Tardos, Maximizing the spread of influence through a social network, in Proc. 9th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Washington, DC, USA, 2003, pp. 137–146.
[6]
V. G. Crawford, A. Kuhnle, and M. T. Thai, Submodular cost submodular cover with an approximate oracle, in Proc. 36th Int. Conf. Machine Learning, Long Beach, CA, USA, 2019, pp. 1426–1435.
[7]
L. A. Wolsey, An analysis of the greedy algorithm for the submodular set covering problem, Combinatorica, vol. 2, no. 4, pp. 385–393, 1982.
[8]
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.
[9]
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.
[10]
A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek, Guarantees for greedy maximization of non-submodular functions with applications, in Proc. 34th Int. Conf. Machine Learning, Sydney, Australia, 2017, pp. 498–507.
[11]
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. 33rd AAAI Conf. Artificial Intelligence, Honolulu, HI, USA, 2019, p. 281.
[12]
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.
[13]
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. 35th Int. Conf. Machine Learning, Stockholm, Sweden, 2018, pp. 2791–2800.
[14]
C. Harshaw, M. Feldman, J. Ward, and A. Karbasi, Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications, in Proc. 36th Int. Conf. Machine Learning, Long Beach, CA, USA, 2019, pp. 2634–2643.
[15]
C. Qian, Multi-objective evolutionary algorithms are still good: Maximizing monotone approximately submodular minus modular functions, arXiv preprint arXiv: 1910.05492, 2019.
[16]
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. 30th Int. Conf. on Neural Information Processing Systems, Barcelona, Spain, 2016, pp. 4500–4508.
[17]
B. Lehmann, D. Lehmann, and N. Nisan, Combinatorial auctions with decreasing marginal utilities, Games Econ. Behav., vol. 55, no. 2, pp. 270–296, 2006.
[18]
U. Feige, V. S. Mirrokni, and J. Vondrák, Maximizing non-monotone submodular functions, SIAM J. Comput., vol. 40, no. 4, pp. 1133–1153, 2011.
[19]
V. G. Crawford, Scalable bicriteria algorithms for non-monotone submodular cover, arXiv preprint arXiv: 2112.09985, 2021.
[20]
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.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 02 August 2022
Revised: 24 October 2022
Accepted: 28 November 2022
Published: 28 July 2023
Issue date: December 2023

Copyright

© The author(s) 2023.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Nos. 72192804, 72192800, and 12201619) and the China Postdoctoral Science Foundation (No. 2022M723333).

Rights and permissions

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/).

Return