Online control message aggregation in chain networks

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F13%3A00424763" target="_blank" >RIV/67985840:_____/13:00424763 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-642-40104-6_12" target="_blank" >http://dx.doi.org/10.1007/978-3-642-40104-6_12</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-40104-6_12" target="_blank" >10.1007/978-3-642-40104-6_12</a>

Result language
angličtina
Original language name
Online control message aggregation in chain networks
Original language description
In the Control Message Aggregation (CMA) problem, control packets are generated over time at the nodes of a tree T and need to be transmitted to the root of T. To optimize the overall cost, these transmissions can be delayed and different packets can beaggregated, that is a single transmission can include all packets from a subtree rooted at the root of T. The cost of this transmission is then equal to the total edge length of this subtree, independently of the number of packets that are sent. A sequence of transmissions that transmits all packets is called a schedule. The objective is to compute a schedule with minimum cost, where the cost of a schedule is the sum of all the transmission costs and delay costs of all packets. The problem is known to be NP -hard, even for trees of depth 2. In the online scenario, it is an open problem whether a constant-competitive algorithm exists.
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)