<p>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 <a href="http://dl.acm.org/citation.cfm?id=1273343" rel="nofollow">http://dl.acm.org/citation.cfm?id=1273343</a> 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 <a href="http://arxiv.org/abs/1102.3643" rel="nofollow">http://arxiv.org/abs/1102.3643</a>. 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 <a href="http://sites.google.com/site/chalermsook/academic/coloring_full.pdf?attredirects=0" rel="nofollow">http://sites.google.com/site/chalermsook/academic/coloring_full.pdf?attredirects=0</a>. However it may require figuring out several technical details. One suspects that there is a constant factor approximation for the coloring problem.</p>

CC BY-SA 3.0
2012-06-03T14:18:47.977Z
2012-06-03T14:18:47.977Z
Chandra Chekuri
<p>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 <strong>Interval Coloring with Capacities and Demands</strong>. 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)$.</p>

<p>What is the best approximation algorithm and hardness result known for this problem?</p>

<ds.algorithms><approximation-algorithms><optimization><approximation-hardness><graph-colouring>
Algorithms for Interval Coloring with Capacities and Demands
Arindam Pal
# Algorithms for Interval Coloring with Capacities and Demands

(Asked by: username_0 on 2012-06-03)

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?

**Tags:** ds.algorithms, approximation-algorithms, optimization, approximation-hardness, graph-colouring

---

## 1 answers

### Answer by username_1 on 2012-06-03. Score: 4 | Accepted answer

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.


---

