The Library
Online algorithms for multi-level aggregation
Tools
Bienkowski, Marcin, Böhm, Martin, Byrka, Jaroslaw, Chrobak, Marek, Dürr, Christoph, Folwarczný, Lukáš, Jeż, Łukasz, Sgall, Jiří, Kim Thang, Nguyen and Veselý, Pavel (2020) Online algorithms for multi-level aggregation. Operations Research, 68 (1). pp. 214-232. doi:10.1287/opre.2019.1847 ISSN 0030-364X.
|
PDF
WRAP-online-algorithms-multi-level-aggregation-Veselý-2019.pdf - Accepted Version - Requires a PDF viewer. Download (889Kb) | Preview |
Official URL: https://doi.org/10.1287/opre.2019.1847
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(D42D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.
Item Type: | Journal Article | |||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Online algorithms, Approximation theory | |||||||||||||||||||||||||||
Journal or Publication Title: | Operations Research | |||||||||||||||||||||||||||
Publisher: | Institute for Operations Research and the Management Sciences (I N F O R M S) | |||||||||||||||||||||||||||
ISSN: | 0030-364X | |||||||||||||||||||||||||||
Official Date: | 2 January 2020 | |||||||||||||||||||||||||||
Dates: |
|
|||||||||||||||||||||||||||
Volume: | 68 | |||||||||||||||||||||||||||
Number: | 1 | |||||||||||||||||||||||||||
Page Range: | pp. 214-232 | |||||||||||||||||||||||||||
DOI: | 10.1287/opre.2019.1847 | |||||||||||||||||||||||||||
Status: | Peer Reviewed | |||||||||||||||||||||||||||
Publication Status: | Published | |||||||||||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||||||||||||||
Copyright Holders: | © 2020, INFORMS | |||||||||||||||||||||||||||
Date of first compliant deposit: | 28 March 2019 | |||||||||||||||||||||||||||
Date of first compliant Open Access: | 12 June 2019 | |||||||||||||||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year