In the study of information technology,one of the important efforts is made on dealing with nonsubmodular optimizations since there are many such problems raised in various areas of computer and information science.Us...In the study of information technology,one of the important efforts is made on dealing with nonsubmodular optimizations since there are many such problems raised in various areas of computer and information science.Usually,nonsubmodular optimization problems are NP-hard.Therefore,design and analysis of approximation algorithms are important tasks in the study of nonsubmodular optimizations.However,the traditional methods do not work well.Therefore,a new method,the global approximation of local optimality,is proposed recently.In this paper,we give an extensive study for this new methodology.展开更多
Submodular optimization is widely used in large datasets.In order to speed up the problems solving,it is essential to design low-adaptive algorithms to achieve acceleration in parallel.In general,the function values a...Submodular optimization is widely used in large datasets.In order to speed up the problems solving,it is essential to design low-adaptive algorithms to achieve acceleration in parallel.In general,the function values are given by a value oracle,but in practice,the oracle queries may consume a lot of time.Hence,how to strike a balance between optimizing them is important.In this paper,we focus on maximizing a normalized and strictly monotone set function with the diminishing-return ratio under a cardinality constraint,and propose two algorithms to deal with it.We apply the adaptive sequencing technique to devise the first algorithm,whose approximation ratio is arbitrarily close to 1-e^(-γ)in O(logn·log(log k/γ)) adaptive rounds,and requires O(logn^(2)·log(log k/γ)) queries.Then by adding preprocessing and parameter estimation steps to the first algorithm,we get the second one.The second algorithm trades a small sacrifice in adaptive complexity for a significant improvement in query complexity.With the same approximation and adaptive complexity,the query complexity is improved to.To the best of our knowledge,this is the first paper of designing adaptive algorithms for maximizing a monotone function using the diminishing-return ratio.展开更多
基金supported in part by the National Natural Science Foundation of China(No.U20A2068)Zhejiang Provincial Natural Science Foundation of China(No.LD19A010001)Natural Science Foundation of USA(No.1907472)。
文摘In the study of information technology,one of the important efforts is made on dealing with nonsubmodular optimizations since there are many such problems raised in various areas of computer and information science.Usually,nonsubmodular optimization problems are NP-hard.Therefore,design and analysis of approximation algorithms are important tasks in the study of nonsubmodular optimizations.However,the traditional methods do not work well.Therefore,a new method,the global approximation of local optimality,is proposed recently.In this paper,we give an extensive study for this new methodology.
基金the National Natural Science Foundation of China(Nos.11971447 and 11871442)the Fundamental Research Funds for the Central Universities.
文摘Submodular optimization is widely used in large datasets.In order to speed up the problems solving,it is essential to design low-adaptive algorithms to achieve acceleration in parallel.In general,the function values are given by a value oracle,but in practice,the oracle queries may consume a lot of time.Hence,how to strike a balance between optimizing them is important.In this paper,we focus on maximizing a normalized and strictly monotone set function with the diminishing-return ratio under a cardinality constraint,and propose two algorithms to deal with it.We apply the adaptive sequencing technique to devise the first algorithm,whose approximation ratio is arbitrarily close to 1-e^(-γ)in O(logn·log(log k/γ)) adaptive rounds,and requires O(logn^(2)·log(log k/γ)) queries.Then by adding preprocessing and parameter estimation steps to the first algorithm,we get the second one.The second algorithm trades a small sacrifice in adaptive complexity for a significant improvement in query complexity.With the same approximation and adaptive complexity,the query complexity is improved to.To the best of our knowledge,this is the first paper of designing adaptive algorithms for maximizing a monotone function using the diminishing-return ratio.
