Online algorithms for multilevel aggregation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F20%3A00522116" target="_blank" >RIV/67985840:_____/20:00522116 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/20:10412570

Výsledek na webu

<a href="https://doi.org/10.1287/opre.2019.1847" target="_blank" >https://doi.org/10.1287/opre.2019.1847</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1287/opre.2019.1847" target="_blank" >10.1287/opre.2019.1847</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Online algorithms for multilevel aggregation

Popis výsledku v původním jazyce

In the multilevel aggregation problem (MLAP), requests arrive at the nodes of an edge-weighted tree J and have to be served eventually. A service is defined as a subtree X of J that contains the root of J. 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 subbees. 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 J. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.

Název v anglickém jazyce

Online algorithms for multilevel aggregation

Popis výsledku anglicky

In the multilevel aggregation problem (MLAP), requests arrive at the nodes of an edge-weighted tree J and have to be served eventually. A service is defined as a subtree X of J that contains the root of J. 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 subbees. 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 J. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-09142S" target="_blank" >GA17-09142S: Moderní algoritmy: Nové výzvy komplexních dat</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2020

Kód důvěrnosti údajů

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

Název periodika

Operations Research

ISSN

0030-364X

e-ISSN

—

Svazek periodika

68

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

19

Strana od-do

214-232

Kód UT WoS článku

000509473400012

EID výsledku v databázi Scopus

2-s2.0-85084941156