Thèse de Doctorat
DOI
https://doi.org/10.11606/T.76.2001.tde-05112008-131459
Document
Auteur
Nom complet
Fernando Fagundes Ferreira
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Carlos, 2001
Directeur
Jury
Fontanari, Jose Fernando (Président)
Koberle, Roland
Marchetti, Domingos Humberto Urbano
Oliveira, Paulo Murilo Castro de
Onody, Roberto Nicolau
Titre en portugais
Análise estatística do problema da partição numérica.
Mots-clés en portugais
Método de réplica
Modelo de Ising
Otimização
Problema de partição numérica
Resumé en portugais
Titre en anglais
Statistical analysis of the number partitioning problem.
Mots-clés en anglais
Computational complexity
Ising Model
Number partitioning problem
Optimization
Replica method
Resumé en anglais
In this thesis we present a statistical mechanics approach to a classical optimization problem called the number partitioning problem (NPP), which is stated as follows. Given a sequence of N positive real numbers {a1, a2, a3,....aN}, the number partitioning problem consists of partitioning them into two sets A and its complementary set Ac such that the absolute value of the difference of the sums of aj over the two sets is minimized. In each case in which the aj's are statistically independent random variables uniformly distributed in the unit interval, this NP-complete problem is equivalent to the problem of finding the ground state of an infinite range, random antiferromagnetic Ising model. Hence the probabilistic analysis of the NPP can be carried out within the framework of the standard statistical mechanics of disordered systems. In this vein we employ the annealed approximation to derive analytical lower bounds to the average value of the difference for the best-constrained and unconstrained partitions in the large N limit. Furthermore, we calculate analytically the fraction of metastable states, i.e. states that are stable against all single spin flips. We conclude the analysis of the so-called direct approach, in which the instances {ai} are fixed and the partitions are variable, with the analytical study of the linear programming relaxation of this NP-complete integer programming. In the second part of this thesis we propose and explore an inverse approach to the NPP, in which the optimal partitions are fixed and the instances are variable. Specifically, using the replica framework we study analytically the instance space of the number partitioning problem. We show that, regardless of the distribution of the instance entries, there is an upper bound αcN 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 =1/2. 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 m N-1/2}.

AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.