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.