互联网改变了人们的生活方式，形成了庞大的社会网络，社会网络影响最大化问题的研究是当前国际上研究的热点。本项目将围绕社会网络环境下非次模函数优化问题和相关合作博弈的算法开展研究，目标是在以下三方面取得进展：一是目标函数为非次模函数、约束为某类独立系统的优化问题的计算复杂性和近似算法；二是目标函数为非次模函数的社会网络影响最大化问题的计算复杂性和近似算法；三是社会网络环境下的合作博弈的最优联盟形成及相关博弈解的计算复杂性和求解算法。本项目争取在非次模函数的优化问题的算法设计与分析上有所突破，并将相关结果应用于社会网络影响最大化以及相应的利益分配问题，突破当前该领域的研究大多仅局限于目标函数为次模函数的瓶颈。本项目属于组合最优化、博弈论和算法理论的交叉领域。项目的预期成果将为组合优化、合作博弈提供一些新的思想、研究方法和理论结果，并具有广泛的前景。

Internet has changed the public’s lifestyle, which encourages the formation of a huge social network. Currently, study on influence maximization in social networks has been a hot topic in the field of international research. This project researches on algorithms for optimization problems with non-submodular objective functions and related cooperative games in social networks. Try to make some progresses in the following three aspects. (1) Research on the computation complexities and approximate algorithms of optimization problems with non-submodular objective functions and constraints for a class of independent systems; (2) Study the computation complexities and approximate algorithms for influence maximization problems with non-submodular objective functions in social network; (3) Explore the optimal coalitions in related cooperative games, analyze the computation complexities and design reasonable algorithms for finding the corresponding game solution. This project tries to make some breakthroughs in the design and analysis of algorithms for optimization with non-submodular objective functions, and apply related results to the influence maximization problems and related interest distribution problems in social networks. Break through the bottleneck that the research in this field are mainly limited to studying problems with submodular objective functions. This project belongs to the cross field of combinatorial optimization, game theory and algorithm theory. The expected results of it will provide some new ideas, research methods and theoretical results for combinatorial optimization and cooperative game theories, and have broad prospects in the future.