O(depth)-Competitive algorithm for online multi-level aggregation

Niv Buchbinder, Moran Feldman, Joseph Naor, Ohad Talmon

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

We consider a multi-level aggregation problem in a weighted rooted tree, studied recently by Bienkowski et al. [7]. In this problem requests arrive over time at the nodes of the tree, and each request specifies a deadline. A request is served by sending it to the root before its deadline at a cost equal to the weight of the path from the node in which it resides to the root. However, requests from different nodes can be aggregated, and served together, so as to save on cost. The cost of serving an aggregated set of requests is equal to the weight of the subtree spanning the nodes in which the requests reside. Thus, the problem is to find a competitive online aggregation algorithm that minimizes the total cost of the aggregated requests. This problem arises naturally in many scenarios, including multicasting, supply- chain management and sensor networks. It is also related to the well studied TCP-acknowledgement problem and the online joint replenishment problem. We present an online O(D)-competitive algorithm for the problem, where D is the depth, or number of levels, of the aggregation tree. This result improves upon the D22D- competitive algorithm obtained recently by Bienkowski et al. [7].

שפה מקוריתאנגלית
כותר פרסום המארח28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
עורכיםPhilip N. Klein
מוציא לאורAssociation for Computing Machinery
עמודים1235-1244
מספר עמודים10
מסת"ב (אלקטרוני)9781611974782
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2017
אירוע28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, ספרד
משך הזמן: 16 ינו׳ 201719 ינו׳ 2017

סדרות פרסומים

שםProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
כרך0

כנס

כנס28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
מדינה/אזורספרד
עירBarcelona
תקופה16/01/1719/01/17

הערה ביבליוגרפית

Publisher Copyright:
Copyright © by SIAM.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'O(depth)-Competitive algorithm for online multi-level aggregation'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי