Approximation Schemes for Broadcasting in Heterogenous Networks

Samir Khuller; Yoo Ah Kim; Gerhard Woeginger

Approximation Schemes for Broadcasting in Heterogenous Networks

Samir Khuller^*, Yoo Ah Kim, Gerhard Woeginger

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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 (US)
Pages (from-to)	163-170
Number of pages	8
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3122
State	Published - Dec 1 2004

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Cite this

@article{a255c779b1df4aae9e2561a629e12836,

title = "Approximation Schemes for Broadcasting in Heterogenous Networks",

abstract = "We study the problem of minimizing the broadcast time for a set of processors in a cluster, where processor pi has transmission time ti, 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 = "Samir Khuller and Kim, {Yoo Ah} and Gerhard Woeginger",

year = "2004",

month = dec,

day = "1",

language = "English (US)",

volume = "3122",

pages = "163--170",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - Approximation Schemes for Broadcasting in Heterogenous Networks

AU - Khuller, Samir

AU - Kim, Yoo Ah

AU - Woeginger, Gerhard

PY - 2004/12/1

Y1 - 2004/12/1

N2 - We study the problem of minimizing the broadcast time for a set of processors in a cluster, where processor pi has transmission time ti, 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 pi has transmission time ti, 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.

UR - http://www.scopus.com/inward/record.url?scp=34547251951&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34547251951&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:34547251951

VL - 3122

SP - 163

EP - 170

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -

Approximation Schemes for Broadcasting in Heterogenous Networks

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this