Telephone Connection (TC)

Input

A telephone line with a fixed channel capacity $k$, an integer $l$, and a sequence of calls $(s_1, f_1), \ldots, (s_n, f_n)$.

Problem

Is the $l^\text{th}$ call serviced?

Definitions

Here, $s_i$ ($f_i$) denotes the starting (respectively, finishing) time of the $i^\text{th}$ call. The $i^\text{th}$ call can be serviced at time $s_i$ if the number of calls being served at that time is less than $k$. If the call cannot be served, it is discarded. When a call is completed, a channel is freed up.

Status

Open (Ramachandran and Wang [1]).

Remarks

This problem is in $\CC$, that is, it is equivalent to CCVP. Ramachandran and Wang give an $O(\min(\sqrt{n}, k) \log n)$ time EREW-PRAM algorithm that uses $n$ processors for solving TC [1]. Also see NetSim.