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 ra-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(ne), for an arbitrarily small positive constant ε. This is the first problem for which a trade-off between the amount of provided information and the efficiency of the solution is shown for arbitrary size of advice. Copyright 2008 ACM.
Trade-offs between the size of advice and broadcasting time in trees / Fusco, EMANUELE GUIDO; Andrzej, Pelc. - STAMPA. - (2008), pp. 77-84. (Intervento presentato al convegno SPAA tenutosi a Munich; Germany nel June 14 - 16, 2008) [10.1145/1378533.1378545].
Trade-offs between the size of advice and broadcasting time in trees
FUSCO, EMANUELE GUIDO;
2008
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 ra-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(ne), for an arbitrarily small positive constant ε. This is the first problem for which a trade-off between the amount of provided information and the efficiency of the solution is shown for arbitrary size of advice. Copyright 2008 ACM.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.