一类新型网络构建问题的算法设计与分析

Design and Analysis of Algorithms for a New Class of Network Construction Problems

研究了一类新型网络构建问题,使有向网络中子网络的弧在切割成权值为L的分段时所产生的总分段数尽可能小。针对问题,假设有向网络每条弧的权值不小于L,给出子网络结构为有向路或强连通支撑子网络两种情形时的近似算法,并证明算法的最坏情况界分别为3/2和3。

This paper considers a new class of network construction problems. Given a directed network, it aims to find a subnetwork with specific structure in which arcs are cut into pieces of length at most L. The objective is to minimize the total number of pieces. When the length of each arc is no smaller than L and the network structure is restricted by a directed path or a strongly-connected spanning subnetwork, we provideapproximation algorithms with worst case ratios of 3/2and 3 respectively.