Off-lattice noise reduced diffusion-limited aggregation in three dimensions

Using off-lattice noise reduction, it is possible to estimate the asymptotic properties of diffusion-limited aggregation clusters grown in three dimensions with greater accuracy than would otherwise be possible. The fractal dimension of these aggregates is found to be 2.50+/-0.01 , in agreement with earlier studies, and the asymptotic value of the relative penetration depth is xi/ R(dep) =0.122+/-0.002 . The multipole powers of the growth measure also exhibit universal asymptotes. The fixed point noise reduction is estimated to be epsilon(f) approximately 0.0035 , meaning that large clusters can be identified with a low noise regime. The slowest correction to scaling exponents are measured for a number of properties of the clusters, and the exponent for the relative penetration depth and quadrupole moment are found to be significantly different from each other. The relative penetration depth exhibits the slowest correction to scaling of all quantities, which is consistent with a theoretical result derived in two dimensions. We also note fast corrections to scaling, whose limited relevance is consistent with the requirement that clusters grow far enough in radius to support sufficient scales of ramification.

Characterization of the probabilistic traveling salesman problem

We show that stochastic annealing can be successfully applied to gain new results on the probabilistic traveling salesman problem. The probabilistic "traveling salesman" must decide on an a priori order in which to visit n cities (randomly distributed over a unit square) before learning that some cities can be omitted. We find the optimized average length of the pruned tour follows E(L(pruned))=sqrt[np](0.872-0.105p)f(np), where p is the probability of a city needing to be visited, and f(np)-->1 as np--> infinity. The average length of the a priori tour (before omitting any cities) is found to follow E(L(a priori))=sqrt[n/p]beta(p), where beta(p)=1/[1.25-0.82 ln(p)] is measured for 0.05< or =p< or =0.6. Scaling arguments and indirect measurements suggest that beta(p) tends towards a constant for p<0.03. Our stochastic annealing algorithm is based on limited sampling of the pruned tour lengths, exploiting the sampling error to provide the analog of thermal fluctuations in simulated (thermal) annealing. The method has general application to the optimization of functions whose cost to evaluate rises with the precision required.

Stochastic annealing

We show how to simulate a system in thermal equilibrium when the energy cannot be evaluated exactly: the error distribution needs to be symmetric, but it does not need to be known. We also solve the Ceperley-Dewing version of this problem, where the error distribution is taken to be fully known. These underlying ideas give an effective optimization strategy for problems where the evaluation of each design can be sampled only statistically, including an application to protein folding.

Off-lattice noise reduction and the ultimate scaling of diffusion-limited aggregation in two dimensions

Off-lattice diffusion-limited aggregation (DLA) clusters grown with different levels of noise reduction are found to be consistent with a simple fractal fixed point. Cluster shapes and their ensemble variation exhibit a dominant slowest correction to scaling, and this also accounts for the apparent "multiscaling" in the DLA mass distribution. We interpret the correction to scaling in terms of renormalized noise. The limiting value of this variable is strikingly small and is dominated by fluctuations in cluster shape. Earlier claims of anomalous scaling in DLA were misled by the slow approach to this small fixed point value.