{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T17:20:56Z","timestamp":1773681656475,"version":"3.50.1"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1991,6]]},"DOI":"10.1007\/bf01759049","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:43:56Z","timestamp":1118918636000},"page":"302-345","source":"Crossref","is-referenced-by-count":123,"title":["A theoretical framework for simulated annealing"],"prefix":"10.1007","volume":"6","author":[{"given":"Fabio","family":"Romeo","sequence":"first","affiliation":[]},{"given":"Alberto","family":"Sangiovanni-Vincentelli","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01759049_CR1","first-page":"193","volume":"40","author":"E. H. L. Aarts","year":"1985","unstructured":"E. H. L. Aarts and P. J. M. van Laarhoven. Statistical Cooling: A General Approach to Combinatorial Optimization Problems.Philips J. Res.,40:193\u2013226, 1985.","journal-title":"Philips J. Res."},{"key":"BF01759049_CR2","volume-title":"Simulated Annealing: Theory and Applications","author":"E. H. L. Aarts","year":"1987","unstructured":"E. H. L. Aarts and P. J. M. van Laarhoven.Simulated Annealing: Theory and Applications. Reidel, Dordrecht, 1987."},{"key":"BF01759049_CR3","series-title":"Technical Report","volume-title":"Graduate School of Business","author":"S. Anily","year":"1985","unstructured":"S. Anily and A. Federgruen. Probabilistic Analysis of Simulated Annealing Methods. Technical Report, Graduate School of Business, Columbia University, New York, 1985."},{"key":"BF01759049_CR4","doi-asserted-by":"crossref","first-page":"657","DOI":"10.2307\/3214097","volume":"24","author":"S. Anily","year":"1987","unstructured":"S. Anily and A. Federgruen. Simulated Annealing Methods with General Acceptance Probabilities.J. Appl. Probab.,24: 657\u2013667, 1987.","journal-title":"J. Appl. Probab."},{"key":"BF01759049_CR5","unstructured":"C. R. Aragon, D. S. Johnson, L. A. McGeoch, and C. Schevon. Simulated Annealing Performance Studies. Workshop on Statistical Physics in Engineering and Biology, April, 1984."},{"key":"BF01759049_CR6","unstructured":"P. Banerjee and M. Jones. A Parallel Simulated Annealing Algorithm for Standard Cell Placement on a Hypercube Computer.Proc. ICCAD, pages 34\u201337, 1986."},{"key":"BF01759049_CR7","volume-title":"Monte Carlo Methods in Statistical Physics","author":"K. Binder","year":"1978","unstructured":"K. Binder.Monte Carlo Methods in Statistical Physics. Springer Verlag, Berlin, 1978."},{"issue":"3","key":"BF01759049_CR8","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1080\/00401706.1986.10488128","volume":"28","author":"I. O. Bohachevsky","year":"1986","unstructured":"I. O. Bohachevsky, M. E. Johnson, and M. L. Stein. Generalized Simulated Annealing for Function Optimization.Technometrics,28 (3): 209\u2013217, August, 1986.","journal-title":"Technometrics"},{"key":"BF01759049_CR9","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1109\/TCAD.1987.1270327","volume":"6","author":"A. Casotto","year":"1987","unstructured":"A. Casotto, F. Romeo, and A. Sangiovanni-Vincentelli. A Parallel Simulated Annealing Algorithm for the Placement of Macro-Cells.IEEE Trans. Computer-Aided Design,6: 838\u2013847, September, 1987.","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"BF01759049_CR10","unstructured":"A. Casotto and A. Sangiovanni-Vincentelli. Placement of Standard Cells Using Simulated Annealing on the Connection Machine.Proc. ICCAD, pages 350\u2013353, 1987."},{"issue":"2","key":"BF01759049_CR11","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1017\/S0269964800000723","volume":"2","author":"D. P. Connors","year":"1988","unstructured":"D. P. Connors and P. R. Kumar. Balance of Recurrence Orders in Time-Inhomogeneous Markov Chains with Applications to Simulated Annealing.Probab. Engrg. Inform. Sci.,2 (2): 157\u2013184, 1988.","journal-title":"Probab. Engrg. Inform. Sci."},{"key":"BF01759049_CR12","unstructured":"F. Darema-Rogers, S. Kirkpatrick, and V. A. Norton. Simulated Annealing on Shared Memory Parallel Systems.IBM J. Res. Develop., 1987."},{"key":"BF01759049_CR13","volume-title":"Probability and Random Processes: An Introduction for Applied Scientists and Engineers","author":"W. B. Davenport","year":"1970","unstructured":"W. B. Davenport.Probability and Random Processes: An Introduction for Applied Scientists and Engineers. McGraw-Hill, New York, 1970."},{"issue":"4","key":"BF01759049_CR14","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0020-0190(88)90024-5","volume":"27","author":"U. Faigle","year":"1988","unstructured":"U. Faigle and R. Schrader. On the Convergence of Stationary Distributions in Simulated Annealing Algorithms.Inform. Process. Lett.,27 (4): 189\u2013194, April, 1988.","journal-title":"Inform. Process. Lett."},{"key":"BF01759049_CR15","volume-title":"Markov Chains","author":"D. Freedman","year":"1971","unstructured":"D. Freedman.Markov Chains. Holden-Day, San Francisco, CA, 1971."},{"key":"BF01759049_CR16","series-title":"Technical Report LIDS-TH-1688","volume-title":"Analysis of Simulated Annealing Type of Algorithms","author":"S. Gelfand","year":"1987","unstructured":"S. Gelfand. Analysis of Simulated Annealing Type of Algorithms. Technical Report LIDS-TH-1688, Massachusetts Institute of Technology, Cambridge, MA., 1987."},{"key":"BF01759049_CR17","doi-asserted-by":"crossref","unstructured":"S. Gelfand and S. Mitter. Analysis of Simulated Annealing for Optimization.Proc. 24th Conf. on Decision and Control, pages 779\u2013786, December 1985.","DOI":"10.21236\/ADA170174"},{"key":"BF01759049_CR18","series-title":"Technical Report","volume-title":"Simulated Annealing with Noisy or Imprecise Energy Measurements","author":"S. Gelfand","year":"1987","unstructured":"S. Gelfand and S. Mitter. Simulated Annealing with Noisy or Imprecise Energy Measurements. Technical Report, Massachusetts Institute of Technology, Cambridge, MA, 1987."},{"key":"BF01759049_CR19","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1109\/TPAMI.1984.4767596","volume":"6","author":"S. Geman","year":"1984","unstructured":"S. Geman and D. Geman. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images.IEEE Trans. Pattern Anal. Mach. Intell.,6: 721\u2013741, 1984.","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"BF01759049_CR20","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF01007975","volume":"39","author":"B. Gidas","year":"1984","unstructured":"B. Gidas. Non-Stationary Markov Chains and Convergence of the Annealing Algorithm.J. Statist. Phys.,39: 73\u2013131, 1984.","journal-title":"J. Statist. Phys."},{"key":"BF01759049_CR21","volume-title":"An Elementary Introduction to the Theory of Probability","author":"B. V. Gnedenko","year":"1961","unstructured":"B. V. Gnedenko and A. Y. Khinchin.An Elementary Introduction to the Theory of Probability, Freeman, San Francisco, CA, 1961."},{"issue":"2","key":"BF01759049_CR22","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1287\/moor.13.2.311","volume":"13","author":"B. Hajek","year":"1985","unstructured":"B. Hajek. Cooling Schedules for Optimal Annealing.Math. Oper. Res.,13 (2): 311\u2013329, 1985.","journal-title":"Math. Oper. Res."},{"key":"BF01759049_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-009-5819-7","volume-title":"Monte Carlo Methods","author":"J. M. Hammersley","year":"1964","unstructured":"J. M. Hammersley and D. C. Handscomb.Monte Carlo Methods, Wiley, New York, 1964."},{"issue":"1","key":"BF01759049_CR24","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","volume":"57","author":"W. K. Hastings","year":"1970","unstructured":"W. K. Hastings. Monte Carlo Sampling Methods Using Markov Chains and Their Applications.Biometrika,57 (1): 97\u2013109, 1970.","journal-title":"Biometrika"},{"key":"BF01759049_CR25","volume-title":"The Connection Machine","author":"D. Hillis","year":"1985","unstructured":"D. Hillis.The Connection Machine. MIT Press, Cambridge, MA, 1985."},{"key":"BF01759049_CR26","volume-title":"Introduction to Mathematical Statistics","author":"P. G. Hoel","year":"1962","unstructured":"P. G. Hoel.Introduction to Mathematical Statistics. Wiley, New York, 1962."},{"issue":"4","key":"BF01759049_CR27","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1007\/BF01224127","volume":"115","author":"R. Holley","year":"1988","unstructured":"R. Holley and D. Stroock. Simulated Annealing via Sobolev Inequalities.Comm. Math. Phys.,115 (4): 553\u2013569, April, 1988.","journal-title":"Comm. Math. Phys."},{"key":"BF01759049_CR28","unstructured":"M. D. Huang, F. Romeo, and A. Sangiovanni-Vincentelli. An Efficient General Cooling Schedule for Simulated Annealing,Proc. ICCAD, pages 381\u2013384, 1986."},{"key":"BF01759049_CR29","volume-title":"Master's thesis","author":"S. Hustin","year":"1988","unstructured":"S. Hustin. Tim, a New Standard Cell Placement Program Based on the Simulated Annealing Algorithm. Master's thesis, University of California, Berkeley, CA, March, 1988."},{"key":"BF01759049_CR30","volume-title":"Markov Chains: Theory and Applications","author":"D. L. Isaacson","year":"1976","unstructured":"D. L. Isaacson and R. W. Madsen.Markov Chains: Theory and Applications. Wiley, New York, 1976."},{"key":"BF01759049_CR31","volume-title":"Finite Markov Chains","author":"J. G. Kemeny","year":"1976","unstructured":"J. G. Kemeny and J. L. Snell.Finite Markov Chains. Springer-Verlag, New York, 1976."},{"issue":"4598","key":"BF01759049_CR32","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick","year":"1983","unstructured":"S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by Simulated Annealing.Science,220(4598): 671\u2013680, 13 May, 1983.","journal-title":"Science"},{"key":"BF01759049_CR33","doi-asserted-by":"crossref","unstructured":"S. A. Kravitz and R. A. Rutenbar. Multiprocessor-based Placement by Simulated Annealing.Proc. 23rd Design Automation Conf., pages 567\u2013573, 1986.","DOI":"10.1109\/DAC.1986.1586144"},{"key":"BF01759049_CR34","unstructured":"J. Lam and J-M. Delosme. Logic Minimization Using Simulated Annealing.Proc. ICCAD, pages 348\u2013352, 1986."},{"key":"BF01759049_CR35","series-title":"Technical Report 8608","volume-title":"An Adaptive Annealing Schedule","author":"J. Lam","year":"1987","unstructured":"J. Lam and J.-M. Delosme. An Adaptive Annealing Schedule. Technical Report 8608, University of Yale, New Haven, C., 1987."},{"key":"BF01759049_CR36","doi-asserted-by":"crossref","unstructured":"J. Lam and J-M. Delosme. Simulated Annealing: A Fast Heuristic for Some Generic Layout Problems.Proc. ICCAD, pages 510\u2013513, 1988.","DOI":"10.1109\/ICCAD.1988.122560"},{"key":"BF01759049_CR37","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01582166","volume":"34","author":"M. Lundy","year":"1986","unstructured":"M. Lundy and A. Mees. Convergence of the Annealing Algorithm.Math. Programming,34: 111\u2013124, 1986.","journal-title":"Math. Programming"},{"issue":"2","key":"BF01759049_CR38","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1214\/aop\/1176996986","volume":"1","author":"R. W. Madsen","year":"1973","unstructured":"R. W. Madsen and D. L. Isaacson. Strongly Ergodic Behavior for Non-Stationary Markov Processes.Ann. Prob.,1 (2): 329\u2013335, 1973.","journal-title":"Ann. Prob."},{"key":"BF01759049_CR39","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N. Metropolis","year":"1953","unstructured":"N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, and A. H. Teller. Equation of State Calculations by Fast Computer Machines.J. Chem. Phys.,21: 1087, 1953.","journal-title":"J. Chem. Phys."},{"key":"BF01759049_CR40","doi-asserted-by":"crossref","unstructured":"D. Mitra, F. Romeo, and A. Sangiovanni-Vincentelli. Convergence and Finite-Time Behavior of Simulated Annealing.Proc. 24th Conf. on Decision and Control, December, 1985.","DOI":"10.1109\/CDC.1985.268600"},{"key":"BF01759049_CR41","doi-asserted-by":"crossref","first-page":"747","DOI":"10.2307\/1427186","volume":"18","author":"D. Mitra","year":"1986","unstructured":"D. Mitra, F. Romeo, and A. Sangiovanni-Vincentelli. Convergence and Finite-Time Behavior of Simulated Annealing.Adv. Appl. Probab.,18: 747\u2013771, 1986.","journal-title":"Adv. Appl. Probab."},{"issue":"4","key":"BF01759049_CR42","doi-asserted-by":"crossref","first-page":"1351","DOI":"10.1103\/PhysRevA.37.1351","volume":"37","author":"J. D. Nulton","year":"1988","unstructured":"J. D. Nulton and P. Salamon. Statistical Mechanics of Combinatorial Optimization.Phys. Rev. A,37(4): 1351\u20131356, February, 1988.","journal-title":"Phys. Rev. A"},{"key":"BF01759049_CR43","unstructured":"R. H. J. M. Otten and L. P. P. P. van Ginneken. Floorplan Design Using Simulated Annealing.Proc. ICCAD, pages 96\u201398, 1984."},{"key":"BF01759049_CR44","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-1627-5","volume-title":"Simulated Annealing: The Algorithm","author":"R. H. Otten","year":"1989","unstructured":"R. H. Otten and L. P. van Ginneken.Simulated Annealing: The Algorithm. Kluwer, Boston, MA, 1989."},{"issue":"3","key":"BF01759049_CR45","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1093\/biomet\/60.3.607","volume":"60","author":"P. H. Peskun","year":"1973","unstructured":"P. H. Peskun. Optimum Monte Carlo Sampling Using Markov Chains.Biometrika,60(3): 607\u2013612, 1973.","journal-title":"Biometrika"},{"key":"BF01759049_CR46","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316726","volume-title":"Stochastic Simulation","author":"B. D. Ripley","year":"1987","unstructured":"B. D. Ripley.Stochastic Simulation. Wiley, New York, 1987."},{"key":"BF01759049_CR47","volume-title":"Ph. D. thesis","author":"F. Romeo","year":"1989","unstructured":"F. Romeo. Simulated Annealing: Theory and Applications to Layout Problems. Ph. D. thesis, University of California, Berkeley, CA, May 1989."},{"key":"BF01759049_CR48","volume-title":"Technical Report RO 851125","author":"Y. Rossier","year":"1985","unstructured":"Y. Rossier, M. Troyon, and T. Liebling. Probabilistic Exchange Algorithms and Euclidean Traveling Salesman Problems. Technical Report RO 851125, EPF, Lousanne, 1985."},{"key":"BF01759049_CR49","volume-title":"Principles of Mathematical Analysis","author":"W. Rudin","year":"1976","unstructured":"W. Rudin.Principles of Mathematical Analysis. McGraw-Hill, New York, 1976."},{"key":"BF01759049_CR50","doi-asserted-by":"crossref","unstructured":"A. Sangiovanni-Vincentelli. Editor's Foreword.Algorithmica, this issue.","DOI":"10.1007\/BF01759048"},{"key":"BF01759049_CR51","doi-asserted-by":"crossref","DOI":"10.1007\/0-387-32792-4","volume-title":"Non-negative Matrices and Markov Chains","author":"E. Seneta","year":"1981","unstructured":"E. Seneta.Non-negative Matrices and Markov Chains. Springer-Verlag, New York, 1981."},{"key":"BF01759049_CR52","volume-title":"Master's thesis","author":"G. B. Sorkin","year":"1987","unstructured":"G. B. Sorkin. Combinatorial Optimization, Simulated Annealing and Fractals. Master's thesis. University of California, Berkeley, CA, December, 1987."},{"key":"BF01759049_CR53","unstructured":"G. B. Sorkin. Rapidly Mixing Analysis of Simulated Annealing on Fractals.Proc. of Sixth Annual MIT VLSI Conf., pages 331\u2013351, April, 1990."},{"key":"BF01759049_CR54","doi-asserted-by":"crossref","unstructured":"G. B. Sorkin. Efficient Simulated Annealing on Fractal Energy Landscapes.Algorithmica, this issue, pp. 367\u2013418, 1991.","DOI":"10.1007\/BF01759051"},{"key":"BF01759049_CR55","series-title":"Technical Report 12923","volume-title":"Optimal Annealing Schedules: A Case Study","author":"P. N. Strenski","year":"1987","unstructured":"P. N. Strenski. Optimal Annealing Schedules: A Case Study. Technical Report 12923, I.B.M. T. J. Watson Research Center, Yorktown Heights, NY, 1987."},{"key":"BF01759049_CR56","doi-asserted-by":"crossref","unstructured":"P. N. Strenski and S. Kirkpatrick. Analysis of Finite Length Annealing Schedules.Algorithmica, this issue, pp. 346\u2013366, 1991.","DOI":"10.1007\/BF01759050"},{"key":"BF01759049_CR57","volume-title":"Stochastic Modeling and Analysis: A Computational Approach","author":"H. C. Tijms","year":"1986","unstructured":"H. C. Tijms.Stochastic Modeling and Analysis: A Computational Approach, Wiley, Chichester, 1986."},{"key":"BF01759049_CR58","doi-asserted-by":"crossref","DOI":"10.21236\/ADA161598","volume-title":"Markov Chains with Rare Transitions and Simulated Annealing","author":"J. N. Tsitsiklis","year":"1985","unstructured":"J. N. Tsitsiklis.Markov Chains with Rare Transitions and Simulated Annealing. MIT Laboratory for Information and Decision Systems, Cambridge, MA, August, 1985."},{"key":"BF01759049_CR59","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF00940812","volume":"45","author":"V. \u010cerny","year":"1985","unstructured":"V. \u010cerny. Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm.J. Optim. Theory Appl.,45: 41\u201351, 1985.","journal-title":"J. Optim. Theory Appl."},{"key":"BF01759049_CR60","doi-asserted-by":"crossref","unstructured":"S. White, Concept of Scale in Simulated Annealing.Proc. ICCD, pages 646\u2013651, 1984.","DOI":"10.1063\/1.34823"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759049.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01759049\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:27:11Z","timestamp":1586287631000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01759049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":60,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01759049"],"URL":"https:\/\/doi.org\/10.1007\/bf01759049","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}