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

Special Issue: Discrete optimization

Previous Articles Next Articles

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

CLC Number:

90C27
68W25

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.

TrendMD

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 5

Recommended Articles

Metrics

Comments

[1]	Jiang Hu, Xin Liu, Zai-Wen Wen, Ya-Xiang Yuan. A Brief Introduction to Manifold Optimization [J]. Journal of the Operations Research Society of China, 2020, 8(2): 199-248.
[2]	Min Li, Dong-Lei Du, Da-Chuan Xu, Zhen-Ning Zhang. A Note on Submodularity Preserved Involving the Rank Functions [J]. Journal of the Operations Research Society of China, 2019, 7(3): 399-407.
[3]	Yao Xu, Yong Chen, Peng Zhang, Randy Goebel. Approximation Algorithms for Vertex Happiness [J]. Journal of the Operations Research Society of China, 2019, 7(3): 429-448.
[4]	Long Wan, Jin-Jiang Yuan. Simultaneous Approximation Ratios for Parallel Machine Scheduling Problems [J]. Journal of the Operations Research Society of China, 2019, 7(3): 485-500.
[5]	Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu. Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan [J]. Journal of the Operations Research Society of China, 2019, 7(2): 303-319.