Lattice-based Algorithms for Number Partitioning in the Hard Phase

The number partitioning problem (NPP) is to divide n numbers a_1,…,a_n into two disjoint subsets such that the difference between the two subset sums – the discrepancy, D, is minimized. In the balanced version of NPP (BalNPP), the subsets must have the same cardinality. With $a_j$s chosen uniformly from $[1,R]$, R > 2^n gives the … Read more

Column basis reduction and decomposable knapsack problems

We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem b’   ≤   Ax   ≤   b,   x ∈ Zn with b’   ≤   (AU)y   ≤   b,   y ∈ Zn, where U is a unimodular matrix computed via basis reduction, to make the … Read more