Maximization of monotone non-k-submodular set function with noise under matroid constraints
简介：Submodular optimization is primarily applied in multi-agent systems for tasks such as resource allocation,task assignment,collaborative decision-making,and optimization problems.Maximiza-tion of optimizing submodular set functions attracts much attention since the 1970s.A large body of work has been done using approximation algorithms.When the dimension of the independent varia-ble of the set function changes from one to k,it is called a k-submodular set function.The k-subm-odular set function,a generalization of the classical submodular set function,arises in diverse fields with varied applications.In many practical scenarios,quantifying the degree of closeness to submod-ularity becomes essential,leading to concepts such as approximately submodular set functions and the diminishing-return(DR)ratio.This paper investigates a k-dimensional set function under ma-troid constraints,which may lack full submodularity.Instead,we focus on an approximately non-k-submodular set function characterized by its DR ratio.Employing a greedy algorithmic approach,we derive an approximation guarantee for this problem.Notably,when the DR ratio is set to one,our results align with existing findings in the literature.Experimental results demonstrate the superiority of our algorithm over the baselines.展开
学者：JIANGYanjunWangYijingYangRuiqiLIAli
关键词：k-submodular set functiongreedymatroid constraintsapproximation algorithm
在线出版日期：2026-04-17 （网站首发日期）
