Online Algorithms for Multilevel Aggregation

Marcin Bienkowski (), Martin Böhm (), Jaroslaw Byrka (), Marek Chrobak (), Christoph Dürr (), Lukáš Folwarczný (), Łukasz Jeż (), Jiří Sgall (), Nguyen Kim Thang () and Pavel Veselý ()
Additional contact information
Marcin Bienkowski: Institute of Computer Science, University of Wrocław, 50-137 Wrocław, Poland
Martin Böhm: CSLog, University of Bremen, 28359 Bremen, Germany, Computer Science Institute, Charles University, 118 00 Prague, Czech Republic
Jaroslaw Byrka: Institute of Computer Science, University of Wrocław, 50-137 Wrocław, Poland
Marek Chrobak: Department of Computer Science, University of California, Riverside, Riverside, California 92521
Christoph Dürr: Laboratoire d’Informatique de Paris 6, Sorbonne Université, Centre National de la Recherche Scientifique, 75252 Paris, France
Lukáš Folwarczný: Computer Science Institute, Charles University, 118 00 Prague, Czech Republic, Institute of Mathematics, Czech Academy of Sciences, 110 00 Prague, Czech Republic
Łukasz Jeż: Institute of Computer Science, University of Wrocław, 50-137 Wrocław, Poland
Jiří Sgall: Computer Science Institute, Charles University, 118 00 Prague, Czech Republic
Nguyen Kim Thang: Laboratoire Informatique, Bio-informatique et Systèmes Complexes, Université d’Evry Val d’Essonne, 91034 Evry, France
Pavel Veselý: Computer Science Institute, Charles University, 118 00 Prague, Czech Republic, Department of Computer Science, University of Warwick, CV4 7AL Coventry, United Kingdom

Operations Research, 2020, vol. 68, issue 1, 214-232

Abstract: In the multilevel aggregation problem (MLAP), requests arrive at the nodes of an edge-weighted tree T and have to be served eventually. A service is defined as a subtree X of T that contains the root of T . This subtree X serves all requests that are pending in the nodes of X , and the cost of this service is equal to the total weight of X . Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the Transmission Control Protocol acknowledgment problem, whereas for trees of depth 2, it is equivalent to the joint replenishment problem. Aggregation problems for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and supply chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests. Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant-competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant-competitive online algorithm for trees of arbitrary (fixed) depth. The competitive ratio is O ( D 4 2 D ) , where D is the depth of T . The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.

Keywords: algorithmic aspects of networks; online algorithms; scheduling and resource allocation; lot sizing; multistage assembly problem (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1847 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:1:p:214-232

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().