网络科学中若干非线性组合优化问题的复杂性和算法

非线性组合优化问题是指目标函数或约束条件是非线性函数的一类组合优化问题，这些非线性函数包括次模函数、二次函数甚至是对数函数等。非线性组合优化是当今国际上组合优化领域的前沿热点研究内容。在本项目中，我们研究来自于网络科学的三个非线性组合优化问题，它们是全局标签割问题、最小结构熵问题和稠密k-子图问题。其中，全局标签割问题和最小结构熵问题是两个新问题，它们的复杂性至今仍是未知的，并成为关注的焦点。稠密k-子图问题是一个经典的问题，但我们得到了研究该问题一个新的视角。由此，我们凝练出三个关键科学问题：全局标签割问题是否是多项式时间可解的，最小结构熵问题是否是NP难的，以及能否得到稠密k-子图问题新的或改进的近似算法。采用前沿的非线性组合优化技术研究网络科学中的前沿优化问题，是本项目最鲜明的特色和新颖之处。项目的研究将推进组合优化和近似算法发展的前沿，并在网络科学等领域产生实际的应用。

The non-linear combinatorial optimization problems are the problems which are combinatorial optimizing and whose objective function or constrained conditions contain non-linear functions, where the non-linear function could be sub-modular function, quadratic function, or even logarithmic function, etc. Non-linear combinatorial optimization is currently the internationally cutting-edge hot topic in the field of combinatorial optimization. In this project, we study three non-linear combinatorial optimization problems coming from network science, which are the Global Label Cut problem, the Min Structural Entropy problem, and the Densest k-Subgraph problem. The Global Label Cut and the Min Structural Entropy problem are two new problems. Meanwhile, their computational complexities are still unknown at the current time, becoming focus drawing attentions from researchers. Though the Densest k-Subgraph problem is a classical and well-known problem, we get a new viewpoint dealing with this problem in the preparation study work of this project. In this way, we abstract three key scientific problems as the following. The first is whether the Global Label Cut problem can be solved in polynomial time, the second is whether the Min Structural Entropy problem is NP-hard, and the third is whether we can get new or even improved approximation algorithms for the Densest k-Subgraph problem. The most notable novelty of our project is to study the cutting-edge optimization problems coming from network science using the cutting-edge non-linear combinatorial optimization techniques. The results of this project should push the cutting edge of combinatorial optimization and approximation algorithms, and find applications in the fields of network science and others.