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