互连网络中若干优化问题研究

本项目研究互连网络中两类重要的优化问题，一个是带有约束条件的路径（Routing）问题，另一个是网络上设备（如web proxy等）的最优配置问题。对于前者我们着重研究带有约束条件的Steiner树问题以及点对间连接问题，如加权约束、时延约束等，研究中将针对有很强实际背景的特殊网络结构设计有效的多项式时间算法或者对一些NP-hard情形设计有良好时间复杂度的多项式时间近似方案。对于后者，将根据不同的模型研究在哪些特殊而有实际意义的网络结构下能够具有多项式时间算法。这些问题的背景直接来自于计算机通讯网络，同时在一般意义下又都是NP-hard问题，因此该项研究具有深刻的理论意义，同时又有重要实用价值。