Discrete Mathematics and Optimization Seminar
BRUCE SHEPHERD |
Bell Labs
To be rescheduled
Title. Demand-Packing Problems and Maximum Revenue Bandwidth Allocation.
Abstract.
The (currently decomissioned) agenda of bandwidth trading, asks for a market
where buyers and sellers of telecommunication bandwidth
can be matched
in real time. One core problem associated with this task, is that of packing
paths into a capacitated network. Each path comes with a demand,
and with a profit
that is obtained if the whole demand on the path can be satisfied. The main algorithmic
complication for such "demand problems"
is the all-or-nothing aspect to the packing.
We show a link between the demand version of such problems and their inherent
combinatorial packing
problem, when all demands are one. Namely, under certain assumptions,
the degree to which we can approximate the demand version is tied to that for the
unit-demand problem. These results also apply to arbitrary
packing problems.
We use these results to address the problem of bandwidth packing in a tree network.
When all demands and profits are 1, (i.e., maximum integer multicommodity flow
on a tree) Garg,
Vazirani, and Yannakakis had already given a 2-approximation algorithm for this problem.
We extend this to give a 4-approximation algorithm
for the weighted verion, and then
a constant approximation for the problem on a tree with non-unit demands.
We provide a number of open problems and directions.