Iglesias, Jennifer ;
Rajaraman, Rajmohan ;
Ravi, R. ;
Sundaram, Ravi
Rumors Across Radio, Wireless, Telephone
Abstract
We study the problem of computing a minimum time schedule to spread rumors in a given graph under several models: In the radio model, all neighbors of a transmitting node listen to the messages and are able to record it only when no other neighbor is transmitting; In the wireless model (also called the edgestar model), each transmitter is at a different frequency to which any neighbor can tune to, but only one neighboring transmission can be accessed in this way; In the telephone model, the set of transmitterreceiver pairs form a matching in the graph. The rumor spreading problems assume a message at one or several nodes of the graph that must reach a target node or set of nodes. The transmission proceeds in synchronous rounds under the rules of the corresponding model. The goal is to compute a schedule that completes in the minimum number of rounds.
We present a comprehensive study of approximation algorithms for these problems, and show several reductions from the harder to the easier models for special demands. We show a new hardness of approximation of Omega(n^1/2  epsilon) for the minimum radio gossip time by a connection to maximum induced matchings. We give the first sublinear approximation algorithms for the most general case of the problem under the wireless model; we also consider various special cases such as instances with symmetric demands and give better approximation algorithms. Our work exposes the relationships across the models and opens up several new avenues for further study.
BibTeX  Entry
@InProceedings{iglesias_et_al:LIPIcs:2015:5638,
author = {Jennifer Iglesias and Rajmohan Rajaraman and R. Ravi and Ravi Sundaram},
title = {{Rumors Across Radio, Wireless, Telephone}},
booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
pages = {517528},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897972},
ISSN = {18688969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5638},
URN = {urn:nbn:de:0030drops56383},
doi = {10.4230/LIPIcs.FSTTCS.2015.517},
annote = {Keywords: Broadcast, Gossip, Approximation algorithms, Graph algorithms, Hardness of Approximation}
}
2015
Keywords: 

Broadcast, Gossip, Approximation algorithms, Graph algorithms, Hardness of Approximation 
Seminar: 

35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Issue date: 

2015 
Date of publication: 

2015 