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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2006
منشور خارجيًانعم
الحدث14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, سويسرا
المدة: ١١ سبتمبر ٢٠٠٦١٣ سبتمبر ٢٠٠٦

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت4168 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference14th Annual European Symposium on Algorithms, ESA 2006


أدرس بدقة موضوعات البحث “Resource allocation in bounded degree trees'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا