×

Two approximation algorithms for maximizing nonnegative weakly monotonic set functions. (English) Zbl 1510.90222

Summary: Many combinatorial optimization problems can be reduced to submodular optimization problems. However, many cases in practical applications do not fully comply with the diminishing returns characteristic. This paper studies the problem of maximizing weakly-monotone non-submodular non-negative set functions without constraints, and extends the normal submodular ratio to weakly-monotone submodular ratio \(\widehat{\gamma } \). In this paper, two algorithms are given for the above problems. The first one is a deterministic greedy approximation algorithm, which realizes the approximation ratio of \(\frac{\widehat{\gamma }}{\widehat{\gamma }+2} \). When \(\widehat{\gamma }=1\), the approximate ratio is 1/3, which matches the ratio of the best deterministic algorithm known for the maximization of submodular function without constraints. The second algorithm is a random greedy algorithm, which improves the approximation ratio to \(\frac{\widehat{\gamma }}{\widehat{\gamma }+1} \). When \(\widehat{\gamma }=1\), the approximation ratio is 1/2, the same as the best algorithm for the maximization of unconstrained submodular set functions.

MSC:

90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmed, S.; Atamtürk, A., Maximizing a class of submodular utility functions, Math Program, 128, 1, 149-169 (2011) · Zbl 1218.90221 · doi:10.1007/s10107-009-0298-1
[2] Attigeri, G.; Manohara, PMM; Radhika, MP, Feature selection using submodular approach for financial big data, J Inform Process Syst, 15, 6, 1306-1325 (2019)
[3] Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: massive data summarization on the fly. In: Proceedings of the 20th International Proceedings on Knowledge discovery and data mining, pp.671-680
[4] Bian AA, Buhmann JM, Krause A, Tschiatschek S (2017) Guarantees for Greedy maximization of non-submodular functions with applications. In: Proceedings of the 35th International Conference on Machine Learning, 70: pp.498-507
[5] Buchbinder, N.; Feldman, M.; Naor, JS; Schwartz, R., A tight linear time (1/2)-approximation for unconstrained submodular maximization, SIAM J Comput, 44, 5, 1384-1402 (2015) · Zbl 1330.68346 · doi:10.1137/130929205
[6] Buchbinder N, Feldman M, Schwartz R (2015b) Online submodular maximization with preemption. In: Proceedings of the 26th International Symposium on Discrete Algorithms, pp.1202-1216 · Zbl 1371.68328
[7] Buchbinder N, Feldman M (2016) Deterministic algorithms for submodular maximization problems, In: Proceedings of the 27th International Symposium on Discrete Algorithms, pp.392-403 · Zbl 1411.68177
[8] Cherenin V (1962) Solving some combinatorial problems of optimal planning by the method of successive calculations. In: Proceedings of Experiences and Perspectives of the Applications of Mathematical Methods and Electronic Computers in Planning
[9] Coelho, VN; Oliveira, TA; Coelho, IM; Coelho, BN; Fleming, PJ; Guimarães, FG; Ramalhinho, H.; Souza, MJF; Talbi, E-G; Lust, T., Generic pareto local search metaheuristic for optimization of targeted offers in a bi-objective direct marketing campaign, Comput Oper Res, 78, 578-587 (2017) · Zbl 1391.90508 · doi:10.1016/j.cor.2016.09.008
[10] Das A, Kempe D (2011) Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection. In: Proceedings of the 28th International Conference on Machine Learning, pp.1057-1064
[11] Dobzinski S, Vondrak J (2012) From query complexity to computational complexity. In: Proceedings of the 44th International Symposium on Theory of Computing, pp.1107-1116 · Zbl 1286.68225
[12] Dughmi S (2009) Submodular functions: Extensions, distributions, and algorithms. a survey, arXiv preprint arXiv:0912.0322
[13] Feige, U.; Mirrokni, VS; Vondrák, J., Maximizing non-monotone submodular functions, SIAM J Comput, 40, 4, 1133-1153 (2011) · Zbl 1230.90198 · doi:10.1137/090779346
[14] Feldman M, Naor J, Schwartz R (2011) Nonmonotone submodular maximization via a structural continuous greedy algorithm. In: Proceedings of the 38th International Colloquium Conference on Automata, Languages and Programming, 6755, pp.342-353 · Zbl 1332.68285
[15] Galbiati, G.; Maffioli, F., Approximation algorithms for maximum cut with limited unbalance, Theoret Comput Sci, 385, 1, 78-87 (2007) · Zbl 1124.68117 · doi:10.1016/j.tcs.2007.05.036
[16] Gharan SO, Vondrák J (2011) Submodular maximization by simulated annealing. In: Proceedings of the 22nd International Symposium on Discrete Algorithms, pp.1098-1116 · Zbl 1377.90073
[17] Golovin, D.; Krause, A., Adaptive submodularity: theory and applications in active learning and stochastic optimization, J Artif Intell Res, 42, 1, 427-486 (2010) · Zbl 1230.90141
[18] Gong, S.; Nong, Q.; Liu, W.; Fang, Q., Parametric monotone function maximization with matroid constraints, J Global Optim, 75, 3, 833-849 (2019) · Zbl 1432.90133 · doi:10.1007/s10898-019-00800-2
[19] Halperin E, Zwick U (2001) Combinatorial approximation algorithms for the maximum directed cut problem. In: Proceedings of the 12th International Symposium on Discrete Algorithms, pp. 1-7 · Zbl 1018.90039
[20] Hartline J, Mirrokni V, Sundararajan M (2008) Optimal marketing strategies over social networks. In: Proceedings of the 17th International Proceedings on World Wide Web, pp.189-198
[21] Hazan, E.; Kale, S., Online submodular minimization, J Mach Learn Res, 13, 2903-2922 (2012) · Zbl 1433.68347
[22] Jegelka S, Bilmes JA (2011) Online Submodular Minimization for Combinatorial Structures. In: Proceedings of the 28th International Conference on Machine Learning, pp.345-352
[23] Kawahara, Y.; Nagano, K.; Okamoto, Y., Submodular fractional programming for balanced clustering, Pattern Recogn Lett, 42, 2, 235-243 (2011) · doi:10.1016/j.patrec.2010.08.008
[24] Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence through a social network, Theory Comput, 11, 1, 105-147 (2015) · Zbl 1337.91069 · doi:10.4086/toc.2015.v011a004
[25] Krause A, Guestrin C (2007) Near-optimal observation selection using submodular functions. In: Proceedings of the 22nd International Conference on Artificial Intelligence, 7, pp.1650-1654
[26] Lin Y, Chen W, Lui JC (2017) Boosting Information Spread: An Algorithmic Approach. In: Proceedings of the International Conference on Data Engineering, pp.883-894
[27] Mansell R, Collins BS (2005) Introduction: Trust and crime in information societies. Edward Elgar, pp. 1-10
[28] Melo, MT; Nickel, S.; Saldanha-da-Gama, F., Facility location and supply chain management-a review, Eur J Oper Res, 196, 2, 401-412 (2009) · Zbl 1163.90341 · doi:10.1016/j.ejor.2008.05.007
[29] Milgrom P, Milgrom PR (2004) Putting auction theory to work. Cambridge University Press · Zbl 1201.91081
[30] Mossel E, Roch S (2007) On the submodularity of influence in social networks. In: Proceedings of the 30th International Symposium on Theory of Computing, pp.128-134 · Zbl 1232.68183
[31] Parambath SA, Chawla S, Vijayakumar N (2018) SAGA: A Submodular Greedy Algorithm for Group Recommendation, In: Proceedings of International Conference on Artificial Intelligence, pp.3900-3908
[32] Roughgarden T, Wang J (2018) An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization. In: Proceedings of the 31st International Conference on Learning Theory, 75, pp.1307-1325
[33] Streeter M, Golovin D (2008) An online algorithm for maximizing submodular functions. In: Proceedings of the 22nd International Conference on Neural Information Processing Systems, pp.1577-1584
[34] Tran, AK; Piran, MJ; Pham, C., SDN controller placement in IoT networks: an optimized submodularity-based approach, Sensors, 19, 24, 5474 (2019) · doi:10.3390/s19245474
[35] Tsai, Y-C; Tseng, K-S, Deep compressed sensing for learning submodular functions, Sensors, 20, 9, 2591 (2020) · doi:10.3390/s20092591
[36] Wei K, Iyer R, Bilmes JA (2015) Submodularity in data subset selection and active learning. In: Proceedings of the 32nd International Conference on Machine Learning, 37, pp.1954-1963
[37] Zhang H, Vorobeychik Y (2016) Submodular optimization with routing constraints. In: Proceedings of the 30th International Proceedings on Artificial Intelligence, pp. 819-825
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.