Timeline for Discrete optimization problem
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 27, 2015 at 5:52 | comment | added | Manfred Weis | @WillBrian nice counterexample! I suspect that there is no efficient solution to the problem because of its relation to clique problems. | |
| Jun 26, 2015 at 16:15 | comment | added | Will Brian | It is not always optimal. Consider the case of trying to choose 3 points from the vertices of a regular hexagon. This algorithm will first remove one point A (any one, by symmetry) and then the point opposite A. It will then remove a third point (again, by symmetry it doesn't matter which) to leave a right triangle. But it's easy to compute that a better solution is the equilateral triangle formed by three mutual non-neighbors. | |
| Jun 26, 2015 at 16:07 | comment | added | Kimball | Can you prove the greedy algorithm is optimal here? I don't see why this should be the case. | |
| Jun 26, 2015 at 15:47 | history | answered | Manfred Weis | CC BY-SA 3.0 |