3
votes
Accepted
minimum number of 2d elements whose sums across both dimensions satisfy some threshold
Your problem is NP-hard, by reduction from the equal-cardinality partition problem.
Let $a_1,\dots,a_n$ be an instance of the equal-cardinality partition problem (so $n$ is even). The reduction works ...
D.W.♦
- 154k
2
votes
Accepted
Can the optimization version of a problem be NP-hard while its decision version is in P?
Lastly, I did not use the set $𝐶$
in my decision question. Therefore I am not 100% certain that it is the 'correct' formulation.
It is not correct, indeed :)
You are describing a decision problem, ...
- 136
2
votes
Can the optimization version of a problem be NP-hard while its decision version is in P?
Often, if the decision problem can be solved in polynomial time, the optimization problem can be solved in polynomial time as well. For example, if you could decide in polynomial time if a problem has ...
- 211
1
vote
Which algorithms could be suitable for solving my disjunctive programming problem?
The prior answer already explained a standard way to solve this kind of problem: introduce boolean (0-or-1) variables to model the disjunction, and then solve with an off-the-shelf integer linear ...
D.W.♦
- 154k
1
vote
Accepted
Integrality gap and complexity classes
The question is incorrect. The integrality gap is defined for a linear programming formulation of the problem and not fundamentally for the problem.
It is possible that a problem has more than one ...
- 5,276
1
vote
Boolean constraints for a connected component of a graph
Here is one encoding. Introduce boolean variables $x_{v,i}$, with the intended meaning that $x_{v,i}$ is true if $v$ is selected and $v$ can by reached by a path of length $\le i$ from $s$ (where $s$ ...
D.W.♦
- 154k
1
vote
Accepted
Possible to solve a combinatorial game with integer programming?
I believe you can't, for many/most combinatorial games. In particular, I believe optimal play for two-player combinatorial games is often a PSPACE-complete problem (sometimes a EXP-complete problem), ...
D.W.♦
- 154k
Only top scored, non community-wiki answers of a minimum length are eligible