|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'503'724
Articles rated: 2609
23 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Proof of the local REM conjecture for number partitioning I: Constant energy scales | | Christian Borgs
; Jennifer Chayes
; Stephan Mertens
; Chandra Nair
; | | Date: |
31 Dec 2004 | | Subject: | Disordered Systems and Neural Networks; Statistical Mechanics; Mathematical Physics; Probability | cond-mat.dis-nn cond-mat.stat-mech math-ph math.MP math.PR | | Abstract: | The number partitioning problem is a classic problem of combinatorial optimization in which a set of $n$ numbers is partitioned into two subsets such that the sum of the numbers in one subset is as close as possible to the sum of the numbers in the other set. When the $n$ numbers are i.i.d. variables drawn from some distribution, the partitioning problem turns out to be equivalent to a mean-field antiferromagnetic Ising spin glass. In the spin glass representation, it is natural to define energies -- corresponding to the costs of the partitions, and overlaps -- corresponding to the correlations between partitions. Although the energy levels of this model are {em a priori} highly correlated, a surprising recent conjecture asserts that the energy spectrum of number partitioning is locally that of a random energy model (REM): the spacings between nearby energy levels are uncorrelated. In other words, the properly scaled energies converge to a Poisson process. The conjecture also asserts that the corresponding spin configurations are uncorrelated, indicating vanishing overlaps in the spin glass representation. In this paper, we prove these two claims, collectively known as the local REM conjecture. | | Source: | arXiv, cond-mat/0501760 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER