Timeline for Show that a $\alpha$-approximation algorithm is not a ($\alpha-x$) approximation algorithm for $x > $0
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 24, 2020 at 18:27 | comment | added | Yuval Filmus | Our goal is to provide an example where the algorithm performs badly. This example requires $\epsilon$ to be small. | |
| Apr 24, 2020 at 18:17 | comment | added | Yuval Filmus | We're interested in small $\epsilon$. This is the regime where this example works. | |
| Apr 24, 2020 at 18:16 | comment | added | nima3 | It's true when $\epsilon > 1$, why does $\epsilon$ need to be less than 1? | |
| Apr 24, 2020 at 18:12 | comment | added | Yuval Filmus | You wrote that $\epsilon/2 + 1/2$ is less than $\epsilon$, but that's actually false. | |
| Apr 24, 2020 at 13:53 | comment | added | nima3 | No, the machine that ends soonest is the one with the lowest load at the time before the job is inserted. | |
| Apr 24, 2020 at 13:51 | comment | added | Yuval Filmus | "When each job arrives, we put it on the machine that currently ends the soonest." Are you using a different algorithm, which puts the job on the machine that minimizes the makespan (after adding the new job)? | |
| Apr 24, 2020 at 13:50 | comment | added | nima3 | The makespan is $ 3/2 + e/2 $ not $ϵ/2+1/2$. For $e = \frac{1}{2}$, $k = 4$ and $x = 1$, is it still true that $(3/2 + 1/4) <= 3/2*3$ | |
| Apr 24, 2020 at 13:45 | comment | added | Yuval Filmus | I think of $\epsilon$ as a very small number. In particular, $\epsilon/2 + 1/2 \approx 1/2$ whereas $\epsilon \approx 0$, and so $\epsilon/2 + 1/2 > \epsilon$ for sufficiently small $\epsilon$ (in fact, any $\epsilon < 1$ would suffice). | |
| Apr 24, 2020 at 13:19 | comment | added | nima3 | This analysis is wrong since the greedy algorithm would put the fourth job on the fast machine since the fast machine after the third job is added ends at e/2 + 1/2, which is less than e (on the slow machine). And therefore the makespan would be: 3/2 + e/2 And it is true for any value of e > 0 that: (3/2 + e/2) <= (1 + e)(k-x). Therefore this cannot be used to prove the algorithm is not a (k-x)-approximation algorithm | |
| Apr 22, 2020 at 10:15 | comment | added | Yuval Filmus | Ok, I spelled it out. I imagine that the source of difficulty is that you don't understand the definition of an approximation algorithm. | |
| Apr 22, 2020 at 10:15 | history | edited | Yuval Filmus | CC BY-SA 4.0 |
added 602 characters in body
|
| Apr 22, 2020 at 10:08 | comment | added | Yuval Filmus | No. You will have to make this step on your own. You won't learn anything if we spoon-feed you. Don't be lazy! You can do it. | |
| Apr 22, 2020 at 10:05 | comment | added | Yuval Filmus | That's something you will have to figure out on your own. Try using the definition. | |
| Apr 22, 2020 at 10:04 | comment | added | nima3 | How does that show that the algorithm is not a (2- x)-approximation ?? | |
| Apr 22, 2020 at 8:08 | vote | accept | nima3 | ||
| Apr 22, 2020 at 10:01 | |||||
| Apr 21, 2020 at 20:45 | review | Low quality posts | |||
| Apr 22, 2020 at 6:07 | |||||
| Apr 21, 2020 at 19:37 | vote | accept | nima3 | ||
| Apr 21, 2020 at 20:42 | |||||
| Apr 21, 2020 at 19:32 | vote | accept | nima3 | ||
| Apr 21, 2020 at 19:34 | |||||
| Apr 21, 2020 at 19:05 | history | answered | Yuval Filmus | CC BY-SA 4.0 |