不相交QoS路径的理论与应用

Due to the development of networking technology, disjoint QoS path routing are attracting considerable interest from more and more researchers because of its advantage in load balance and reliability. This project will first design approximation algorithms and fast algorithms for kCSP, a sub problem of the disjoint QoS path problem. First, we will design an enhanced cycle cancellation method which can compute proper cycles in a bi-weighted graph with negative cycles. The computed cycles can be used to repeatedly improve a solution of kCSP, towards an optimal solution until an approximation solution is obtained. It is expected the method results in a single constant factor approximation ratio, improving the currently best single factor approximation ratio of O(ln n). Through combining the property of an optimal solution to kCSP and the existing LP rounding algorithm, we will improve the currently best bifactor ratio for kCSP. Through designing a more in-depth LP formula for kCSP, we will present a fast LP primal-dual algorithm. Then, we will investigate the relationship between 1CSP and 2CSP, to accordingly design parameterized approximation algorithm for 2CSP. While designing the algorithms, we will simultaneously analyze inapproximability of kCSP. Later, we will design an Linear Program for kDCSP, and three cycle cancellation method for kDCSP, kCSPP and kDCSPP, respectively, as to obtain approximation algorithms for the problems. At last, we will also investigate the parallelism of the above algorithms. The output of the project can leverage the improvement of the data transmission method in current networks.

随着网络技术发展，不相交QoS路径路由因其良好的负载均衡与可靠性，得到越来越多研究者的关注。本研究首先拟设计其子问题kCSP的近似算法与快速算法。将设计加强的消圈方法在有负圈的双权值图中寻找合适圈，并据此持续改进kCSP的一个任意解至近似最优解，预期可改进当前最佳单因子近似比O(ln n)至常数近似比；将结合kCSP最优解的图论属性与线性规划取整算法，预期可改进当前最佳双因子近似比；通过设计一个更深刻的线性规划松弛，预期可设计一个快速的线性规划对偶算法。其次，拟探索1CSP与2CSP之间的联系，以据此设计2CSP问题的固定参数近似算法。设计算法过程中，拟同时分析kCSP的不可近似性。之后，拟设计kDCSP的线性规划刻画，并设计kDCSP、kCSPP与kDCSPP的消圈算法，以得到问题的近似算法。最后，将研究上述算法的并行化。本项目产出不仅有理论价值，还可用以改良网络数据传输。

项目团队首先设计了不相交QoS路径问题的高效算法，并探索了使用消圈算法解决本问题的难解性。在不相交路径问题的算法方面，对于一个结定的参数δ，项目团队探索了δ-部分点不相交与δ-部分边不相交路径的高效算法: (1)证明了δ-部分点不相交路径与最短路径之间的关系，并基于关系设计了一个快速算法，可在O(δ(m+nlogn))的时间内计算2条同源或同终端的边不相交路径，使得2条路径上共享的结点个数不超过给定的参数δ；(2)设计了可计算2条同源或同终端的δ部分边不相交路径的快速算法。参数δ提供了一个平衡(balance)所计算路径的不相交性与其占用资源之间的选项，从而可以使数据传输具有更好的服务质量(QoS)。(3)针对k条(完全)点不相交路径问题，探索了BP(belief propagation)框架的使用并设计了一个基于信息传递(message passing)的算法。在问题难解性方面，证明了判定简单图中是否存在长度不小于3负圈的NP完全性，从而刻画了使用消圈法计算不相交QoS路径的难解性。.其次，项目团队探索了不相交路径算法在若干相关应用问题中的应用，包括计算机网络路由问题、大规模集成电路的布线问题与(移动传感器网络的)覆盖问题等。其中，通过结合路径的线性规划(Linear Programming, LP)刻画方法，使用LP随机舍入技术设计了带组约束的覆盖问题的近似比为1-1/e的近似算法，在理论上达到了该问题的最佳近似比；通过将栅栏覆盖问题转化为最短路径问题，设计了栅栏覆盖问题的高效算法；基于部分不相交路径的关键算法思想，设计了使用时分复用技术的多FPGA系统互连的布线问题的高效实用算法。.此外，项目团队探索了带(QoS)约束的若干优化问题(包括带约束的k-means与约束次模优化等问题)，设计了这些问题的近似算法。其中，在带背包约束的次模最大化问题变体上所得的近似比已经非常接近该问题的无约束版本。