Theoretical Computer Science

Volume 265, Issues 1–2, 28 August 2001, Pages 79-108

Phase Transitions in Combinatorial Problems

A physicist's approach to number partitioning

Available online 20 August 2001

doi:10.1016/S0304-3975(01)00153-0

Get rights and content

Under an Elsevier user license


Open Archive

References

  • [1] 

    F. Barahona

    On the computational complexity of Ising spin glass models

    J. Phys. A, 15 (1982), p. 3241

  • [2] 

    P. Cheeseman, B. Kanefsky, W.M. Taylor

    Where the really hard problems are

    J. Mylopoulos, R. Rediter (Eds.), Proc. of IJCAI-91, Morgan Kaufmann, San Mateo, CA (1991), pp. 331–337

  • [3] 

    E.G. Coffman, G.S. Lueker

    Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, New York (1991)

  • [4] 

    N.G. De Bruijn

    Asymptotic Methods in Analysis, Wiley, New York (1961)

  • [5] 

    B. Derrida

    Random-energy model

    Phys. Rev. Lett., 45 (1980), pp. 79–82

  • [6] 

    B. Derrida

    Random-energy model

    Phys. Rev. E, 24 (5) (1981), pp. 2613–2626

  • [7] 

    F.F. Ferreira, J.F. Fontanari

    Probabilistic analysis of the number partitioning problem

    J. Phys. A, 31 (1998), pp. 3417–3428

  • [8] 

    Y. Fu

    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

  • [9] 

    J. Galambos

    The Asymptotic Theory of Extreme Order Statistics, Robert E. Krieger Publishing Co, Malabar, Fl (1987)

  • [10] 

    M.R. Garey, D.S. Johnson

    Computers and Intractability. A Guide to the Theory of NP-Completeness, W.H. Freeman, New York (1997)

  • [11] 

    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.

  • [12] 

    I.P. Gent, T. Walsh

    Phase transitions and annealed theories

    W. Wahlster (Ed.), Proc. of ECAI-96, Wiley, New York (1996), pp. 170–174

  • [13] 

    I.P. Gent, T. Walsh

    Analysis of heuristics for number partitioning

    Comput. Intell., 14 (3) (1998), pp. 430–451

  • [14] 

    D.J. Gross, M. Mézard

    The simplest spin glass

    Nucl. Phys. B, 240 (1984), pp. 431–452

    Article PDF (938K)

  • [15] 

    W.D. Harvey, M.L. Ginsberg, Limited discrepancy search, in Proc. IJCAI-95, Montreal, Quebec, 1995, pp. 607–613.

  • [16] 

    D.S. Johnson, C.R. Aragon, L.A. McGeoch, C. Schevron

    Optimization by simulated annealing

    Oper. Res., 39 (2) (1991), pp. 378–406

  • [17] 

    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.

  • [18] 

    N. Karmarkar, R.M. Karp, G.S. Lueker, A.M. Odlyzko

    Probabilistic analysis of optimum partitioning

    J. Appl. Probab., 23 (1986), pp. 626–645

  • [19] 

    S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi

    Optimization by simulated annealing

    Science, 220 (4598) (1983), pp. 671–680

  • [20] 

    R.E. Korf

    From approximate to optimal solutions

    C.S. Mellish (Ed.), Proc. of IJCAI-95, Morgan Kaufmann, San Mateo, CA (1995), pp. 266–272

  • [21] 

    R.E. Korf

    A complete anytime algorithm for number partitioning

    Art. Intell., 106 (1998), pp. 181–203

    Article PDF (1756K)

  • [22] 

    M.J. Lighthill

    Introduction to Fourier Analysis and Generalised Functions, Cambridge University Press, Cambridge (1959)

  • [23] 

    G.S. Lueker

    Exponentially small bounds on the expected optimum of the partition and subset sum problems

    Random Struct. Algorithms, 12 (1998), pp. 51–62

  • [24] 

    J. Mathews, R.L. Walker

    Mathematical Methods of Physics, Addison-Wesley Publishing Company, Inc, Redwood City, CA (1970)

  • [25] 

    S. Mertens

    Phase transition in the number partitioning problem

    Phys. Rev. Lett., 81 (20) (1998), pp. 4281–4284

  • [26] 

    S. Mertens, A complete anytime algorithm for balanced number partitioning, preprint xxx.lanl.gov/abs/cs.DS/9903011, 1999.

  • [27] 

    S. Mertens

    Random costs in combinatorial optimization

    Phys. Rev. Lett., 84 (7) (2000), pp. 1347–1350

  • [28] 

    M. Mézard, G. Parisi, M.A. Virasoro

    Spin Glass Theory and Beyond, World Scientific, Singapore (1987)

  • [29] 

    R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, L. Troyanksy

    Determining computational complexity from characteristic ‘phase transitions’

    Nature, 400 (1999), pp. 133–137

  • [30] 

    J.P. Provost, G. Vallee

    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

  • [31] 

    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.

  • [32] 

    W. Ruml, J.T. Ngo, J. Marks, S.M. Shieber

    Easily searched encodings for number partitioning

    J. Opt. Theory Appl., 89 (2) (1996), pp. 251–291

  • [33] 

    Li-Hui Tsai

    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.