Competitive non-preemptive call control
Baruch Awerbuch, Yair Bartal, Amos Fiat, Adi Rosén · 1994
We deal with randomized competitive algorithms for non-preemptive call control on tree-like switching networks. We give an O(log n) competitive algorithm for nonpreemptive call scheduling on trees. We then introduce the complexities of variable call rates, call durations, and arbitrary call benefits, resulting in a polylog competitive algorithm for the combined problem. We also show that many algorithms for similar problems that can deal with fixed parameters such as rates and benefits can be randomly transformed to deal with variable values of the parameters. Using randomization, this extends the work of [GGKMY] on call control for the line network to tree networks, without the preemption requirement, and while allowing arbitrary benefits, arbitrary rates, and arbitrary capacities on the links. Alternately, this can be viewed as a generalization of [AAP] for throughput competitive routing, limited to trees, but without the limitation of requiring that communication request ...