# 2-Approximation algorithm for for messages across a cyclic network

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.

For each $$i$$, there is a variable $$x_i \in \{0,1\}$$ which represents which way the $$i$$'th message is routed. You can express the number of messages going through an edge $$e$$ as some linear combination $$y_e$$ of the $$x_i$$'s. Your goal is to minimize $$\max(y_e)$$. Equivalently, you want to minimize $$m$$ under the constraints $$m \geq y_e$$.
Now consider the LP relaxation. Determine which way to route the $$i$$'th message by rounding $$x_i$$.
• I'll try that thanks. Is my partial reasoning of approximation factor of $3$ correct ? – sashas Nov 26 '20 at 22:30