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.展开更多
Submodular function maximization problem has been extensively studied recently.A natural variant of submodular function is k-submodular function,which has many applications in real life,such as influence maximization ...Submodular function maximization problem has been extensively studied recently.A natural variant of submodular function is k-submodular function,which has many applications in real life,such as influence maximization and sensor placement problem.The domain of a k-submodular function has k disjoint subsets,and hence includes submodular function as a special case when k=1.This work investigates the k-submodular function maximization problem with d-knapsack constraints over the sliding window.Based on the smooth histogram technique,we design a deterministic approximation algorithm.Furthermore,we propose a randomized algorithm to improve the approximation ratio.展开更多
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.展开更多
The key issue in top-k retrieval, finding a set of k documents （from a large document collection） that can best answer a user＇s query, is to strike the optimal balance between relevance and diversity. In this paper...The key issue in top-k retrieval, finding a set of k documents （from a large document collection） that can best answer a user＇s query, is to strike the optimal balance between relevance and diversity. In this paper, we study the top-k re- trieval problem in the framework of facility location analysis and prove he submodularity of that objective function which provides a theoretical approximation guarantee of factor 1 -1/ε for the （best-first） greedy search algorithm. Furthermore, we propose a two-stage hybrid search strategy which first ob- tains a high-quality initial set of top-k documents via greedy search, and then refines that result set iteratively via local search. Experiments on two large TREC benchmark datasets show that our two-stage hybrid search strategy approach can supersede the existing ones effectively and efficiently.展开更多
基金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 National Natural Science Foundation of China(Nos.12271259 and 12371352)the Zhejiang Provincial Natural Science Foundation of China(No.LY23A010011)+1 种基金the Yongjiang Talent Introduction Programme of Ningbo(No.2021B-011-G)the Natural Sciences and Engineering Research Council of Canada(NSERC)(No.06446).
文摘Submodular function maximization problem has been extensively studied recently.A natural variant of submodular function is k-submodular function,which has many applications in real life,such as influence maximization and sensor placement problem.The domain of a k-submodular function has k disjoint subsets,and hence includes submodular function as a special case when k=1.This work investigates the k-submodular function maximization problem with d-knapsack constraints over the sliding window.Based on the smooth histogram technique,we design a deterministic approximation algorithm.Furthermore,we propose a randomized algorithm to improve the approximation ratio.
基金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.
基金This work was supported by the National Natural Science Foundation of China （Grant Nos. 61572135 and 61170085）, 973 project （2010CB328106）, Program for New Century Excellent Talents in China （NCET-10-0388）.
文摘The key issue in top-k retrieval, finding a set of k documents （from a large document collection） that can best answer a user＇s query, is to strike the optimal balance between relevance and diversity. In this paper, we study the top-k re- trieval problem in the framework of facility location analysis and prove he submodularity of that objective function which provides a theoretical approximation guarantee of factor 1 -1/ε for the （best-first） greedy search algorithm. Furthermore, we propose a two-stage hybrid search strategy which first ob- tains a high-quality initial set of top-k documents via greedy search, and then refines that result set iteratively via local search. Experiments on two large TREC benchmark datasets show that our two-stage hybrid search strategy approach can supersede the existing ones effectively and efficiently.
