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

刘　丽，张　安，陈　永，陈光亭

(杭州电子科技大学理学院，浙江 杭州，310018)



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

刘丽，张安，陈永，陈光亭

(杭州电子科技大学理学院，浙江 杭州，310018)

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

关键词：网络构建；近似算法；最坏情况界；装箱问题

0引言

1近似算法设计与分析

1.1　CDP问题

首先考虑CDP问题，即在有向图D中寻找一条s-t有向路，使构建该有向路所用的资源尽可能少。在算法中调用装箱问题[3]的经典算法——FFD作为子过程。对FFD算法，文献[4]给出了如下性质。

针对CDP问题，设计了算法A1，算法A1的具体描述如下：

1)利用Dijkstra算法[5]在网络D中找到一条总权重最小的s-t有向路Pst，记其弧集为A(Pst)={e1,e2,…,ek}；

3)对全部剩余弧段(权重为w′(ei)，i=1,2,…,k)，调用装箱问题的FFD算法将他们装入大小为L的箱子中，记b2为所用的箱子数，即此阶段所产生的分段数；

4)输出总共所需的分段数OUT=b1+b2。

1.2　CSCSS问题

本小节考虑CSCSS问题，即在有向网络D中找到一个强连通支撑子网络，使得构建该子网络所用的资源尽可能少。采用类似于算法A1的方法，得到算法A2，算法A2的计算步骤如下：

3)对全部剩余弧段(权重为w′(ei)，i=1,2,…,k)，调用装箱问题的FFD算法将他们装入大小为L的箱子中，记b2为所用的箱子数，即此阶段所产生的分段数；

4)输出总共所需的分段数OUT=b1+b2。

定理2算法A2的最坏情况界是3。

证明最小权强连通支撑子网络问题是NP-难的，SCA算法给出的是一个近似算法，最坏情况界为2[6]。设OPT是CSCSS问题最优解所用的分段数，则有w(A1)≤2w(A*)且w(A*)≤L×OPT，即w(A1)≤2w(A*)≤2L×OPT。与定理1证明类似，分两种情况讨论。

2结束语

参考文献

[1]Schrijver A.Combinatorial optimization:Polyhedra and efficiency[M].Berlin:Springer-Verlag Berlin Heidelberg,2003:1002-1035.

[2]Li J P,Ge Y,He S,et al.Approximation algorithms for constructing some required structures in digraphs[J].European Journal of Operational Reaearch,2014,232(2):307-314.

[3]Kantorovich L V.Mathematical methods of organizing and planning production[J].Management Science,1960,6(4):366-422.

[4]Simchi-Levi D.New worst-case results for the bin-packing problem[J].Naval Research Logistics,1994,41(4):579-585.

[5]Dijkstra E W.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959,1(1):269-271.

[6]Frederckson G N,Jaja J.Approximation algorithms for several graph augmentation problems[J].SIAM Journal on computing,1981,10(2):270-283.

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

Liu Li，Zhang An，Chen Yong，Chen Guangting

(SchoolofScience，HangzhouDianziUniversity，HangzhouZhejiang310018，China)

Abstract：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. and 3 respectively.

Key words：network construction；approximation algorithm；worst case ratio；bin packing problem

中图分类号：O221.7

文献标识码：A

文章编号：1001-9146(2015)06-0090-03

通信作者：

作者简介：刘丽(1991-)，女，安徽马鞍山人，在读研究生，组合优化与网络优化.张安副教授，E-mail：anzhang@hdu.edu.cn.

基金项目：国家自然科学基金资助项目(11201105；11401149)

收稿日期：2015-02-05

DOI：10.13954/j.cnki.hdu.2015.06.019