2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Start with an integer program for your problem.

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$.

$\endgroup$
2
  • $\begingroup$ I'll try that thanks. Is my partial reasoning of approximation factor of $3$ correct ? $\endgroup$ – sashas Nov 26 '20 at 22:30
  • 1
    $\begingroup$ If the argument is valid then the claim is correct. $\endgroup$ – Yuval Filmus Nov 26 '20 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.