I Multi-Level Aggregering Problem (MLAP), förfrågningar anländer till noderna i en kantviktad träd T, och måste serveras så småningom. En tjänst definieras som ett underträd X av T som innehåller dess rot. Detta underträd X tjänar alla förfrågningar som väntar i noderna av X, och kostnaden för denna tjänst är lika med den totala vikten av X. Varje begäran medför också kostnader i väntan mellan ankomst och tjänstetid. Målet är att minimera den totala väntekostnaden för alla förfrågningar plus den totala kostnaden för alla servicesubträd. MLAP är en generalisering av några välstuderade optimeringsproblem; till exempel, för träd på djup 1, MLAP är likvärdig med TCP erkännande problem, medan för träd på djup 2, är det motsvarar Joint Replenishment Problem. Aggregeringsproblem för träd av godtyckligt djup uppstår i multicasting, sensornätverk, kommunikation i organisationshierarkier, och i försörjningskedja ledning. De fall av MLAP som är förknippade med dessa ansökningar är naturligtvis online, i den meningen att aggregering beslut måste fattas utan information om framtida förfrågningar. Ständigt konkurrenskraftiga online-algoritmer är kända för MLAP med en eller två nivåer. Det har dock varit öppet om det finns konstant konkurrenskraftiga online-algoritmer för träd på djup mer än 2. Ta itu med detta öppna problem, ger vi den första konstant konkurrenskraftiga online-algoritm för träd av godtyckliga (fasta) djup. Den konkurrenskraftiga förhållandet är O(D 4 2 D ), där D är djupet av T. Algoritmen arbetar för godtyckliga vänta kostnadsfunktioner, inklusive varianten med deadlines. Vi inkluderar flera ytterligare resultat i tidningen. Vi visar att en standard teknik med lägre bindningsgrad för MLAP, baserad på så kallade Single-Phase-fall, inte kan ge superkonstanta nedre gränser (som en funktion av träddjupet). Detta resultat etableras genom att ge en online-algoritm med optimal konkurrens förhållande 4 för sådana fall på godtyckliga träd. Vi bevisar att, i offline fallet, dessa fall kan lösas till optimalitet i polynom tid. Vi studerar också MLAP-varianten när trädet är en väg, för vilken vi ger en lägre gräns på 4 på konkurrensförhållandet, förbättra den nedre gränsen känd för allmänna MLAP. Vi kompletterar detta med en matchande övre gräns för deadline inställning. Dessutom, för godtyckliga träd, ger vi en enkel 2- approximation algoritm för offline MLAP med deadlines.
Slutligen, när aggregeringsträdet är en oändlig halv linje, Bienkowski et al. REF gav en 4-konkurrensalgoritm för deadlineversionen av problemet, och visade att detta är det bästa möjliga.
Online Algorithms for Multi-Level Aggregation
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}