Timeline for Is a problem that is NP-hard to solve under known future still NP-hard to solve under random future? [closed]
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 29, 2017 at 12:39 | comment | added | fishermanymc | @DirkLiebhold thanks for your prompt reply! It is inspiring that such reduction is not hard. But embarrassingly, I am new to combinatorial optimization. I don't know how to reduce a deterministic problem to a random one. It is highly appreciated if you could recommend something I can read and learn about this technique. | |
| Sep 29, 2017 at 12:38 | review | Reopen votes | |||
| Sep 29, 2017 at 19:09 | |||||
| Sep 29, 2017 at 12:29 | history | edited | fishermanymc | CC BY-SA 3.0 |
added 1 character in body
|
| Sep 29, 2017 at 12:25 | comment | added | Dirk | Then proof that it is NP by giving a reduction from the zero loss case to the nonzero one. It is really basic, but if they want to see it...^^ | |
| Sep 29, 2017 at 12:25 | comment | added | fishermanymc | @zen It is interesting to know a new problem that my problem could potentially be reduced to. Thanks! But in my existing work I reduce my problem to a hypergraph strong coloring problem. Please kindly refer to my updated problem - clarified and concrete. | |
| Sep 29, 2017 at 12:23 | comment | added | fishermanymc | @DirkLiebhold I totally agree with you. But my reviewers were not happy. They explicitly ask what is the hardness if there are nonzero losses. | |
| Sep 29, 2017 at 12:22 | comment | added | fishermanymc | @RobinHouston thanks a lot for your attention and kindness to a newbie. Please kindly refer to my clarified and concrete problem. | |
| Sep 29, 2017 at 12:18 | history | edited | fishermanymc | CC BY-SA 3.0 |
Provided a more detailed and concrete problem formulation.
|
| Sep 28, 2017 at 13:50 | history | closed |
Gro-Tsen coudy Stefan Kohl♦ Neil Strickland Mikhail Katz |
Needs details or clarity | |
| Sep 28, 2017 at 13:30 | comment | added | zen | The original problem sounds like the multiple knapsack problem. Can you confirm this is the case? If that is the case can we assume we miss knapsacks (and all items in them) randomly? | |
| Sep 28, 2017 at 8:28 | comment | added | Dirk | Doesn't your second case contain the first one, i.e. it is possible that exactly $0$ packets get lost? In this case, an efficient algorithm for the second case should also work when nothing is lost, thus in the NP-hard case... | |
| Sep 28, 2017 at 8:20 | comment | added | Robin Houston | (Sorry for the bizarre autocorrecto in my comment above, which I can no longer edit.) | |
| Sep 28, 2017 at 7:52 | comment | added | Robin Houston | Can you specify the problem? Your question seems impossible to answer without knowing more about the prso ken you’re considering. | |
| Sep 28, 2017 at 7:28 | review | Close votes | |||
| Sep 28, 2017 at 13:50 | |||||
| Sep 28, 2017 at 7:02 | review | First posts | |||
| Sep 28, 2017 at 7:17 | |||||
| Sep 28, 2017 at 6:59 | history | asked | fishermanymc | CC BY-SA 3.0 |