1999/10/31 by Fábio Furlan Ferreira, F. F. Ferreira, José F. Fontanari +1
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Cardinality (data modeling) #Combinatorics #Computer science #Constraint Satisfaction and Optimization #Discrete mathematics #Distribution (mathematics) #Integer (computer science) #Integer programming #Limits and Structures in Graph Theory #Machine Learning and Algorithms #Mathematics #Replica #Sequence (biology) #Space (punctuation) #Upper and lower bounds #cond-mat
paper · pdf · doi:10.1088/0305-4470/33/41/301
7 pages
arxiv created 1999/11/01 · openalex publication_date 2000/10/05 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Within the replica framework we study analytically the instance space of the number partitioning problem. This classic integer programming problem consists of partitioning a sequence of N positive real numbers a 1 , a 2 ,..., a N (the instance) into two sets such that the absolute value of the difference of the sums of a j over the two sets is minimized. We show that, regardless of the distribution of the instance entries, there is an upper bound α c N to the number of perfect random partitions (i.e. partitions for which that difference is zero). In particular, in the case where the two sets have the same cardinality (balanced partitions) we find α c = ½. Moreover, in the case of unbalanced partitions, we show that perfect random partitions exist only if the difference between the cardinalities of the two sets scales like mN 1/2 , where m is of the order of 1.