Skip to main content
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+xj1 and xi1 and xi0, 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