Timeline for Greedy algorithm correctness proof for "Elegant Permuted Sum" (UVa 11158)
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 24, 2015 at 6:40 | vote | accept | matheuscscp | ||
| Jun 24, 2015 at 5:18 | answer | added | Yuval Filmus | timeline score: 2 | |
| Jun 24, 2015 at 3:45 | history | tweeted | twitter.com/#!/StackCompSci/status/613553562887581697 | ||
| Jun 24, 2015 at 3:08 | comment | added | hengxin | related post at cs.theory | |
| Jun 24, 2015 at 2:44 | comment | added | Yuval Filmus | @matheuscscp No, by $b$ I don't mean an optimal solution. By $b$ I mean the value of $a$ from the previous iteration. If we denote the value of $a$ at iteration $t$ by $a_t$, and the current iteration is $t$, then in my comment, $a = a_t$ while $b = a_{t-1}$. | |
| Jun 24, 2015 at 2:18 | comment | added | matheuscscp | @D.W. Yes, but no progress :( | |
| Jun 24, 2015 at 2:17 | comment | added | matheuscscp | @YuvalFilmus Thanks for helping! But, by $a$, you mean the partial solution of the algorithm, right? And $b$ is just any optimal solution. In this case, I don't get what you mean by "there is some optimal solution extending $b$, which is the value of $a$ from the last round". Actually, I don't understand any relation between $a$ and $b$, because $b$ is not necessarily the final result of $a$ (the partial solution), it's just any hypothetical optimal solution to the problem. Can you try again? Thanks! | |
| Jun 24, 2015 at 2:17 | comment | added | D.W.♦ | Have you tried working through some small examples? Often that helps you understand what's going on and helps you formulate a proof strategy. | |
| Jun 24, 2015 at 1:33 | comment | added | Yuval Filmus | How do you do this? By induction, there is some optimal solution extending $b$, which is the value of $a$ from the last round. Now you take any solution extending $b$, and show how to modify it so that it extends $a$ while not decreasing the objective function. That is the crux of the proof. | |
| Jun 24, 2015 at 1:32 | comment | added | Yuval Filmus | It is not necessarily the case that only adding $s'_1$ or $s'_k$ yields an optimal solution. Rather, there is always some choice of that type which yields an optimal solution. In order to prove the correctness of the algorithm, you prove by induction that at any point, there is an optimal solution extending $a$. | |
| Jun 24, 2015 at 1:18 | history | edited | matheuscscp | CC BY-SA 3.0 |
added 30 characters in body
|
| Jun 24, 2015 at 0:44 | history | asked | matheuscscp | CC BY-SA 3.0 |