改进型网络模型中若干组合优化问题的复杂性理论与算法设计研究

The problems that construct some local subnetworks from the given networks to have certain specified properties with minimun costs are most important research topics in network theory, they have importantly theoretical research values and wide application prospects. This project will aim to focus on some combinatorial structures and their combinatorial optimization problems in improved network models, and each objective is either to minimize the sum of the cost of constructing the local subnetwork required and the cost of purchasing materials used in building such a local subnetwork, or to maximize the benefit produced by such a local subnetwork with the constraint of total investment limited, where the cost of calculation may have a different metric form if needed. The combinatorial optimization problems in such improved network models of this project extend the combinatorial optimization problems in the traditional ones as shown in the original research papers. This project involves combinatorial optimization, graph theory, computer science, game theory and other disciplines. By utilizing some combinations of the proceding related theories and good combinatorial structues in such improved network models, we shall establish their related mathematical models, and then find some strategy to design some approximation algorithms or randomization algorithms to solve these combinatorial optimization problems and other related optimization problems, and finally analyze the complexity of algorithms designed. As concerning the final outcomes in expectation, by utilizing good combinatorial structues in such improved network models, we shall deeply study some basic problems in the improved network models and the other related basic frontier problems, further develop some theories of combinatorial optimization and new methods of algorithm designs, publish a batch of important and influential research papers with original results in high level, we shall expect to publish our 16 research papers, some of which will be publishable in top journals in China and oversea. Meanwhile, we shall train some talented persons in combinatorial optimization, graph theory and theoretical computer science in order to strengthen and consummate our research team, and finally improve our scientific research level in these areas and related areas.

在给定网络中构建局部网络具有某些指定的性质，使费用达到最小，这些问题是网络理论研究中前沿课题，具有重要理论和应用价值。本项目重点研究改进型网络模型中若干组合结构及其优化问题,目标是使构建局部网络的工时费用与购买材料的费用之总和达到最小，或总投资费用有限的前提下，使构建局部网络产生最大效益，费用的计算可有多种度量形式。本项目推广了传统网络模型中的优化问题。项目涉及组合最优化、图论、计算机科学、博弈论和其它学科的交叉领域，借助这些理论工具和好的组合结构，对构建局部网络问题建立数学模型，寻找解决优化问题的策略，设计近似算法或随机算法来解决它们，并分析其复杂性。利用好的组合结构，对改进型网络模型中若干基础性问题及其它前沿基本问题进行深入研究，发展组合优化理论及算法设计新方法，产出一批高质量原创性成果，发表核心论文16篇，培养组合最优化、图论与计算机科学方面人才，完学研究梯队，提升该领域的研究水平。

科学技术的进步极大地促进了图论、组合优化与其它学科的交叉，组合算法理论作为其应用基础倍受重视，已成为研究的热点之一。实际应用与理论研究中的一些基本问题常能转化为网络模型中若干组合优化问题。若干组合优化问题的复杂性理论与算法设计的研究是网络理论研究的重要课题之一，在组合优化和其它学科分支中有广泛的应用，尤其是利用长度固定的若干材料来构建网络的优化问题是我们首次提出并付诸研究的问题，诱发了他人进行跟踪研究。我们在该项目中着重研究了网络模型中若干组合优化问题的复杂性理论与算法设计，主要从图论和组合算法理论角度来建立相应的数学模型，特别是建立了改进型网络模型上若干优化问题，设计近似算法或随机算法来解决这些难问题，并分析其复杂性，利用计算机及相关的数学软件来进行辅助性模拟计算研究，达到启发式地思考、解决问题的目的；我们还利用得到的算法来研究了一些其他优化问题，取得一些研究成果,达到总的预期目标。该研究项目已经完成学术研究论文22篇，其中正式发表16篇。还以改进型网络构建的部分成果，增加了2014年以前发表的成果，成功申请获得云南省自然科学奖三等奖1项（公示期为2018年10月16-11月15日）。我们以该研究项目作为平台，通过4年的努力，提升了图论与组合优化方向队伍的研究水平；共培养了毕业博士生1名和硕士生21名，在读博士生5名和硕士生11名。