若干最小网络及其集成组合优化问题的算法研究

The minimum spanning tree problem and the minimum Steiner tree problem might be of the most importance in the network optimization fields, researches on which used to give birth to theories and methods of network optimization or even the whole combinatorial optimization. This project mainly studies several minimum network problems with respect to but different from the classical spanning tree and Steiner tree, and some integrated combinatorial optimization problems, specifically, including the constrained spanning tree problem, the Internal or Terminal Steiner tree problem and the combinatorial optimization problems integrated network and scheduling or bin packing. For each problem, we prove the NP-hardness or the non-approximability by the computational complexity theory, design solution algorithms in according to its combinatorial structure and properties, and analyze the algorithms’ performance in both theoretical and numerical sense. In particular, to generate a good algorithm for the integrated combinatorial problems, we should capture the general character of different combinatorial problems and combine their own sophisticated algorithms together. In a word, the project contains not only important further study on the classical network optimization problems, but also several new problems that integrate network and other combinatorial optimization problems. With both theoretical consequence and application prospect, it should be an innovative research.

最小支撑树问题和Steiner最小树问题一直是网络优化领域中最重要、最核心的内容，对它们的研究产生了一系列影响网络优化乃至整个组合优化的理论和方法。本项目着重研究几类与传统支撑树和Steiner树相关但又不尽相同的最小网络问题和与其集成的组合优化问题，包括带约束支撑树问题、Internal或Terminal Steiner树问题以及集成网络与排序、网络与装箱的组合优化问题。对每一具体问题，利用计算复杂性理论证明问题的NP-困难性或不可近似性，根据问题本身的组合结构和组合性质设计求解算法，并从理论和数值两个角度分析算法的性能。对其中的集成组合优化问题，注重挖掘各组合优化问题的共性，利用它们已有的算法，设计实用有效的集成算法。本项目研究不仅包含了经典网络优化问题的前沿研究，而且开展了集成网络与其他组合优化问题的创新研究，既有理论深度，又有应用前景，是一项前瞻性创新研究。

本项目主要研究网络优化问题以及与其它组合优化问题集成的优化问题。项目主要针对集成组合优化问题、网络优化问题、相关调度问题以及图上匹配多项式最大根问题等展开研究，并取得系列成果。. 研究了若干集成优化问题。对于链式或环状弹性光网络上谱分配问题，分别给出了4/3和3/2的近似算法。带冲突图的两台机上Flow-shop排序问题，利用图上路覆盖问题，对单位工件或任意工件情形，分别给出了4/3和3/2的近似算法。对于最大内点权生成树问题以及顶点Happy问题，分别给出了明显改进的近似算法。对于2-max-duo问题，引入一种新的方法，给出了近似比无限接近1.4的近似算法。对于港口作业相关的若干集成优化问题，针对几类不同约束条件，分别给出了近似算法。. 研究了若干图上划分问题。对于图上最小3-path划分问题，利用不同算法，把文献中3/2的近似比依次改进到13/9，4/3，21/16。对于图上划分成k个连通子图的min-max balanced 问题，当k=3时，给出了一个3/2近似算法，对一般情形给出了k/2的近似算法，并对k=4的特殊情形，给出了24/13近似算法。对于3n个顶点的边赋权完全图上最大三角划分问题，首次给出一个随机近似算法，其期望近似比可以任意接近0.66745。. 研究了若干排序问题新模型，对三台机的混合排序模型，操作集合约束的在线模型，时间约束的排序问题，平行机上分层在线排序问题，平行机上带单个服务器且工件大小相同的排序问题等，分别分析其问题复杂性或设计了更优近似比的近似算法。. 项目研究了若干不同类型图上匹配多项式最大根问题，得到了若干改进结果。. 项目还支持培养了12位学生获得硕士学位，支持举办了多场学术研讨会。. 项目成果丰富，而且在算法设计上有较多创新，科学意义较大。