  


Latticebased Algorithms for Number Partitioning in the Hard Phase
Bala Krishnamoorthy (bkrishnamath.wsu.edu) Abstract:
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 hard phase, when there are no equal partitions (i.e., D=0) with high probability (whp). In this phase, the minimum partition is also unique whp. Most current methods struggle in the hard phase, as they often perform exhaustive enumeration of all partitions to find the optimum. 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  