有向网络中最大容量支撑树形图扩容问题

doi:10.15960/j.cnki.issn.1007-6093.2024.02.012

Abstract

Abstract:

For the expansion problem of the maximum capacity spanning arborescence in networks (EMCSA), NP-hardness is proved by constructing an instance of EMCSA from 0-1 knapsack problem, and a heuristic algorithm is designed. Finally, one special version of EMCSA, the expansion problem of the minimum arc number on the maximum capacity spanning arborescence in networks (NEMCSA), is considered. For NEMCSA, a strongly polynomial algorithm, in $O(mn) $ time, is provided by substituting the arc with the minimum weight difference.

Key words: maximum capacity arborescence, capacity expansion, NP-hard, heuristic algorithm, polynomial time algorithm

CLC Number:

O157.6

Zilan YANG, Juanping ZHU, Yu YANG. The expansion problem of maximum capacity spanning arborescence in networks[J]. Operations Research Transactions, 2024, 28(2): 151-158.

Figures/Tables 1

References 20

1	黄韬,霍如,刘江,等.未来网络发展趋势与展望[J].中国科学: 信息科学,2019,49,941-948.
2	张超. 有向网络容量扩张问题研究[D]. 武汉: 华中科技大学, 2007.
3	LiJ P,ZhuJ P.The capacity expansion path problem in networks[J].Journal of Applied Mathematics,2013,7(16):361-376.
4	杨宇. 有向网络中最大容量树形图扩容问题[D]. 昆明: 云南大学, 2011.
5	朱娟萍. 限制性网络扩容问题[D]. 昆明: 云南大学, 2011.
6	李彬,张洁,陈宋宋,等.基于复杂网络的电力通信网扩容保护策略[J].电网技术,2018,42(6):1974-1980.
7	王凌风,卢国潇.基于帕累托法则的网络负荷扩容研究[J].邮电设计技术,2019,7,54-59.
8	FragkosL,CordeauJ F,JansR.Decomposition methods for large-scale network expansion problems[J].Transportation Research Part B,2021,144,60-80. doi: 10.1016/j.trb.2020.12.002
9	张国清,程苏琦.小世界网络中的删边扩容效应[J].中国科学: 信息科学,2012,42(2):151-160.
10	赵焱鑫,李黎,王小明.复杂网络加边扩容策略研究[J].计算机应用研究,2015,32(6):1839-1841. doi: 10.3969/j.issn.1001-3695.2015.06.053
11	FulkersonD R.Increasing the capacity of a network: The parametric budget problem[J].Management Science,1959,5(4):472-483. doi: 10.1287/mnsc.5.4.472
12	SchwarzS,KrumkeS O.On budget—constrained flow improvement[J].Information Proccssing Letters,1998,66,291-297. doi: 10.1016/S0020-0190(98)00070-2
13	YangC,LiuJ L.A capacity expansion problem with budget constraint and bottleneck limitation[J].Acta Mathematica Scientia,2002,22(2):207-212. doi: 10.1016/S0252-9602(17)30473-3
14	ZhangJ Z,YangC,LinY X.A class of bottleneck expansion problems[J].Computers & Operations Research,2001,28(6):505-519.
15	ZhangJ Z,LiuJ L.An oracle strongly polynomial algorithm for bottleneck expansion problems[J].Operation Methods and Software,2002,17(1):61-75. doi: 10.1080/10556780290027819
16	YangC,ZhangJ Z.On the bottleneck capacity expansion problems on networks[J].Acta Mathematica Scientia,2006,26B(2):202-208.
17	TaghaviM,HuangK.A Lagrangian relaxation approach for stochastic network capacity expansion with budget constraints[J].Annals of Operations Research,2020,284,605-621. doi: 10.1007/s10479-018-2862-7
18	田丰,马仲蕃.图与网络流理论[M].北京:科学出版社,1987.
19	ChuY J,LiuT H.On the shortest arborescence of a directed graph[J].Science Sinica,1965,14,1396-1400.
20	EdmondsJ.Optimum branchings[J].Research of the National Bureau of Standards,1967,71B,233-240. doi: 10.6028/jres.071B.032

[1]	Binwu ZHANG, Xiucui GUAN. The bounded inverse optimal value problem on minimum spanning tree under unit infinity norm [J]. Operations Research Transactions, 2022, 26(3): 44-56.
[2]	Chenghao ZHOU, Boxuan LYU, Hanyu ZHOU, Haiyan LU. Optimization model and algorithm for Online to Offline dynamic take-out delivery routing problem centered on business districts [J]. Operations Research Transactions, 2022, 26(3): 17-30.
[3]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[4]	LU Shuxiang, Lü Changhong, QIN Tao. An algorithm based on makespan lower bound for quay crane schedule problem in container terminals [J]. Operations Research Transactions, 2020, 24(3): 67-76.
[5]	CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices [J]. Operations Research Transactions, 2020, 24(2): 131-144.
[6]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[7]	ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates [J]. Operations Research Transactions, 2019, 23(2): 67-74.
[8]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[9]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.
[10]	XU Dachuan, XU Yicheng, ZHANG Dongmei. A survey on algorithms for k-means problem and its variants [J]. Operations Research Transactions, 2017, 21(2): 101-109.
[11]	ZHANG Long. Two-stage supply chain scheduling with a limited holding time [J]. Operations Research Transactions, 2017, 21(2): 126-134.
[12]	MIAO Cuixia, MENG Fanxiao. Two-machine flow-shop scheduling with deterioration and rejection [J]. Operations Research Transactions, 2017, 21(2): 66-72.
[13]	FAN Jing, ZHANG Feng. Supply chain scheduling problem with multiple unavailability intervals on a single machine [J]. Operations Research Transactions, 2015, 19(3): 116-122.
[14]	ZHONG Weiya, MA Wenhui, HUO Zhiming. A preemptive multiprocessor order parallel machine scheduling problem [J]. Operations Research Transactions, 2013, 17(3): 115-123.
[15]	ZHONG Wei-Ya, LIU Xiao-Lei, Huo-Zhi-Ming. A Single Machine Scheduling Problem with Subcontracting Options [J]. Operations Research Transactions, 2012, 16(1): 121-128.

The expansion problem of maximum capacity spanning arborescence in networks

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 1

References 20

Related Articles 15

Recommended Articles

Metrics

Comments