Timeline for Does this algorithm terminate in all scenarios?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 21, 2013 at 16:09 | history | edited | Andrés E. Caicedo | CC BY-SA 3.0 |
edited body
|
| Nov 21, 2013 at 12:10 | vote | accept | shna | ||
| Nov 21, 2013 at 9:51 | comment | added | shna | @MvG Ok, you are right for that version of the algorithm. What about the case where instead of identifying $ALL x_i \in A'$ (Step 1), I immediately move $x_i$ from A to B as soon as I detect that $d^{(A,k)}_{x_i}>d^{(B,k)}_{x_i}$ (and vice versa) ? that is we do not need A' and B', we directly move a point from A to B as soon as we detect it (and from B to A as soon as we detect it). Will we have the same problem ? I just tested that on your example and it terminates. | |
| Nov 21, 2013 at 8:53 | comment | added | MvG | @shna: I updated my answer to include a detailed step-by-step run. $A'=\{x_1\}$ because the distance(x2,x1) is higher than the distance(x2,x4). | |
| Nov 21, 2013 at 8:50 | history | edited | MvG | CC BY-SA 3.0 |
Step-by-step run
|
| Nov 20, 2013 at 22:39 | comment | added | shna | @MvG for you example, the algorithm that I provide terminates. Let the points: x1=(-2, 0), x2=(0,1), x3=(3,0), x4=(0,-1). At the first step A' = {} because distance(x1, x2) is not higher than distance(x1, x4), and distance(x2, x1) is not higher than distance(x2, x4), see step (1) of my Algorithm. So in step (2) A still the same. Similarly, in step (3) the B' = {x4} because x4 is closer to x1 than to x3, and x3 is not put in B' because distance(x3, x2) is not less than distance(x3, x4). Now at steps (5) and (6) we end up with A = {x1,x2,x4} and B={x3}. Algo stops now subce|B|=1$\leq$k | |
| Nov 20, 2013 at 22:37 | comment | added | Gerhard Paseman | The vector $x$ also does not appear in the algorithm, and looks to me as a placeholder to explain notation. Gerhard "Ask Me About System Design" Paseman, 2013.11.20 | |
| Nov 20, 2013 at 22:01 | comment | added | Gerry Myerson | The problem statement has starts with a vector $x$, which vector does not appear in your answer. | |
| Nov 20, 2013 at 21:57 | history | answered | MvG | CC BY-SA 3.0 |