不相交QoS路径与斯坦纳网络的近似算法研究

项目名称： 不相交QoS路径与斯坦纳网络的近似算法研究

项目编号： No.61300025

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 郭龙坤

作者单位： 福州大学

项目金额： 23万元

中文摘要： 随着网络的发展，视频应用日益增多，鲁棒视频流传输受到越来越多重视。为进行满足服务质量 (QoS）要求的鲁棒视频单播与多播，本课题拟研究不相交QoS路径与斯坦纳网络的高效构造方法。首先，本研究拟设计不相交QoS 路径的高效近似算法，其预期近似比与时间复杂度都优于当前最好结果；同时拟证明不相交QoS路径的不可近似性，从理论上分析可达到的最佳近似比。其次，基于申请人之前的2,3连通斯坦纳网络的近似算法成果，本研究将结合k不相交路径算法，设计k边连通最小斯坦纳网络的高效近似算法，并改进k点连通斯坦纳网络的近似比。最后，本研究将融合不相交QoS路径与k连通斯坦纳网络的近似算法，设计满足QoS约束的最小斯坦纳网络的高效近似算法。本项目处于计算机科学与数学的交叉领域，所研究的上述问题的近似算法不但具有重要的理论意义，而且可以直接用来改良当前网络中的视频传输方法，具有较大的实用价值。

中文关键词： 近似算法；不可近似性；k不相交双约束路径；k受限最短路径；QoS斯坦纳网络

英文摘要： Since video applications are growing along with the development of networks, robust video streaming is attracting more and more research interest. To meet the quality of service (QoS) requirements for robust video unicast and multicast, this project will investigate efficient method for constructing disjoint QoS paths and Steiner networks. First, this project will design efficient approximation algorithms for the disjoint QoS path problem, with approximation ratio and time complexity better than the known best results. Meanwhile this project will investigate the inapproximability of the disjoint QoS path problem and analyze the theoretically best approximation ratio. Secondly, based on our previous approximation algorithms for the 2,3-connected Steiner network problem and combining together with the k disjoint shortest paths algorithm, this project will design an efficient approximation algorithm for k-edge connectivity minimum Steiner network, and then improve the known best approximation ratio for the k-vertex connected Steiner network problem. Finally, this project will combine the method for constructing disjoint QoS paths and k-connected Steiner networks to obtain efficient approximation algorithms for the minimum QoS Steiner network problem. This project is interdisciplinary and involving both comput

英文关键词： approximation algorithm；Inapproximability；k-disjoint bi-constrained path；k-disjoint constrained shortest path；QoS Steiner network