direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Journal and Magazine Articles

Tight Bounds for Delay-Sensitive Aggregation
Zitatschlüssel PSW-TBDSA-10
Autor Pignolet, Yvonne Anne and Schmid, Stefan and Wattenhofer, Roger
Seiten 39–58
Jahr 2010
ISSN 1365-8050
Journal Discrete Mathematics and Theoretical Computer Science Journal
Jahrgang 12
Nummer 1
Monat February
Zusammenfassung This article studies the fundamental trade-off between delay and communication cost in networks. We consider an online optimization problem where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about the changes of their states and to use as few transmissions as possible. We derive an upper bound on the competitive ratio of O(min(h,c)) where h is the tree's height, and c is the transmission cost per edge. Moreover, we prove that this upper bound is tight in the sense that any oblivious algorithm has a ratio of at least Ω(min(h,c)). For chain networks, we prove a tight competitive ratio of Θ(min(radic(h),c)). Furthermore, we introduce a model for value-sensitive aggregation, where the cost depends on the number of transmissions and the error at the root.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang:

Schnellnavigation zur Seite über Nummerneingabe