Maximizing the Ratio of Monotone DR-Submodular Functions on Integer Lattice

作     者：Sheng-Min-Jie Chen Dong-Lei Du Wen-Guo Yang Sui-Xiang Gao 

作者机构：School of Mathematical SciencesUniversity of Chinese Academy of SciencesBeijing100049China Faculty of ManagementUniversity of New BrunswickFrederictonNBCanada 

出 版 物：《Journal of the Operations Research Society of China》 (中国运筹学会会刊(英文))

年 卷 期：2025年第13卷第1期

页      面：142-160页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：upported by the China Scholarship Council(No.202004910755) supported by the National Natural Science Foundation of China(Nos.12071459 and 11991022) the Fundamental Research Funds for Central Universities(No.E1E40107X2) supported by the Natural Sciences and Engineering Research Council of Canada(No.283106) the National Natural Science Foundation of China(Nos.11771386 and 11728104) 

主　　题：DR-submodular maximization Integer lattice Threshold decrease algorithm 

摘      要：In this work,we focus on maximizing the ratio of two monotone DR-submodular functions on the integer *** is neither submodular nor *** prove that the Threshold Decrease Algorithm is a 1-e^(1-kg)-εapproximation ratio ***,we construct the relationship between maximizing the ratio of two monotone DR-submodular functions and maximizing the difference of two monotone DR-submodular functions on the integer *** on this relationship,we combine the dichotomy technique and Threshold Decrease Algorithm to solve maximizing the difference of two monotone DR-submodular functions on the integer lattice and prove its approximation ratio is f(x)-g(x)≥1-e^(1-kg)f(X^(*))-g(X^(*)).To the best of our knowledge,before us,there was no work to focus on maximizing the ratio of two monotone DR-submodular functions on integer lattice by using the Threshold Decrease Algorithm.