Constrained maximum weighted bipartite matching: a novel approach to radio broadcast scheduling

doi:10.1007/s11432-017-9324-0

	Constrained maximum weighted bipartite matching: a novel approach to radio broadcast scheduling
	Wang, Shaojiang 1,2; Wu, Tianyong 1,2; Yao, Yuan 2,3; Bu, Dongbo 4; Cai, Shaowei 1,2
	2019-07-01
发表期刊	SCIENCE CHINA-INFORMATION SCIENCES
ISSN	1674-733X
卷号	62 期号:7 页码:14
摘要	Given a set of radio broadcast programs, the radio broadcast scheduling problem is to allocate a set of devices to transmit the programs to achieve the optimal sound quality. In this article, we propose a complete algorithm to solve the problem, which is based on a branch-and-bound (BnB) algorithm. We formulate the problem with a new model, called constrained maximum weighted bipartite matching (CMBM), i.e., the maximum matching problem on a weighted bipartite graph with constraints. For the reduced matching problem, we propose a novel BnB algorithm by introducing three new strategies, including the highest quality first, the least conflict first and the more edge first. We also establish an upper bound estimating function for pruning the search space of the algorithm. The experimental results show that our new algorithm can quickly find the optimal solution for the radio broadcast scheduling problem at small scales, and has higher scalability for the problems at large scales than the existing complete algorithm.
关键词	radio broadcast scheduling branch-and-bound algorithm constrained maximum weighted bipartite matching Kuhn-Munkres algorithm strategy combinations
DOI	10.1007/s11432-017-9324-0
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61772503] ; National Basic Research Program of China[2014CB340302]
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Information Systems ; Engineering, Electrical & Electronic
WOS记录号	WOS:000467502900001
出版者	SCIENCE PRESS
引用统计	被引频次：4[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/4240
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Cai, Shaowei
作者单位	1.Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 100190, Peoples R China 3.Chinese Acad Sci, Inst Software, Beijing Key Lab Human Comp Interact, Beijing 100190, Peoples R China 4.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Wang, Shaojiang,Wu, Tianyong,Yao, Yuan,et al. Constrained maximum weighted bipartite matching: a novel approach to radio broadcast scheduling[J]. SCIENCE CHINA-INFORMATION SCIENCES,2019,62(7):14.
APA	Wang, Shaojiang,Wu, Tianyong,Yao, Yuan,Bu, Dongbo,&Cai, Shaowei.(2019).Constrained maximum weighted bipartite matching: a novel approach to radio broadcast scheduling.SCIENCE CHINA-INFORMATION SCIENCES,62(7),14.
MLA	Wang, Shaojiang,et al."Constrained maximum weighted bipartite matching: a novel approach to radio broadcast scheduling".SCIENCE CHINA-INFORMATION SCIENCES 62.7(2019):14.