A new hybrid GRASP with the pilot method for the delay-constrained multicast routing problem

被引：0
作者：
Xu, Ying [1 ]
Zheng, Xiongfei [1 ]
Li, Renfa [1 ]
机构：
[1] Hunan Univ, Coll Informat Sci & Engn, Changsha 410082, Hunan, Peoples R China
来源：
PROCEEDINGS OF THE 2ND INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION APPLICATIONS (ICCIA 2012) | 2012年
关键词：
GRASP(Greedy Randomised Adaptive Search Procedure); Pilot Method; Multicast Routing; ALGORITHM;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Multicast routing problem is a well know optimization problem for transmitting real-time multimedia applications in telecommunication networks. As the underpinning mathematical model, the constrained minimum Steiner tree problem in graphs is a well-known NP-complete problem. In this paper we investigate a new hybrid GRASP (Greedy Randomized Adaptive Search Procedure) approach where a pilot method is applied to further enhance the search for the Delay-Constrained Least-Cost (DCLC) multicast routing problem. Experimental results demonstrate the efficiency of the hybrid GRASP algorithm and the contributions of the post-processing pilot method to better solutions in most cases. The proposed GRASP approach is a competitive approach in solving the DCLC multicast routing problem.
引用
收藏
页码：410 / 414
页数：5
相关论文
共 44 条
  • [1] [Anonymous], P 2 INT C COMP COMM
  • [2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
  • [3] AN SST-BASED ALGORITHM FOR THE STEINER PROBLEM IN GRAPHS
    BEASLEY, JE
    [J]. NETWORKS, 1989, 19 (01) : 1 - 16
  • [4] Rollout Algorithms for Combinatorial Optimization
    Bertsekas D.P.
    Tsitsiklis J.N.
    Wu C.
    [J]. Journal of Heuristics, 1997, 3 (3) : 245 - 262
  • [5] Cheng X., 2001, Steiner trees in Industry
  • [6] Multipoint communication: A survey of protocols, functions, and mechanisms
    Diot, C
    Dabbous, W
    Crowcroft, J
    [J]. IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 1997, 15 (03) : 277 - 290
  • [7] Duin G, 1999, NETWORKS, V34, P181, DOI 10.1002/(SICI)1097-0037(199910)34:3<181::AID-NET2>3.0.CO
  • [8] 2-Y
  • [9] Finding the k shortest paths
    Eppstein, D
    [J]. SIAM JOURNAL ON COMPUTING, 1998, 28 (02) : 652 - 673
  • [10] GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES
    FEO, TA
    RESENDE, MGC
    [J]. JOURNAL OF GLOBAL OPTIMIZATION, 1995, 6 (02) : 109 - 133
12345