Minimizing Ratio of Monotone Non-submodular Functions

doi:10.1007/s40305-019-00244-1

Journal of the Operations Research Society of China ›› 2019, Vol. 7 ›› Issue (3): 449-459.doi: 10.1007/s40305-019-00244-1

所属专题： Discrete optimization

收稿日期:2018-09-24 修回日期:2019-03-03 出版日期:2019-09-30 发布日期:2019-10-08
通讯作者: Dong-Mei Zhang, Yi-Jing Wang, Da-Chuan Xu, Yan-Jun Jiang E-mail:zhangdongmei@sdjzu.edu.cn;yjwang@emails.bjut.edu.cn;xudc@bjut.edu.cn;jyjmath@emails.bjut.edu.cn
基金资助:
Da-Chuan Xu's research was supported by the National Natural Science Foundation of China (No. 11531014). Yan-Jun Jiang was supported by the National Natural Science Foundation of China (No. 11801251). Dong-Mei Zhang was supported by the National Natural Science Foundation of China (No. 11871081).

Minimizing Ratio of Monotone Non-submodular Functions

Yi-Jing Wang¹, Da-Chuan Xu¹, Yan-Jun Jiang^1,2, Dong-Mei Zhang³

1 Department of Information and Operations Research, College of Applied Sciences, Beijing University of Technology, Beijing 100124, China;
2 School of Mathematics and Statistics Science, Ludong University, Yantai 264025, Shandong, China;
3 School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, China

Received:2018-09-24 Revised:2019-03-03 Online:2019-09-30 Published:2019-10-08
Contact: Dong-Mei Zhang, Yi-Jing Wang, Da-Chuan Xu, Yan-Jun Jiang E-mail:zhangdongmei@sdjzu.edu.cn;yjwang@emails.bjut.edu.cn;xudc@bjut.edu.cn;jyjmath@emails.bjut.edu.cn

摘要/Abstract

Abstract: In this paper, we investigate the problem of minimizing the ratio of normalized non-negative monotone non-submodular set function f and normalized non-negative monotone set function g. We take advantage of the greedy technique and get a performance guarantee depending on the generalized curvature and inverse generalized curvature of f, as well as the submodularity ratio of g. Our results generalize the works of Bai et al. (Algorithms for optimizing the ratio of submodular functions. In:Proceedings of the 33rd International Conference on Machine Learning, 2016) and Qian et al. (Optimizing ratio of monotone set functions. In:Proceedings of the 26th International Joint Conference on Artificial Intelligence, 2017).

Key words: Non-submodular, Set functions, Minimizing ratio, Greedy algorithm

中图分类号:

90C27
68W25

. [J]. Journal of the Operations Research Society of China, 2019, 7(3): 449-459.

Yi-Jing Wang, Da-Chuan Xu, Yan-Jun Jiang, Dong-Mei Zhang. Minimizing Ratio of Monotone Non-submodular Functions[J]. Journal of the Operations Research Society of China, 2019, 7(3): 449-459.

参考文献

[1] Hoppe, B., Tardos, É.:The quickest transshipment problem. Math. Oper. Res. 25, 36-62(2000)
[2] Shapley, L.S.:Cores of convex games. Int. J. Game Theory 1, 11-26(1971)
[3] Fujishige, S.:Polymatroidal dependence structure of a set of random variables. Inf. Control 39, 55-72(1978)
[4] Grötschel, M., Lovász, L., Schrijver, A.:The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169-197(1981)
[5] Iwata, S., Fleischer, L., Fujishige, S.:A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4), 761-777(2001)
[6] Kamiyama, N.:A note on submodular function minimization with covering type linear constraints. Algorithmica 80(10), 2957-2971(2018)
[7] Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.:An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14, 265-294(1978)
[8] Nemhauser, G.L., Wolsey, L.A.:Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177-188(1978)
[9] Qian, C., Shi, J.C., Tang, K., Zhou, Z.H.:Constrained monotone k-submodular function maximization using multi-objective evolutionary algorithms with theoretical guarantee. IEEE Trans. Evol. Comput. 22(4), 595-608(2018)
[10] Bian, A.A., Levy, K., Krause, A., Buhmann, J.M.:Continuous dr-submodular maximization:structure and algorithms. In:Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 486-496(2017)
[11] Van Rijsbergen, C.J.:Foundation of evaluation. J. Doc. 30(4), 365-373(1974)
[12] McLachlan, G.:Discriminant Analysis and Statistical Pattern Recognition, vol. 544. Wiley, New York (2004)
[13] Shi, J., Malik, J.:Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. 22, 888-905(2000)
[14] Bai, W., Iyer, R., Wei, K., Bilmes, J.:Algorithms for optimizing the ratio of submodular functions. In:Proceedings of the 33rd International Conference on Machine Learning, pp. 2751-2759(2016)
[15] Kawahara, Y., Nagano, K., Okamoto, Y.:Submodular fractional programming for balanced clustering. Pattern Recogn. Lett. 32, 235-243(2011)
[16] Buchbinder, N., Feldman, M., Naor, J.S., Schwartz, R.:Submodular maximization with cardinality constraints. In:Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1433-1452(2014)
[17] Krause, A., Singh, A., Guestrin, C.:Nearoptimal sensor placements in gaussian processes:theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235-284(2008)
[18] Wei,K.,Iyer,R.,Bilmes,J.:Submodularityindatasubsetselectionandactivelearning.In:Proceedings of the 32th International Conference on Machine Learning, pp. 1954-1963(2015)
[19] Wolsey, L.A.:An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 385-393(1982)
[20] Atamtrk, A., Narayanan, V.:The submodular knapsack polytope. Discrete Optim. 6, 333-344(2009)
[21] Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.:Guarantees for greedy maximization of non-submodular functions with applications. In:Proceedings of the 34th International Conference on Machine Learning, pp. 498-507(2017)
[22] Lawrence, N., Seeger, M., Herbrich, R.:Fast sparse Gaussian process methods:the informative vector machine. In:Proceedings of the 16th International Conference on Neural Information Processing Systems, pp. 625-632(2003)
[23] Qian, C., Shi, J.C., Yu, Y., Tang, K., Zhou, Z.H.:Optimizing ratio of monotone set functions. In:Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 2606-2612(2017)
[24] Das,A.,Kempe,D.:Submodularmeetsspectral:greedyalgorithmsforsubsetselection,sparseapproximation and dictionary selection. In:Proceedings of the 28th International Conference on Machine Learning, pp. 1057-1064(2011)
[25] Conforti, M., Cornuejols, 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, 251-274(1984)
[26] Vondrak, J.:Submodularity and curvature:the optimal algorithm. RIMS Kokyuroku Bessatsu B 23, 253-266(2010)
[27] Bogunovic, I., Zhao, J., Cevher, V.:Robust maximization of non-submodular objectives (2018). arXiv:1802.07073
[28] Iyer, R., Jegelka, S., Bilmes, J.:Curvature and optimal algorithms for learning and minimizing submodular functions. In:Proceedings of the 26th International Conference on Neural Information Processing Systems, pp. 2742-2750(2013)

Minimizing Ratio of Monotone Non-submodular Functions

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价