Timeline for How to maximize the number of variables with value at least 0?
Current License: CC BY-SA 4.0
11 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Apr 4 at 20:46 | vote | accept | Erel Segal-Halevi | ||
Apr 4 at 20:46 | history | bounty ended | Erel Segal-Halevi | ||
Apr 4 at 20:36 | history | edited | RobPratt | CC BY-SA 4.0 |
edited body
|
Apr 4 at 20:36 | comment | added | RobPratt | Yes, that is the usual relationship between an optimization problem and a decision problem. | |
Apr 4 at 19:36 | comment | added | Erel Segal-Halevi | Thanks! In the reduction, can you consider only the simpler program with 3 constraints xi+xj≤−1 and −xi≤1 and xi≤0, and argue that maximizing the number of nonnegative variables is equivalent to maximizing the number of variables with value 0, which is equivalent to maximizing the size of the independent set? | |
Apr 3 at 1:01 | history | edited | RobPratt | CC BY-SA 4.0 |
added 813 characters in body
|
Mar 30 at 20:19 | comment | added | RobPratt | I suspect that there is no polynomial-time algorithm, but the formulation I suggested should in practice perform much better than brute force. | |
Mar 30 at 19:34 | comment | added | Erel Segal-Halevi | Since the new variables yi are binary, solving the new program requires, in the worst case, to check all 2n possible combinations of their values, which is similar to the solution I described (checking all 2n possible subsets of variables xi). Is there a polynomial-time solution? | |
Mar 29 at 14:00 | comment | added | Kuifje | I believe it should be mentioned that this cannot be solved in polynomial time (since OP asked). | |
Mar 29 at 13:07 | history | edited | RobPratt | CC BY-SA 4.0 |
added 65 characters in body
|
Mar 29 at 12:26 | history | answered | RobPratt | CC BY-SA 4.0 |