## Related books

Suggest a Book

Level: unknown

posted Jun 17 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

Consider a telephone network that consists of a cycle on $n$ nodes, numbered $0$ through $n-1$ clockwise around the cycle. Let $S$ be a set of calls. Each call is a pair $(i,j)$ originating at node $i$ and ending at node $j$. The call can be routed either clockwise or counterclockwise around the cycle. The objective is to route the calls so as to minimize the total "load" on the network. The load $L_i$ on the link $(i, i+1(\mbox{mod}\ n))$ is the number of calls routed through the link. The total load is $\max_{1 \leq i \leq n}{L_i}$.

• Design a 2-approximation algorithm algorithm for the above problem.
delete retag edit

## Stats

Posted: Jun 17 '12

Seen: 28 times

Last updated: Jun 17 '12