拟阵约束下次模函数最大化问题的近似算法设计及应用

The study of submodular functions is one of the hot topics in theoretical computer science. It is motivated both by many real-world applications and by their frequent occurrence in many theoretical fields such as computational economics and algorithmic game theory. In particular, submodular functions and submodular maximization problems play a major role in combinatorial optimization as several well-known combinatorial functions turn out to be submodular. ..In this project, we focus on the deterministic approximation algorithm of several submodular maximization problems under matroid constraints. We want to answer the question: Is randomness necessary for the submodular maximization problem under matroid constraints? Firstly, we will study two important cases in matroid constraints: partition matroid and transversal matroid. We then consider submodular welfare problem and influence maximization problem. Both problems can be considered as special cases of submodular maximization, while they are also the abstractions of many real-world applications...There are two distinguished properties in our project. Firstly, the research on the submodular maximization problems will deep our understanding of submodularity and matroid system. We hope we can make contribution to the field of approximation algorithm and combinatorial optimization. Secondly, we will apply our theoretical results to submodular welfare problem and influence maximization problem. Both problems capture many real-world applications. The submodular welfare problem comes from computational economics and algorithmic game theory, while the influence maximization problem can abstract the real-world scenarios such as network marketing, internet rumor control, etc.

次模函数最大化问题一直是理论计算机科学中的热门研究问题，与很多重要的优化问题如最大割问题和最大k-覆盖问题等都有着密切的关系。本项目计划从确定性近似算法设计和近似比分析的角度研究拟阵约束下的次模函数最大化问题，力求能回答“随机性对于求解次模函数最大化问题是否是必要的？”这个关键的科学问题。项目首先研究划分拟阵、遍历拟阵这两类重要的拟阵约束下次模函数最大化问题，接着应用到两类特殊的次模优化问题：次模福利问题和网络上影响力最大化问题上。这两个问题前者来源于经济学中拍卖和资源分配相关的场景，后者可以解决如网络营销、谣言控制等和影响力传播紧密相关的优化问题。本项目有两个显著特色：一是项目属于前沿理论研究，能够深化对次模结构、拟阵结构的理解和认识，为近似算法和组合优化的发展做出贡献；二是项目将利用所研究的理论结果从算法的角度研究经济学和网络科学中的两个优化问题，属于交叉研究。

次模函数最大化问题一直是理论计算机科学中的热门研究问题，与很多重要的优化问题如最大割问题和最大k-覆盖问题等都有着密切的关系。本项目从确定性近似算法设计和近似比分析的角度对多种不同约束下的次模函数最大化问题展开研究，并进一步把理论结果应用到影响力最大化问题上，对社交网络中的影响力传播这类应用场景的优化问题展开研究。. 在本项目中，针对拟阵约束和背包约束下的次模最大化问题，我们分别设计了新的确定性近似算法，其近似比均优于目前最好的理论结果。具体来说，对多背包约束下的单调次模最大化问题，我们的算法近似为1-1/e-ϵ，几乎达到了最优；对单背包约束下的非单调次模最大化问题，我们算法的近似比为1/4，并指出了双胞胎技术最多只能做到1/4的近似比；对拟阵约束下的非单调次模最大化问题，近似比为0.283。这些结果缩小了目前次模最大化领域随机算法和确定性算法的近似比之间的差距。. 在应用到影响力最大化问题的研究中，我们首先针对影响力函数这种特殊的次模函数的性质展开研究，之后主要关注采样模型和老虎机模型这两种输入模型下影响力最大化问题的算法研究。在采样模型中，我们提出了带有结构信息的采样模型，并基于此先后针对覆盖最大化问题和影响力最大化问题提出了常数近似比的近似算法。这个结果通过获知结构信息解决了前人工作中不带结构信息的采样模型的近似困难性，同时，所需的结构信息也是在实际应用中很容易得到的，并没有降低模型的适用性。在老虎机模型中，我们的工作不依赖于过去工作中所需要边反馈信息的假设，而改为只需要点反馈信息这种更弱的输入模型，这也是更符合实际情况的一种输入模型。我们所设计的算法能达到和边反馈输入模型一样的悔值界，这使得算法在实际场景中有了更广泛的应用。可以看到，在影响力最大化问题的研究中，项目不仅仅关注所设计算法的近似比，也重点关注研究的问题模型是否贴合实际应用场景，为理论算法在实际中的应用打下了良好的基础。