Branching proofs of infeasibility in low density subset sum problems

Gabor Pataki, Mustafa Tural

We prove that the subset sum problem has a polynomial time computable certificate of infeasibility for all $a$ weight vectors with density at most $1/(2n)$ and for almost all integ…