Timeline for Verifying if a greedy solution is optimal for a specific instance (Set cover)
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 22, 2017 at 9:58 | answer | added | Yuval Filmus | timeline score: 1 | |
| S Sep 22, 2017 at 9:13 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
Precising that I mean efficiently
|
| S Sep 22, 2017 at 9:13 | history | suggested | yawn | CC BY-SA 3.0 |
Precising that I mean efficiently
|
| Sep 22, 2017 at 3:57 | review | Suggested edits | |||
| S Sep 22, 2017 at 9:13 | |||||
| Sep 19, 2017 at 16:41 | comment | added | D.W.♦ | I guess you want an efficient way? Sounds like something that might be co-NP-hard. | |
| Sep 18, 2017 at 22:48 | comment | added | Raphael | Of course there is: use a verified solver. | |
| Sep 18, 2017 at 22:48 | history | edited | Raphael |
edited tags; edited tags
|
|
| Sep 18, 2017 at 20:41 | comment | added | Yuval Filmus | It's rather unlikely. It would be a nice challenge to show that such an efficient method can be used to solve or at least approximate set cover. | |
| Sep 18, 2017 at 20:38 | review | First posts | |||
| Sep 19, 2017 at 1:41 | |||||
| Sep 18, 2017 at 20:37 | history | asked | Yawn | CC BY-SA 3.0 |