2006 | OriginalPaper | Buchkapitel
Resource Allocation in Bounded Degree Trees
verfasst von : Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, Dror Rawitz
Erschienen in: Algorithms – ESA 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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\sqrt{e}-1)/(\sqrt{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.