| - | ||||
|
|
Lattice-based Algorithms for Number Partitioning in the Hard Phase
Bala Krishnamoorthy (bkrishna Abstract: The number partitioning problem (NPP) is to divide $n$ numbers $a_1, \dots, a_n$ into two disjoint subsets such that the difference between the two subset sums -- the {\em discrepancy}, $\triangle$, is minimized. In the balanced version of NPP ({\sc BalNPP}), the subsets have the same cardinality. With $a_j$s chosen randomly from $[1,R]$, $R > 2^n$ gives the {\em hard} phase, when there are no equal partitions, and the minimum partition is unique, with high probability. We propose reductions of NPP and {\sc BalNPP} in the hard phase to instances of the closest vector problem (CVP). We can solve the original problems by making polynomial numbers of calls to a CVP oracle. In practice, we apply basis reduction (BR) to several CVP instances ($O(n)$ in general, $4n$ in most cases) to solve NPP problems with reasonably large dimensions. Second, we propose a direct mixed integer programming (MIP) model for NPP and {\sc BalNPP}. We then solve a lattice-based reformulation of the original MIP using branch-and-cut methods. Assuming it terminates, the MIP model is guaranteed to find the optimum partition. Third, we propose a {\em truncated} NPP algorithm, which finds approximate minimum discrepancies for instances well into the hard phase. In place of the original instance, we solve a modified instance with $\bar{a}_j = \lfloor a_j / T \rceil$ for some $T \leq R$. We show that the discrepancy of the original problem given by the truncated solution, $\triangle_T$, is not much different from the expected optimal discrepancy: $\triangle_T \leq \triangle^* + nT/2$. Keywords: Number partitioning, closest vector problem, basis reduction, integer programming Category 1: Combinatorial Optimization (Other ) Category 2: Integer Programming (Other ) Category 3: Combinatorial Optimization (Approximation Algorithms ) Citation: Download: [PDF] Entry Submitted: 10/15/2008 Modify/Update this entry | ||
| Visitors | Authors | More about us | Links | |
|
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
|
||||