In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular funct...In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular function.No multiplicative approximation algorithm exists for the regularized model,and most works have focused on designing weak approximation algorithms for this problem.In this study,we consider the k-CCRSM problem in a streaming fashion,wherein the elements are assumed to be visited individually and cannot be entirely stored in memory.We propose two multipass streaming algorithms with theoretical guarantees for the above problem,wherein submodular terms are monotonic and nonmonotonic.展开更多
We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint.This sum function is non-submodular in general.For an offline model,we introduce two approximation ...We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint.This sum function is non-submodular in general.For an offline model,we introduce two approximation algorithms:A greedy algorithm and a threshold greedy algorithm.For a streaming model,we propose a one-pass streaming algorithm.We also analyze the approximation ratios of these algorithms,which all depend on the total curvature of the supermodular function.The total curvature is computable in polynomial time and widely utilized in the literature.展开更多
Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guara...Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guarantees.The submodularity was investigated to capture the diversity and representativeness of the utilities,and the monotonicity has the advantage of improving the coverage.Regularized submodular optimization models were developed in the latest studies(such as a house on fire),which aimed to sieve subsets with constraints to optimize regularized utilities.This study is motivated by the setting in which the input stream is partitioned into several disjoint parts,and each part has a limited size constraint.A first threshold-based bicriteria(1/3,2/3/)-approximation for the problem is provided.展开更多
In this paper,we mainly investigate the optimization model that minimizes the cost function such that the cover function exceeds a required threshold in the set cover problem,where the cost function is additive linear...In this paper,we mainly investigate the optimization model that minimizes the cost function such that the cover function exceeds a required threshold in the set cover problem,where the cost function is additive linear,and the cover function is non-monotone approximately submodular.We study the problem under streaming model and propose three bicriteria approximation algorithms.Firstly,we provide an intuitive streaming algorithm under the assumption of known optimal objective value.The intuitive streaming algorithm returns a solution such that its cover function value is no less thanα(1−ϵ)times threshold,and the cost function is no more than(2+ϵ)^(2)/(ϵ^(2)ω^(2))⋅κ,whereκis a value that we suppose for the optimal solution andαis the approximation ratio of an algorithm for unconstrained maximization problem that we can call directly.Next we present a bicriteria streaming algorithm scanning the ground set multi-pass to weak the assumption that we guess the optimal objective value in advance,and maintain the same bicriteria approximation ratio.Finally we modify the multi-pass streaming algorithm to a single-pass one without compromising the performance ratio.Additionally,we also propose some numerical experiments to test our algorithm’s performance comparing with some existing methods.展开更多
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.展开更多
In this paper, we study the dynamic facility location problem with submodular penalties (DFLPSP). We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.
In many kinds of games with economic significance,it is very important to study the submodularity of functions.In this paper,wemainly study the problem of maximizing a concave function over an intersection of two matr...In many kinds of games with economic significance,it is very important to study the submodularity of functions.In this paper,wemainly study the problem of maximizing a concave function over an intersection of two matroids.We obtain that the submod-ularity may not be preserved,but it involves one maximal submodular problem(or minimal supermodular problem)with some conditions.Moreover,we also present examples showing that these conditions can be satisfied.展开更多
Recently intensive interest has been raised on approximation of the NPhard submodular maximization problem due to their theoretical and practical significance.In this work,we extend this line of research by focusing o...Recently intensive interest has been raised on approximation of the NPhard submodular maximization problem due to their theoretical and practical significance.In this work,we extend this line of research by focusing on the simultaneous approximation of multiple submodular function maximization.We address the existence and nonexistence results for both deterministic and randomized approximation when the submodular functions are symmetric and asymmetric,respectively,along with algorithmic corollaries.We offer complete characterization of the symmetric case and partial results on the asymmetric case.展开更多
In this paper,we consider the generalized prize-collecting Steiner forest problem with submodular penalties(GPCSF-SP problem).In this problem,we are given an undirected connected graph G=(V,E)and a collection of disjo...In this paper,we consider the generalized prize-collecting Steiner forest problem with submodular penalties(GPCSF-SP problem).In this problem,we are given an undirected connected graph G=(V,E)and a collection of disjoint vertex subsets V={V_(1),V_(2),…,V_(l)}.Assume c:E→R_(+)is an edge cost function andπ:2^(V)→R_(+)is a submodular penalty function.The objective of the GPCSF-SP problem is to find an edge subset F such that the total cost including the edge cost in F and the penalty cost of the subcollection S containing these Vi not connected by F is minimized.By using the primal-dual technique,we give a 3-approximation algorithm for this problem.展开更多
It is shown that for a valid non-cooperative utility system,if the social utility function is submodular,then any Nash equilibrium achieves at least 1/2 of the optimal social utility,subject to a function-dependent ad...It is shown that for a valid non-cooperative utility system,if the social utility function is submodular,then any Nash equilibrium achieves at least 1/2 of the optimal social utility,subject to a function-dependent additive term.Moreover,if the social utility function is nondecreasing and submodular,then any Nash equilibrium achieves at least 1/(1+c)of the optimal social utility,where c is the curvature of the social utility function.In this paper,we consider variations of the utility system considered by Vetta,in which users are grouped together.Our aim is to establish how grouping and cooperation among users affect performance bounds.We consider two types of grouping.The first type is from a previous paper,where each user belongs to a group of users having social ties with it.For this type of utility system,each user’s strategy maximises its social group utility function,giving rise to the notion of social-aware Nash equilibrium.We prove that this social utility system yields to the bounding results of Vetta for non-cooperative system,thus establishing provable performance guarantees for the social-aware Nash equilibria.For the second type of grouping we consider,the set of users is partitioned into l disjoint groups,where the users within a group cooperate to maximise their group utility function,giving rise to the notion of group Nash equilibrium.In this case,each group can be viewed as a new user with vector-valued actions,and a 1/2 bound for the performance of group Nash equilibria follows from the result of Vetta.But as we show tighter bounds involving curvature can be established.By defining the group curvature cki associated with group i with ki users,we show that if the social utility function is nondecreasing and submodular,then any group Nash equilibrium achieves at least 1/(1+max1≤i≤l cki)of the optimal social utility,which is tighter than that for the case without grouping.As a special case,if each user has the same action space,then we have that any group Nash equilibrium achieves at least 1/(1+ck∗)of the optimal social utility,where k∗is the least number of users among the l groups.Finally,we present an example of a utility system for database-assisted spectrum access to illustrate our results.展开更多
基金This work was supported by the Beijing Natural Science Foundation Project(No.Z220004)the National Natural Science Foundation of China(Nos.11901544 and 12101587)the China Postdoctoral Science Foundation(No.2022M720329).
文摘In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular function.No multiplicative approximation algorithm exists for the regularized model,and most works have focused on designing weak approximation algorithms for this problem.In this study,we consider the k-CCRSM problem in a streaming fashion,wherein the elements are assumed to be visited individually and cannot be entirely stored in memory.We propose two multipass streaming algorithms with theoretical guarantees for the above problem,wherein submodular terms are monotonic and nonmonotonic.
基金The first author was supported by the National Natural Science Foundation of China(Nos.12001025 and 12131003)The second author was supported by the Spark Fund of Beijing University of Technology(No.XH-2021-06-03)+2 种基金The third author was supported by the Natural Sciences and Engineering Research Council of Canada(No.283106)the Natural Science Foundation of China(Nos.11771386 and 11728104)The fourth author is supported by the National Natural Science Foundation of China(No.12001335).
文摘We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint.This sum function is non-submodular in general.For an offline model,we introduce two approximation algorithms:A greedy algorithm and a threshold greedy algorithm.For a streaming model,we propose a one-pass streaming algorithm.We also analyze the approximation ratios of these algorithms,which all depend on the total curvature of the supermodular function.The total curvature is computable in polynomial time and widely utilized in the literature.
基金This work was supported by the Beijing Natural Science Foundation Project(No.Z200002)the National Natural Science Foundation of China(Nos.12001523,12131003,and 12101587)+1 种基金the National Innovation and Entrepreneurship Training Program for College Students of Beijing University of Technology(No.GJDC-2022-01-39)the China Postdoctoral Science Foundation(No.2022M720329).
文摘Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guarantees.The submodularity was investigated to capture the diversity and representativeness of the utilities,and the monotonicity has the advantage of improving the coverage.Regularized submodular optimization models were developed in the latest studies(such as a house on fire),which aimed to sieve subsets with constraints to optimize regularized utilities.This study is motivated by the setting in which the input stream is partitioned into several disjoint parts,and each part has a limited size constraint.A first threshold-based bicriteria(1/3,2/3/)-approximation for the problem is provided.
基金This work was supported by the National Natural Science Foundation of China(Nos.72192804,72192800,and 12201619)the China Postdoctoral Science Foundation(No.2022M723333).
文摘In this paper,we mainly investigate the optimization model that minimizes the cost function such that the cover function exceeds a required threshold in the set cover problem,where the cost function is additive linear,and the cover function is non-monotone approximately submodular.We study the problem under streaming model and propose three bicriteria approximation algorithms.Firstly,we provide an intuitive streaming algorithm under the assumption of known optimal objective value.The intuitive streaming algorithm returns a solution such that its cover function value is no less thanα(1−ϵ)times threshold,and the cost function is no more than(2+ϵ)^(2)/(ϵ^(2)ω^(2))⋅κ,whereκis a value that we suppose for the optimal solution andαis the approximation ratio of an algorithm for unconstrained maximization problem that we can call directly.Next we present a bicriteria streaming algorithm scanning the ground set multi-pass to weak the assumption that we guess the optimal objective value in advance,and maintain the same bicriteria approximation ratio.Finally we modify the multi-pass streaming algorithm to a single-pass one without compromising the performance ratio.Additionally,we also propose some numerical experiments to test our algorithm’s performance comparing with some existing methods.
基金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.
基金Supported in part by Hebei Province Department of Education Fund under Grant No.Z2012017the National Natural Science Foundation of China under Grant No.11371001 and 11201013
文摘In this paper, we study the dynamic facility location problem with submodular penalties (DFLPSP). We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.
基金supported by Higher Educational Science and Technology Program of Shandong Province(No.J17KA171)Natural Science and Engineering Research Council of Canada(No.06446)+1 种基金the National Natural Science Foundation of China(No.11871081)Science and Technology Program of Beijing Education Commission(No.KM201810005006).
文摘In many kinds of games with economic significance,it is very important to study the submodularity of functions.In this paper,wemainly study the problem of maximizing a concave function over an intersection of two matroids.We obtain that the submod-ularity may not be preserved,but it involves one maximal submodular problem(or minimal supermodular problem)with some conditions.Moreover,we also present examples showing that these conditions can be satisfied.
基金supported by the Natural Sciences and Engineering Research Council of Canada(NSERC,No.283103)This work was partially done while the second author was a visiting doctorate student at the Faculty of Business Administration,University of New Brunswick and supported in part by NSERC(No.283103)+2 种基金The research of the third author is supported by the National Basic Research Program of China(No.2010CB732501)The fourth author’s research is supported by National Natural Science Foundation of China(No.11371001)Scientific Research Common Program of Beijing Municipal Commission of Education(No.KM201210005033).
文摘Recently intensive interest has been raised on approximation of the NPhard submodular maximization problem due to their theoretical and practical significance.In this work,we extend this line of research by focusing on the simultaneous approximation of multiple submodular function maximization.We address the existence and nonexistence results for both deterministic and randomized approximation when the submodular functions are symmetric and asymmetric,respectively,along with algorithmic corollaries.We offer complete characterization of the symmetric case and partial results on the asymmetric case.
基金This work is supported by the National Natural Science Foundation of China(No.11971146)the Natural Science Foundation of Hebei Province(Nos.A2019205089 and A2019205092)+1 种基金Hebei Province Foundation for Returnees(No.CL201714)Overseas Expertise Introduction Program of Hebei Auspices(No.25305008).
文摘In this paper,we consider the generalized prize-collecting Steiner forest problem with submodular penalties(GPCSF-SP problem).In this problem,we are given an undirected connected graph G=(V,E)and a collection of disjoint vertex subsets V={V_(1),V_(2),…,V_(l)}.Assume c:E→R_(+)is an edge cost function andπ:2^(V)→R_(+)is a submodular penalty function.The objective of the GPCSF-SP problem is to find an edge subset F such that the total cost including the edge cost in F and the penalty cost of the subcollection S containing these Vi not connected by F is minimized.By using the primal-dual technique,we give a 3-approximation algorithm for this problem.
基金NSF and Division of Computing and Communication Foundations[grant number CCF-1422658]the CSU Information Science and Technology Center(ISTeC)。
文摘It is shown that for a valid non-cooperative utility system,if the social utility function is submodular,then any Nash equilibrium achieves at least 1/2 of the optimal social utility,subject to a function-dependent additive term.Moreover,if the social utility function is nondecreasing and submodular,then any Nash equilibrium achieves at least 1/(1+c)of the optimal social utility,where c is the curvature of the social utility function.In this paper,we consider variations of the utility system considered by Vetta,in which users are grouped together.Our aim is to establish how grouping and cooperation among users affect performance bounds.We consider two types of grouping.The first type is from a previous paper,where each user belongs to a group of users having social ties with it.For this type of utility system,each user’s strategy maximises its social group utility function,giving rise to the notion of social-aware Nash equilibrium.We prove that this social utility system yields to the bounding results of Vetta for non-cooperative system,thus establishing provable performance guarantees for the social-aware Nash equilibria.For the second type of grouping we consider,the set of users is partitioned into l disjoint groups,where the users within a group cooperate to maximise their group utility function,giving rise to the notion of group Nash equilibrium.In this case,each group can be viewed as a new user with vector-valued actions,and a 1/2 bound for the performance of group Nash equilibria follows from the result of Vetta.But as we show tighter bounds involving curvature can be established.By defining the group curvature cki associated with group i with ki users,we show that if the social utility function is nondecreasing and submodular,then any group Nash equilibrium achieves at least 1/(1+max1≤i≤l cki)of the optimal social utility,which is tighter than that for the case without grouping.As a special case,if each user has the same action space,then we have that any group Nash equilibrium achieves at least 1/(1+ck∗)of the optimal social utility,where k∗is the least number of users among the l groups.Finally,we present an example of a utility system for database-assisted spectrum access to illustrate our results.