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 $1\le$ optimal. Which is trivially true.
PS: I would highly appreciate hints only.
