License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2015.517
URN: urn:nbn:de:0030-drops-56383
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5638/
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 edge-star 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 transmitter-receiver 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 = {517--528},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-97-2},
ISSN = {1868-8969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5638},
URN = {urn:nbn:de:0030-drops-56383},
doi = {10.4230/LIPIcs.FSTTCS.2015.517},
annote = {Keywords: Broadcast, Gossip, Approximation algorithms, Graph algorithms, Hardness of Approximation}
}
|
Keywords: |
|
Broadcast, Gossip, Approximation algorithms, Graph algorithms, Hardness of Approximation |
|
Collection: |
|
35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
14.12.2015 |
