林永松2006-07-262018-06-292006-07-262018-06-292005http://ntur.lib.ntu.edu.tw//handle/246246/18847In this report, we attempt to solve the problem of min-cost multi-cast routing for multi-layered multimedia distribution. More specifically, for (i) a given network topology (ii) the destinations of a multicast group and (iii) the bandwidth requirement of each destination, we attempt to find a feasible routing solution to minimize the cost of a multicast tree for multi-layered mul-timedia distribution. This problem has been proved to be NP-hard. We pro-pose two adjustment procedures, namely: the tie breaking procedure and the drop-and-add procedure to enhance the solution quality of the modified T-M heuristic. We also formally model this problem as an optimization problem and apply the Lagrangean relaxation method and the subgradient method to solve the problem. Computational experiments are performed on regular net-works, random networks, and scale-free networks. According to the experi-ment results, the Lagrangean based heuristic can achieve up to 23.23% im-provement compared to the M-T-M heuristic.application/pdf275287 bytesapplication/pdfzh-TW國立臺灣大學資訊管理學系暨研究所otherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/18847/1/932213E002111.pdf