New results on multi-level aggregation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F21%3A00540790" target="_blank" >RIV/67985840:_____/21:00540790 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/21:10431447

Výsledek na webu

<a href="https://doi.org/10.1016/j.tcs.2021.02.016" target="_blank" >https://doi.org/10.1016/j.tcs.2021.02.016</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2021.02.016" target="_blank" >10.1016/j.tcs.2021.02.016</a>

Jazyk výsledku

angličtina

Název v původním jazyce

New results on multi-level aggregation

Popis výsledku v původním jazyce

In the Multi-Level Aggregation Problem (MLAP ), requests for service arrive at the nodes of an edge-weighted rooted tree T. Each service is represented by a subtree X of T that contains its root. 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 a waiting cost between its arrival and service time. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. The currently best online algorithms for the MLAP achieve competitive ratios polynomial in the tree depth, while the best lower bound is only 3.618. In this paper, we report some progress towards closing this gap, by improving this lower bound and providing several tight bounds for restricted variants of MLAP: (1) We first study a Single-Phase variant of MLAP where all requests are released at the beginning and expire at some unknown time θ, for which we provide an online algorithm with optimal competitive ratio of 4. (2) We prove a lower bound of 4 on the competitive ratio for MLAP, even when the tree is a path. We complement this with a matching upper bound for the deadline variant of MLAP on paths. Additionally, we provide two results for the offline case: (3) We prove that the Single-Phase variant can be solved optimally in polynomial time, and (4) we give a simple 2-approximation algorithm for offline MLAP with deadlines.

Název v anglickém jazyce

New results on multi-level aggregation

Popis výsledku anglicky

In the Multi-Level Aggregation Problem (MLAP ), requests for service arrive at the nodes of an edge-weighted rooted tree T. Each service is represented by a subtree X of T that contains its root. 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 a waiting cost between its arrival and service time. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. The currently best online algorithms for the MLAP achieve competitive ratios polynomial in the tree depth, while the best lower bound is only 3.618. In this paper, we report some progress towards closing this gap, by improving this lower bound and providing several tight bounds for restricted variants of MLAP: (1) We first study a Single-Phase variant of MLAP where all requests are released at the beginning and expire at some unknown time θ, for which we provide an online algorithm with optimal competitive ratio of 4. (2) We prove a lower bound of 4 on the competitive ratio for MLAP, even when the tree is a path. We complement this with a matching upper bound for the deadline variant of MLAP on paths. Additionally, we provide two results for the offline case: (3) We prove that the Single-Phase variant can be solved optimally in polynomial time, and (4) we give a simple 2-approximation algorithm for offline MLAP with deadlines.

Druh

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

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

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

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

1879-2294

Svazek periodika

861

Číslo periodika v rámci svazku

March 12

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

11

Strana od-do

133-143

Kód UT WoS článku

000621869300009

EID výsledku v databázi Scopus

2-s2.0-85101328071