Algorithms for Interval Coloring with Capacities and Demands

Question

We are given a graph $G = (V,E)$, 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 source and $t_i$ is the destination 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} 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. This problem is called Interval Coloring with Capacities and Demands. This is because 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. This can also be thought of as routing the requests in a feasible manner in a number of rounds. We consider the special case where $G$ is a path $(v_1,e_1,v_2,e_2,\ldots,e_{n-1},v_n)$.

What is the best approximation algorithm and hardness result known for this problem?

Answer 1

If the demands satisfy the no-bottleneck assumption, that is $\max_i d_i \leq \min_e c(e)$ then a constant factor approximation is known even for trees. See http://dl.acm.org/citation.cfm?id=1273343 which gives a 48-approx for trees. For paths a better bound can be obtained and may have been shown but I am not sure where or whether it was published. For the general case it is not quite clear what the best known result is. One can get an easy $O(\log n)$-approximation as follows. Consider the problem of maximizing the number of requests that can be feasibly routed; there is a constant factor approximation for this problem, see http://arxiv.org/abs/1102.3643. Using this as a black box one can do a greedy set-cover like algorithm to repeatedly pack as many requests as possible to get the desired $O(\log n)$-approximation. A paper by Chalermsook on coloring rectangles may have some implications including giving an $O(\log \log n)$-approximation; the paper is available at http://sites.google.com/site/chalermsook/academic/coloring_full.pdf?attredirects=0. However it may require figuring out several technical details. One suspects that there is a constant factor approximation for the coloring problem.