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

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

项目编号： No.11461081

项目类型： 地区科学基金项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 李建平

作者单位： 云南大学

项目金额： 36万元

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

中文关键词： 改进型网络模型；组合优化问题；算法设计；复杂性理论；不可近似性

英文摘要： 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.

英文关键词： Improved network models;Combinatorial optimization problems;Design of algorithms;Complexity theory;Innapproximation