版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.