Large deviation principles for Euclidean functionals and other nearly additive processes |
| |
Authors: | Timo Seppäläinen J.E. Yukich |
| |
Affiliation: | (1) Department of Mathematics, Iowa State University, Ames, Iowa 50011, USA. e-mail: seppalai@iastate.edu, US;(2) Department of Mathematics, Lehigh University, 14 E. Packer Avenue, Bethlehem, PA 18015-3174, USA. e-mail: joseph.yukich@lehigh.edu, US |
| |
Abstract: | We prove a large deviation principle for a process indexed by cubes of the multidimensional integer lattice or Euclidean space, under approximate additivity and regularity hypotheses. The rate function is the convex dual of the limiting logarithmic moment generating function. In some applications the rate function can be expressed in terms of relative entropy. The general result applies to processes in Euclidean combinatorial optimization, statistical mechanics, and computational geometry. Examples include the length of the minimal tour (the traveling salesman problem), the length of the minimal matching graph, the length of the minimal spanning tree, the length of the k-nearest neighbors graph, and the free energy of a short-range spin glass model. Received: 3 April 1999 / Revised version: 23 June 1999 / Published online: 8 May 2001 |
| |
Keywords: | Mathematics Subject Classification (2000): 60F10 05C80 60D05 |
本文献已被 SpringerLink 等数据库收录! |
|