• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Doctoral Thesis
DOI
https://doi.org/10.11606/T.76.2001.tde-05112008-131459
Document
Author
Full name
Fernando Fagundes Ferreira
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2001
Supervisor
Committee
Fontanari, Jose Fernando (President)
Koberle, Roland
Marchetti, Domingos Humberto Urbano
Oliveira, Paulo Murilo Castro de
Onody, Roberto Nicolau
Title in Portuguese
Análise estatística do problema da partição numérica.
Keywords in Portuguese
Complexidade computacional
Método de réplica
Modelo de Ising
Otimização
Problema de partição numérica
Abstract in Portuguese
Nesta tese apresentamos a abordagem da Mecânica Estatística para o clássico problema de otimização denominado problema da partição numérica (PPN), que é definido como: Dada uma seqüência de N números reais positivos {a1, a2, a3,....aN}, o problema consiste em particioná-los em dois conjuntos complementares, A e Ac, tais que o valor absoluto da diferença da soma dos ais nos dois conjuntos seja minimizada. No caso em que os aj's são variáveis aleatórias estatisticamente independentes distribuídas uniformemente no intervalo unitário, este problema NP-completo equivale ao problema de encontrar o estado fundamental de um modelo de Ising antiferromagnético aleatório de alcance infinito. Conseqüentemente, a análise probabilística do PPN pode ser realizada com as ferramentas da Mecânica Estatística de sistemas desordenados. Neste trabalho empregamos a aproximação recozida (annealed) para derivar uma expressão analítica para o limitante inferior do valor médio da diferença para partições tanto com vínculo de cardinalidade quanto sem vínculo para grandes valores de N. Além disso, calculamos analiticamente a fração de estados metaestáveis, isto é, estados que possuem a menor energia mediante todos os vizinhos (estados que diferem pela troca de um único spin). Concluímos a análise da abordagem direta, cujas instâncias {(ai) são fixas e as partições são variáveis, com o estudo analítico da versão relaxada deste problema de programação inteira NP-completo. Na segunda parte desta tese propomos e exploramos uma abordagem inversa para o PPN, no qual as partições ótimas são fixas e as instâncias são variáveis. Especificamente, usando o método das réplicas estudamos analiticamente o espaço de configuração do problema da partição numérica. Mostramos que, independentemente da distribuição de entradas das instâncias, existe um limitante superior αcN para o número de partições perfeitas aleatórias (isto é, partições com diferença igual a zero). Em particular, no caso em que os dois conjuntos têm a mesma cardinalidade (partições balanceadas) encontramos αc= 1/2. Mais ainda, no caso de partições não balanceadas, mostramos que as partições perfeitas aleatórias existem somente se a diferença entre as cardinalidades dos dois conjuntos escala com N-1/2}.
Title in English
Statistical analysis of the number partitioning problem.
Keywords in English
Computational complexity
Ising Model
Number partitioning problem
Optimization
Replica method
Abstract in English
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}.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
FernandoFerreiraD.pdf (4.76 Mbytes)
Publishing Date
2008-11-06
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2024. All rights reserved.