**Question**

There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 le i le m$) has to be sent from computer $s_i$ to computer $t_i$. There are two ways to deliver a message $i$: clockwise from $s_i$ to $t_i$ or anti-clockwise from $s_i$ to $t_i$. Aim is to send all messages in such a way that the number of messages going through the most frequently used edge is minimized. We need to devise a $2$-Approximation algorithm for the same.

**Example**

Let $n=4$. Let $m=2$. And let $s_1=1,t_1=4$ and $s_2=2,t_2=3$. Then if we send message $1$ in the following way: $1 to 2 to 3 to 4$ and message $2$ as: $2 to 3$. The most frequently edge used is $2 to 3$, through which $2$ messages go. We can do better than this.

Message $1$: $1 to 4$ and delivery of message $2$ remains same $2 to 3$. Then both the edges are most frequently used. But only $1$ message goes through most frequently used edges.

**My approach 1**

For every message with probability $frac{1}{2}$ send it in clockwise direction and with $frac{1}{2}$ in anti-clockwise direction.

But this gives a bad performance, which can be seen with the help of the following example:

$n=10000$, $m=200$ and $s_i = i,t_i=i+1$ for $1 le i le 200$. Then the optimal answer is $1$ (ie. every edge has at most $1$ message going through it). Which can be achieved by sending message $i$ as $i to (i+1)$.

Also this is the only way to achieve the optimal. If anyone of the messages were sent in the other direction the answer increases. For eg. if $x$ of the $200$ messages were sent in other direction, all these $x$ would use say edge $800 to 801$. So the answer would be at least $x$. Thus in this case the random solution picks the optimal arrangement with only probability $frac{1}{2^{200}}$, which is very less and for other arrangements answer gets bigger.

**My approach 2**

I turned towards greedy. Where for message $i$ we send it in the direction where it will travel through lesser number of edges, ie. we send it along the shorter route. Then I argued as below

(I consider $n$ odd for now, and also don’t consider some other corner cases)

For an arbitrary input $n$, $m$ (and the respective source and sinks) let the optimal be $p$ (that is $p$ is the number of messages going through the most frequent used edge), then the optimal arrangement cannot have more than $2p$ messages for which longer routes were chosen. **Reason**: longer routes have at least $frac{n+1}{2}$ contiguous edges, for example for $n=7$, if I list all thecontiguous subsets of size $frac{n+1}{2}$ (the possibilities of longer route)

$$

1,2,3,4 \

3,4,5,6 \

4,5,6,7 \

6,7,1,2 \

7,1,2,3 \

$$

and lets say $p=1$. Then as first two subsets (nearly the half) have a common element $4$, and so do the last three subsets (again nearly the half) have common element $7$ (this is true for arbitrary odd $n$).

There can be a case where (in the optimal arrangement) $p$ of the longer routes lie in first half of subsets and another $p$ of longer routes in the second half of subsets. But if more than $2p$ are there. There would be at least $p+1$ in a single half of subsets, making the answer $p+1$ which is a contradiction.

And as changing direction of a message can at worst increase the answer by $1$. The greedy should have answer $le 3p$ (change all $2p$ longer routes to short, to get to what greedy outputs).

But I seem to be stuck beyond this. As this gives approximation factor of $3$ (I did not consider $n$ is even case, as I think if odd case is handled it will be just about the corner case of source and sink being at exactly $frac{n}{2}$ distance).

Maybe in my reasoning I overestimated somewhere.

I had also tried tried to obtain bounds using weak duality by expressing problem as LP relaxation. Assuming my working was correct what I could get is $1le$ optimal. Which is trivially true.

PS: I would highly appreciate hints only.