3
$\begingroup$

Given a sequence of positive reals $a_1, a_2, \dots, a_n$ and an integer $m$, for each $j$ assign $a_j$ to a machine $i$, $1< i < m$, so as to minimize the maximum, over $i$, of the sum of all reals assigned to machine $i$.

Theorem: There is no randomized $m$-machine scheduling algorithm with a competitive ratio less than $4/3$ for any $m \geq 2$.

The following is the Proof Sketch given in the paper:

Consider the job sequences $m \times 1$ and $m \times 1, 2$. (Here $m \times 1$ denotes a sequence of $m$ 1’s.) If the algorithm schedules the $m$ 1‘s on $m$ different machines with probability $p$, the worst-case ratio between its cost and the optimal cost is at least $\max\{2 – p, 1 + p/2\} \sim 4/3$.

I have problem understanding the proof. I would really appreciate if anyone can explain the proof in details, especially how to arrive at the worst-case ratio of $\max\{2-p, 1+p/2\}$.

$\endgroup$
  • 1
    $\begingroup$ It's not a proof – it's just a proof sketch. You have to fill in the details. $\endgroup$ – Yuval Filmus Jul 13 '17 at 5:13
2
$\begingroup$

Consider first the sequence $m \times 1$. If the algorithm schedules all the 1's in different machines, then its competitive ratio is 1. Otherwise, its competitive ratio is at least 2 (since the maximum is at least 2 instead of the optimum 1). This case gives an average competitive ratio of at least $p \cdot 1 + (1-p) \cdot 2 = 2-p$.

Consider next the sequence $m \times 1, 2$. If the algorithm schedules all the 1's in different machines, then its competitive ratio is 3/2, since the maximum is 3 while the optimum is 2. If it doesn't schedule the 1's in different machines, we use the trivial bound on the competitive ratio. This case gives an average competitive ratio of at least $p \cdot (3/2) + (1-p) \cdot 1 = 1 + p/2$.

We conclude that the competitive ratio is at least $\max(2-p,1+p/2)$. If $p \leq 2/3$ then $2-p \geq 4/3$, whereas if $p \geq 2/3$ then $1+p/2 \geq 4/3$, and so whatever the value of $p$, we get that the competitive ratio must be at least $4/3$.

$\endgroup$

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.