Trade‐offs Between the Size of Advice and Broadcasting Time in Trees

Trade‐offs Between the Size of Advice and Broadcasting Time in Trees

0.00 Avg rating0 Votes
Article ID: iaor20115139
Volume: 60
Issue: 4
Start Page Number: 719
End Page Number: 734
Publication Date: Aug 2011
Journal: Algorithmica
Authors: ,
Keywords: communication, networks
Abstract:

We study the problem of the amount of information required to perform fast broadcasting in tree networks. The source located at the root of a tree has to disseminate a message to all nodes. In each round each informed node can transmit to one child. Nodes do not know the topology of the tree but an oracle knowing it can give a string of bits of advice to the source which can then pass it down the tree with the source message. The quality of a broadcasting algorithm with advice is measured by its competitive ratio: the worst case ratio, taken over n‐node trees, between the time of this algorithm and the optimal broadcasting time in the given tree. Our goal is to find a trade‐off between the size of advice and the best competitive ratio of a broadcasting algorithm for n‐node trees. We establish such a trade‐off with an approximation factor of O(n ϵ ), for an arbitrarily small positive constant ϵ. This is the first communication problem for which a trade‐off between the size of advice and the efficiency of the solution is shown for arbitrary size of advice.

Reviews

Required fields are marked *. Your email address will not be published.