Submodular optimization is primarily applied in multi-agent systems for tasks such as resource allocation,task assignment,collaborative decision-making,and optimization problems.Maximization of optimizing submodular s...Submodular optimization is primarily applied in multi-agent systems for tasks such as resource allocation,task assignment,collaborative decision-making,and optimization problems.Maximization 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 variable of the set function changes from one tok,it is called ak-submodular set function.Thek-submodular 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 submodularity becomes essential,leading to concepts such as approximately submodular set functions and the diminishing-return(DR) ratio.This paper investigates ak-dimensional set function under matroid constraints,which may lack full submodularity.Instead,we focus on an approximately non-ksubmodular 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.展开更多
In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint.In order to reduce the complexity of this algorithm,we al...In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint.In order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm failure.Moreover,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.展开更多
A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization proble...A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization problem has a wide range of applications.In this paper,we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.展开更多
基金Supported by the Natural Science Foundation of Shandong Province (No.ZR2023MA031)the Natural Science Foundation of China (No.12201619)。
文摘Submodular optimization is primarily applied in multi-agent systems for tasks such as resource allocation,task assignment,collaborative decision-making,and optimization problems.Maximization 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 variable of the set function changes from one tok,it is called ak-submodular set function.Thek-submodular 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 submodularity becomes essential,leading to concepts such as approximately submodular set functions and the diminishing-return(DR) ratio.This paper investigates ak-dimensional set function under matroid constraints,which may lack full submodularity.Instead,we focus on an approximately non-ksubmodular 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.
基金supported by the Natural Science Foundation of Shandong Province of China(No.ZR2020MA029).
文摘In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint.In order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm failure.Moreover,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.
基金supported by the Natural Science Foundation of Shandong Province of China(Nos.ZR2020MA029,ZR2021MA100)the National Natural Science Foundation of China(No.12001335).
文摘A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization problem has a wide range of applications.In this paper,we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.
