Branching proofs of infeasibility in low density subset sum problems
| dc.creator | Pataki, Gabor | |
| dc.creator | Tural, Mustafa | |
| dc.date | 2008-07-31 | |
| dc.date.accessioned | 2026-07-07T09:55:33Z | |
| dc.date.available | 2026-07-07T09:55:33Z | |
| dc.description | 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 integer right hand sides. The certificate is branching on a hyperplane, i.e. by a methodology dual to the one explored by Lagarias and Odlyzko; Frieze; Furst and Kannan; and Coster et. al. The proof has two ingredients. We first prove that a vector that is near parallel to $a$ is a suitable branching direction, regardless of the density. Then we show that for a low density $a$ such a near parallel vector can be computed using diophantine approximation, via a methodology introduced by Frank and Tardos. We also show that there is a small number of long intervals whose disjoint union covers the integer right hand sides, for which the infeasibility is proven by branching on the above hyperplane. | |
| dc.identifier | https://arxiv.org/abs/0808.0023 | |
| dc.identifier | http://arxiv.org/abs/0808.0023 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/166665 | |
| dc.subject | Computational Complexity | |
| dc.subject | Cryptography and Security | |
| dc.subject | Combinatorics | |
| dc.subject | Optimization and Control | |
| dc.subject | F.2.2; G.2.1 | |
| dc.title | Branching proofs of infeasibility in low density subset sum problems | |
| dc.type | text |