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.展开更多
基金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.
