Timeline for A combinatorial matrix reconstruction problem II
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 31, 2022 at 16:22 | comment | added | Arnold Neumaier | I'd be quite interested in a proof on NP-completeness. | |
| Aug 31, 2022 at 15:39 | comment | added | Max Alekseyev | @ArnoldNeumaier: On the contrary, I think your problem is quite likely NP-complete. I gave a link to a simpler problem, which is proved to be NP-complete. Perhaps, that one can be reduced to yours but I did not check. As for ILP, it's often can be solved quite fast in practice for moderate instances with state-of-art solvers like Gurobi or CPLEX. | |
| Aug 31, 2022 at 15:26 | comment | added | Arnold Neumaier | Since ILP is NP-hard, this approach would be appropriate if the problem can be shown to be NP-hard. But this is unlikely; the problem should be easier, perhaps of the complexity class of graph isomorphism. Your approach also needs graph isomorphism for postprocessing since if there are multiple solutions of your ILP one still needs to check whether they are permutation equivalent. | |
| Aug 30, 2022 at 19:42 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
typo corrected
|
| Aug 30, 2022 at 19:26 | comment | added | RobPratt | To explicitly disallow a given binary solution, you can use a no-good cut, as in my answer here. | |
| Aug 30, 2022 at 15:42 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
added 89 characters in body
|
| Aug 30, 2022 at 13:25 | history | answered | Max Alekseyev | CC BY-SA 4.0 |