We are given a path $P = (V,E)$ on $n$ nodes, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $I_i = [s_i,t_i]$ associated with it, where $s_i$ is the start vertex and $t_i$ is the end vertex. A set of requests $\mathcal{R}$ is called feasible, if the total demand of all requests in $\mathcal{R}$ passing through any edge $e$ does not exceed it's capacity, i.e., $\sum_{i:e \in R_i, R_i \in \mathcal{R}} d_i \le c_e$ for all $e \in E$. The goal is to partition the requests $R_1,\ldots,R_k$ into a number of sets such that each set is feasible and the total number of sets is minimized. We can think of this as coloring the requests in such a manner so that requests in each color class are feasible and we want to minimize the number of colors.
Let $r_e = \frac{\sum_{i:e \in R_i} d_i}{c_e}$ be the congestion on edge $e$ and let $r = \max_{e \in E} r_e$ be the maximum congestion. Clearly, $r$ is a lower bound on the number of colors required.
We consider the online scenario, where the requests are coming one after another, and we have to assign a color to each request upon its arrival. What is the best online algorithm and hardness result (lower bound) known for this problem? In particular, for small values of $r$ what is the number of colors required? For $r = 1$, one color is sufficient. For $r = 2$ and $r = 3$ can we do it with small number of colors? What is the performance of first-fit for $r = 2$ and $r = 3$?
