A physicist's approach to number partitioning
Available online 20 August 2001
Under an Elsevier user license
Open Archive
Keywords
- Number partitioning;
- Phase transition;
- NP-complete;
- Heuristic algorithms;
- Statistical mechanics;
- Random cost problem
References
-
On the computational complexity of Ising spin glass models
J. Phys. A, 15 (1982), p. 3241
-
Where the really hard problems are
J. Mylopoulos, R. Rediter (Eds.), Proc. of IJCAI-91, Morgan Kaufmann, San Mateo, CA (1991), pp. 331–337
-
Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, New York (1991)
-
Asymptotic Methods in Analysis, Wiley, New York (1961)
-
Random-energy model
Phys. Rev. Lett., 45 (1980), pp. 79–82
-
Random-energy model
Phys. Rev. E, 24 (5) (1981), pp. 2613–2626
-
Probabilistic analysis of the number partitioning problem
J. Phys. A, 31 (1998), pp. 3417–3428
-
The use and abuse of statistical mechanics in computational complexity
D.L. Stein (Ed.), Lectures in the Sciences of Complexity, Vol. 1, Addison-Wesley Publishing Company, Reading, MA (1989), pp. 815–826
-
The Asymptotic Theory of Extreme Order Statistics, Robert E. Krieger Publishing Co, Malabar, Fl (1987)
-
Computers and Intractability. A Guide to the Theory of NP-Completeness, W.H. Freeman, New York (1997)
-
I.P. Gent, T. Walsh, Phase transitions from real computational problems, Proc. of the 8th International Symposium on Artificial Intelligence, Monterrey, 1995. ITESM, pp. 356–364.
-
Phase transitions and annealed theories
W. Wahlster (Ed.), Proc. of ECAI-96, Wiley, New York (1996), pp. 170–174
-
Analysis of heuristics for number partitioning
Comput. Intell., 14 (3) (1998), pp. 430–451
-
W.D. Harvey, M.L. Ginsberg, Limited discrepancy search, in Proc. IJCAI-95, Montreal, Quebec, 1995, pp. 607–613.
-
Optimization by simulated annealing
Oper. Res., 39 (2) (1991), pp. 378–406
-
N. Karmarkar, R.M. Karp, The differencing method of set partitioning, Technical Report UCB/CSD 81/113, Computer Science Division, University of California, Berkeley, 1982.
-
Probabilistic analysis of optimum partitioning
J. Appl. Probab., 23 (1986), pp. 626–645
-
Optimization by simulated annealing
Science, 220 (4598) (1983), pp. 671–680
-
From approximate to optimal solutions
C.S. Mellish (Ed.), Proc. of IJCAI-95, Morgan Kaufmann, San Mateo, CA (1995), pp. 266–272
-
A complete anytime algorithm for number partitioning
Art. Intell., 106 (1998), pp. 181–203
-
Introduction to Fourier Analysis and Generalised Functions, Cambridge University Press, Cambridge (1959)
-
Exponentially small bounds on the expected optimum of the partition and subset sum problems
Random Struct. Algorithms, 12 (1998), pp. 51–62
-
Mathematical Methods of Physics, Addison-Wesley Publishing Company, Inc, Redwood City, CA (1970)
-
Phase transition in the number partitioning problem
Phys. Rev. Lett., 81 (20) (1998), pp. 4281–4284
-
S. Mertens, A complete anytime algorithm for balanced number partitioning, preprint xxx.lanl.gov/abs/cs.DS/9903011, 1999.
-
Random costs in combinatorial optimization
Phys. Rev. Lett., 84 (7) (2000), pp. 1347–1350
-
Spin Glass Theory and Beyond, World Scientific, Singapore (1987)
-
Determining computational complexity from characteristic ‘phase transitions’
Nature, 400 (1999), pp. 133–137
-
Ergodicity of the coupling constants and the symmetric n-replicas trick for a class of mean-field spin-glass models
Phys. Rev. Lett., 50 (8) (1983), pp. 598–600
-
H. Rieger, Frustrated systems: Ground state properties via combinatorial optimization, in: J. Kertesz, I. Kondor (Eds.), Advances in Computer Simulation, Vol. 501, Lecture Notes in Physics, Springer, Berlin, Heidelberg, New York, 1998.
-
Easily searched encodings for number partitioning
J. Opt. Theory Appl., 89 (2) (1996), pp. 251–291
-
Asymptotic analysis of an algorithm for balanced parallel processor scheduling
SIAM J. Comput., 21 (1) (1992), pp. 59–64
open in overlay
- http://itp.nat.uni-magdeburg.de/∼mertens
Copyright © 2001 Elsevier Science B.V. All rights reserved.