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}$.
Posted: Jun 17 '12
Seen: 28 times
Last updated: Jun 17 '12
