Lower Bounds for Two Call Control Problems

We present lower bounds for two call control scheduling problems. For the problem of scheduling infinite-duration calls deterministically without pre-emption on a linear array of processors, in which the goal is to use as many edges as possible, we show a 2OE + 1 ß 4:2 lower bound on the competitive ratio (where OE is the golden ratio). For the problem of scheduling infinite-duration calls on an edge of capacity 1 with randomization but no pre-emption, such that calls have bandwidth between 1=B and 1, we show a (log B)=2 lower bound. Keywords: Algorithms, Call Control, Scheduling 1 Introduction The call admission problem is the problem of determining whether an incoming call should be accepted to a communication network, or whether it should be rejected in order to preserve resources for future calls. A call admission algorithm must accept or reject each call in an on-line manner, i.e., before seeing any future calls. Algorithms are evaluated using the competitive ratio, defined by Sl..