Timeline for Greedy approach to 0-1 Knapsack problem in specific instances
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 5, 2011 at 16:48 | vote | accept | BharatRam | ||
| Jun 3, 2011 at 12:07 | comment | added | BharatRam | Also, the greedy algorithm's performance here seems near optimal here, as the difference between its solution and the optimal is just the difference in its performance in the much smaller counterexample we started out with. Can this be quantified? | |
| Jun 3, 2011 at 11:57 | comment | added | BharatRam | Your counterexample seems correct. So is there any characterization or property of knapsack instances which makes the simple greedy approach optimal in their cases? | |
| Jun 2, 2011 at 14:30 | history | answered | Federico Poloni | CC BY-SA 3.0 |