Minimizing Ratio of Monotone Non-submodular Functions
- PDF / 264,296 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 77 Downloads / 239 Views
Minimizing Ratio of Monotone Non-submodular Functions Yi-Jing Wang1 · Da-Chuan Xu1 · Yan-Jun Jiang1,2 · Dong-Mei Zhang3 Received: 24 September 2018 / Revised: 3 March 2019 / Accepted: 7 March 2019 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2019
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). Keywords Non-submodular · Set functions · Minimizing ratio · Greedy algorithm Mathematics Subject Classification 90C27 · 68W25 This paper is dedicated to Professor Ding-Zhu Du in celebration of his 70th birthday. 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).
B
Dong-Mei Zhang [email protected] Yi-Jing Wang [email protected] Da-Chuan Xu [email protected] Yan-Jun Jiang [email protected]
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
123
Y.-J. Wang et al.
1 Introduction Submodular functions often arise in various fields of operations research, such as discrete optimization [1], game theory [2] and information theory [3]. Grötschel et al. [4] gave the first polynomial algorithm for the minimization of submodular functions. Iwata et al. [5] presented a combinatorial polynomial time algorithm which answered an open problem proposed by [4]. Kamiyama [6] gave a new polynomial time primal–dual algorithm for minimizing submodular functions with covering type linear constraints. Different from submodular minimization problem, maximizing a submodular function is NP-hard. We list briefly some literature on submodular maximization problem with various constraints. Nemhauser et al. [7,8] proposed celebrated results for monotone submodular maximization subject to a cardinality constraint. Recently, Qian et al. [9] provided a new approach to maximize monotone k-submodular functions under a size constra
Data Loading...
