Approximation Algorithms for Layered Multicast Scheduling

Autor:	Vincenzo Liberatore, Qingbo Cai
Rok vydání:	2005
Předmět:	Job shop scheduling Multicast Computer science Distributed computing Scalability Approximation algorithm Xcast Dissemination Telecommunications network Heterogeneous network Randomized algorithm Scheduling (computing)
Zdroj:	Algorithms and Computation ISBN: 9783540309352 ISAAC
DOI:	10.1007/11602613_97
Popis:	Layered multicast is a scalable solution to data dissemination in heterogeneous networks such as the Internet. In this paper, we study the scheduling problem arising in the layered multicast context. Our goal is to generate a multicast schedule for two different objectives, i.e., to minimize the weighted sum (the L1 objective) of the per-layer average waiting time, and to minimize the maximum approximation ratio (the L∞ objective) of the subschedules on individual layers. Compared to the previous work on multicast scheduling, this paper addresses the data popularity and the interaction among layers simultaneously. We present a simple randomized algorithm for both objectives of the layered multicast scheduling problem. For the L1 objective, we provide a deterministic 2-approximation algorithm for the general multi-layer cases. For the L∞ objective, we present an algorithm for the two-layer case which is 1.6875-approximation ignoring an additive constant.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::2f7a1ced83f686b646f56a84e4645c1d https://doi.org/10.1007/11602613_97 Zobrazit plný text záznamu