Number of the records: 1
Online control message aggregation in chain networks
- 1.
SYSNO ASEP 0424763 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title Online control message aggregation in chain networks Author(s) Bienkowski, M. (PL)
Byrka, J. (PL)
Chrobak, M. (US)
Jeż, Ł. (PL)
Sgall, Jiří (MU-W) RID, ORCID, SAI
Stachowiak, G. (PL)Source Title Algorithms and Data Structures. - Berlin : Springer, 2013 / Dehne F. ; Solis-Oba R. ; Sack J.-R. - ISSN 0302-9743 - ISBN 978-3-642-40103-9 Pages s. 133-145 Number of pages 13 s. Publication form Print - P Action International Symposium, WADS 2013, /13./ Event date 12.08.2013-14.08.2013 VEvent location London Country CA - Canada Event type WRD Language eng - English Country DE - Germany Keywords chain networks ; control messages ; control packets Subject RIV BA - General Mathematics R&D Projects IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) GBP202/12/G061 GA ČR - Czech Science Foundation (CSF) EID SCOPUS 84881179034 DOI 10.1007/978-3-642-40104-6_12 Annotation 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 be aggregated, 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2014
Number of the records: 1