Approximation schemes for broadcasting in heterogeneous networks

S. Khuller; Y.-A. Kim; G.J. Woeginger

doi:10.1007/978-3-540-27821-4_15

Approximation schemes for broadcasting in heterogeneous networks

S. Khuller, Y.-A. Kim, G.J. Woeginger

Combinatorial Optimization

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

Abstract

We study the problem of minimizing the broadcast time for a set of processors in a cluster, where processor p i has transmission time t i , which is the time taken to send a message to any other processor in the cluster. Previously, it was shown that the Fastest Node First method (FNF) gives a 1.5 approximate solution. In this paper we show that there is a polynomial time approximation scheme for the problems of broadcasting and multicasting in such a heterogenous cluster.

Original language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Proceedings APPROX 2004 and RANDOM 2004, Cambridge MA, USA, August 22-24, 2004)
Editors	K. Jansen, xx et al.
Place of Publication	Berlin
Publisher	Springer
Pages	163-170
ISBN (Print)	978-3-540-22894-3
DOIs	https://doi.org/10.1007/978-3-540-27821-4_15
Publication status	Published - 2004

Publication series

Name	Lecture Notes in Computer Science
Volume	3122
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-540-27821-4_15

Cite this

Khuller, S., Kim, Y-A., & Woeginger, G. J. (2004). Approximation schemes for broadcasting in heterogeneous networks. In K. Jansen, & X. et al. (Eds.), Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Proceedings APPROX 2004 and RANDOM 2004, Cambridge MA, USA, August 22-24, 2004) (pp. 163-170). (Lecture Notes in Computer Science; Vol. 3122). Springer. https://doi.org/10.1007/978-3-540-27821-4_15

Khuller, S. ; Kim, Y.-A. ; Woeginger, G.J. / Approximation schemes for broadcasting in heterogeneous networks. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Proceedings APPROX 2004 and RANDOM 2004, Cambridge MA, USA, August 22-24, 2004). editor / K. Jansen ; xx et al. Berlin : Springer, 2004. pp. 163-170 (Lecture Notes in Computer Science).

@inproceedings{35832dcf663442d0883276ca581fee80,

title = "Approximation schemes for broadcasting in heterogeneous networks",

abstract = "We study the problem of minimizing the broadcast time for a set of processors in a cluster, where processor p i has transmission time t i , which is the time taken to send a message to any other processor in the cluster. Previously, it was shown that the Fastest Node First method (FNF) gives a 1.5 approximate solution. In this paper we show that there is a polynomial time approximation scheme for the problems of broadcasting and multicasting in such a heterogenous cluster.",

author = "S. Khuller and Y.-A. Kim and G.J. Woeginger",

year = "2004",

doi = "10.1007/978-3-540-27821-4_15",

language = "English",

isbn = "978-3-540-22894-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "163--170",

editor = "K. Jansen and {et al.}, xx",

booktitle = "Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Proceedings APPROX 2004 and RANDOM 2004, Cambridge MA, USA, August 22-24, 2004)",

address = "Germany",

}

Khuller, S, Kim, Y-A & Woeginger, GJ 2004, Approximation schemes for broadcasting in heterogeneous networks. in K Jansen & X et al. (eds), Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Proceedings APPROX 2004 and RANDOM 2004, Cambridge MA, USA, August 22-24, 2004). Lecture Notes in Computer Science, vol. 3122, Springer, Berlin, pp. 163-170. https://doi.org/10.1007/978-3-540-27821-4_15

Approximation schemes for broadcasting in heterogeneous networks. / Khuller, S.; Kim, Y.-A.; Woeginger, G.J.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Proceedings APPROX 2004 and RANDOM 2004, Cambridge MA, USA, August 22-24, 2004). ed. / K. Jansen; xx et al. Berlin: Springer, 2004. p. 163-170 (Lecture Notes in Computer Science; Vol. 3122).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximation schemes for broadcasting in heterogeneous networks

AU - Khuller, S.

AU - Kim, Y.-A.

AU - Woeginger, G.J.

PY - 2004

Y1 - 2004

N2 - We study the problem of minimizing the broadcast time for a set of processors in a cluster, where processor p i has transmission time t i , which is the time taken to send a message to any other processor in the cluster. Previously, it was shown that the Fastest Node First method (FNF) gives a 1.5 approximate solution. In this paper we show that there is a polynomial time approximation scheme for the problems of broadcasting and multicasting in such a heterogenous cluster.

AB - We study the problem of minimizing the broadcast time for a set of processors in a cluster, where processor p i has transmission time t i , which is the time taken to send a message to any other processor in the cluster. Previously, it was shown that the Fastest Node First method (FNF) gives a 1.5 approximate solution. In this paper we show that there is a polynomial time approximation scheme for the problems of broadcasting and multicasting in such a heterogenous cluster.

U2 - 10.1007/978-3-540-27821-4_15

DO - 10.1007/978-3-540-27821-4_15

M3 - Conference contribution

SN - 978-3-540-22894-3

T3 - Lecture Notes in Computer Science

SP - 163

EP - 170

BT - Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Proceedings APPROX 2004 and RANDOM 2004, Cambridge MA, USA, August 22-24, 2004)

A2 - Jansen, K.

A2 - et al., xx

PB - Springer

CY - Berlin

ER -

Khuller S, Kim Y-A, Woeginger GJ. Approximation schemes for broadcasting in heterogeneous networks. In Jansen K, et al. X, editors, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Proceedings APPROX 2004 and RANDOM 2004, Cambridge MA, USA, August 22-24, 2004). Berlin: Springer. 2004. p. 163-170. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-27821-4_15

Approximation schemes for broadcasting in heterogeneous networks

Abstract

Publication series

Access to Document

Fingerprint

Cite this