On Bounded Integer Programming
| dc.creator | Khoát, Thân Quang | |
| dc.date | 2008-08-09 | |
| dc.date.accessioned | 2026-07-07T09:55:53Z | |
| dc.date.available | 2026-07-07T09:55:53Z | |
| dc.description | We present an efficient reduction from the Bounded integer programming (BIP) to the Subspace avoiding problem (SAP) in lattice theory. The reduction has some special properties with some interesting consequences. The first is the new upper time bound for BIP, $poly(φ)\cdot n^{n+o(n)}$ (where $n$ and $φ$ are the dimension and the input size of the problem, respectively). This is the best bound up to now for BIP. The second consequence is the proof that #SAP, for some norms, is #P-hard under semi-reductions. It follows that the counting version of the Generalized closest vector problem is also #P-hard under semi-reductions. Furthermore, we also show that under some reasonable assumptions, BIP is solvable in probabilistic time $2^{O(n)}$. | |
| dc.description | The preliminary version of this paper appeared in Proceedings of the 2008 IEEE International Conference on Research, Innovation & Vision for the Future - RIVF, July 2008, pages 23-28, Ho Chi Minh city, Vietnam, entitled "On the Bounded Integer Programming" | |
| dc.identifier | https://arxiv.org/abs/0808.1364 | |
| dc.identifier | http://arxiv.org/abs/0808.1364 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/166788 | |
| dc.subject | Computational Complexity | |
| dc.subject | Discrete Mathematics | |
| dc.subject | G.1.6; F.1.3; F.2; G.2.1 | |
| dc.title | On Bounded Integer Programming | |
| dc.type | text |