Resource allocation in bounded degree trees

Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, Dror Rawitz

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


We study the bandwidth allocation problem (BAP) in bounded degree trees. In this problem we are given a tree and a set of connection requests. Each request consists of a path in the tree, a bandwidth requirement, and a weight. Our goal is to find a maximum weight subset S of requests such that, for every edge e, the total bandwidth of requests in S whose path contains e is at most 1. We also consider the storage allocation problem (SAP), in which it is also required that every request in the solution is given the same contiguous portion of the resource in every edge in its path. We present a deterministic approximation algorithm for BAP in bounded degree trees with ratio (2√e - 1)/(√e - 1)+ε < 3.542. Our algorithm is based on a novel application of the local ratio technique in which the available bandwidth is divided into narrow strips and requests with very small bandwidths are allocated in these strips. We also present a randomized (2 + ε)-approximation algorithm for BAP in bounded degree trees. The best previously known ratio for BAP in general trees is 5. We present a reduction from SAP to BAP that works for instances where the tree is a line and the bandwidths are very small. It follows that there exists a (2 + ε)-approximation algorithm for SAP in the line. The best previously known ratio for this problem is 7.

שפה מקוריתאנגלית
כותר פרסום המארחAlgorithms, ESA 2006 - 14th Annual European Symposium, Proceedings
מוציא לאורSpringer Verlag
מספר עמודים12
מסת"ב (מודפס)3540388753, 9783540388753
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2006
פורסם באופן חיצוניכן
אירוע14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, שוויץ
משך הזמן: 11 ספט׳ 200613 ספט׳ 2006

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

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך4168 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349


כנס14th Annual European Symposium on Algorithms, ESA 2006

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Resource allocation in bounded degree trees'. יחד הם יוצרים טביעת אצבע ייחודית.

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