Solution for a bipartite Euclidean traveling-salesman problem in one dimension.

The traveling-salesman problem is one of the most studied combinatorial optimization problems, because of the simplicity in its statement and the difficulty in its solution. We characterize the optimal cycle for every convex and increasing cost function when the points are thrown independently and with an identical probability distribution in a compact interval. We compute the average optimal cost for every number of points when the distance function is the square of the Euclidean distance.

Current quantization and fractal hierarchy in a driven repulsive lattice gas.

Driven lattice gases are widely regarded as the paradigm of collective phenomena out of equilibrium. While such models are usually studied with nearest-neighbor interactions, many empirical driven systems are dominated by slowly decaying interactions such as dipole-dipole and Van der Waals forces. Motivated by this gap, we study the nonequilibrium stationary state of a driven lattice gas with slow-decayed repulsive interactions at zero temperature.

Universal Gaussian behavior of driven lattice gases at short times.

The dynamic and static critical behaviors of driven and equilibrium lattice gas models are studied in two spatial dimensions. We show that in the short-time regime immediately following a critical quench, the dynamics of the transverse anisotropic order parameter, its autocorrelation, and Binder cumulant are consistent with the prediction of a Gaussian, i.e.

Random Euclidean matching problems in one dimension.

We discuss the optimal matching solution for both the assignment problem and the matching problem in one dimension for a large class of convex cost functions. We consider the problem in a compact set with the topology both of the interval and of the circumference. Afterwards, we assume the points' positions to be random variables identically and independently distributed on the considered domain.

Finite-size corrections in the random assignment problem.

We analytically derive, in the context of the replica formalism, the first finite-size corrections to the average optimal cost in the random assignment problem for a quite generic distribution law for the costs. We show that, when moving from a power-law distribution to a Γ distribution, the leading correction changes both in sign and in its scaling properties. We also examine the behavior of the corrections when approaching a δ-function distribution.

Short-Time Behavior and Criticality of Driven Lattice Gases.

The nonequilibrium short-time critical behaviors of driven and undriven lattice gases are investigated via Monte Carlo simulations in two spatial dimensions starting from a fully disordered initial configuration. In particular, we study the time evolution of suitably defined order parameters, which account for the strong anisotropy introduced by the homogeneous drive. We demonstrate that, at short times, the dynamics of all these models is unexpectedly described by an effective continuum theory in which transverse fluctuations, i.

Quadratic Stochastic Euclidean Bipartite Matching Problem.

We propose a new approach for the study of the quadratic stochastic Euclidean bipartite matching problem between two sets of N points each, N≫1. The points are supposed independently randomly generated on a domain Ω⊂R^{d} with a given distribution ρ(x) on Ω. In particular, we derive a general expression for the correlation function and for the average optimal cost of the optimal matching.

Scaling hypothesis for the Euclidean bipartite matching problem. II. Correlation functions.

We analyze the random Euclidean bipartite matching problem on the hypertorus in d dimensions with quadratic cost and we derive the two-point correlation function for the optimal matching, using a proper ansatz introduced by Caracciolo et al. [Phys. Rev.

One-dimensional Euclidean matching problem: exact solutions, correlation functions, and universality.

We discuss the equivalence relation between the Euclidean bipartite matching problem on the line and on the circumference and the Brownian bridge process on the same domains. The equivalence allows us to compute the correlation function and the optimal cost of the original combinatorial problem in the thermodynamic limit; moreover, we solve also the minimax problem on the line and on the circumference. The properties of the average cost and correlation functions are discussed.

Two-parameter model predictions and theta-point crossover for linear-polymer solutions.

We consider the first few virial coefficients of the osmotic pressure, the radius of gyration, the hydrodynamic radius, and the end-to-end distance for a monodisperse polymer solution. We determine the corresponding two-parameter model functions which parametrize the crossover between the good-solvent and the ideal-chain behavior. These results allow us to predict the osmotic pressure and the polymer size in the dilute regime in a large temperature region above the theta point.

Polymer size in dilute solutions in the good-solvent regime.

We determine the density expansion of the radius of gyration, of the hydrodynamic radius, and of the end-to-end distance for a monodisperse polymer solution in good-solvent conditions. We consider the scaling limit (large degree of polymerization), including the leading scaling corrections. Using the expected large-concentration behavior, we extrapolate these low-density expansions outside the dilute regime, obtaining a prediction for the radii for any concentration in the semidilute region.

Virial coefficients and osmotic pressure in polymer solutions in good-solvent conditions.

We determine the second, third, and fourth virial coefficients appearing in the density expansion of the osmotic pressure Pi of a monodisperse polymer solution in good-solvent conditions. Using the expected large-concentration behavior, we extrapolate the low-density expansion outside the dilute regime, obtaining the osmotic pressure for any concentration in the semidilute region. Comparison with field-theoretical predictions and experimental data shows that the obtained expression is quite accurate.

Critical behavior of the two-dimensional randomly driven lattice gas.

We investigate the critical behavior of the two-dimensional randomly driven lattice gas, in which particles are driven along one of the lattice axes by an infinite external field with randomly changing sign. A finite-size scaling (FSS) analysis provides novel evidences that this model is not in the same universality class as the driven lattice gas with a constant drive (DLG), contrarily to what has been recently reported in the literature. Indeed, the FSS functions of transverse observables (i.

Fermionic field theory for trees and forests.

We prove a generalization of Kirchhoff's matrix-tree theorem in which a large class of combinatorial objects are represented by non-Gaussian Grassmann integrals. As a special case, we show that unrooted spanning forests, which arise as a q-->0 limit of the Potts model, can be represented by a Grassmann theory involving a Gaussian term and a particular bilocal four-fermion term. We show that this latter model can be mapped, to all orders in perturbation theory, onto the N-vector model at N=-1 or, equivalently, onto the sigma model taking values in the unit supersphere in R(1|2).

Two-dimensional Heisenberg model with nonlinear interactions.

We investigate a two-dimensional classical N-vector model with a nonlinear interaction (1+sigma(i) x sigma(j))(p) in the large-N limit. As observed for N=3 by Blöte et al. [Phys.

Dynamic critical behavior of an extended reptation dynamics for self-avoiding walks.

We consider lattice self-avoiding walks and discuss the dynamic critical behavior of two dynamics that use local and bilocal moves and generalize the usual reptation dynamics. We determine the integrated and exponential autocorrelation times for several observables, perform a dynamic finite-size scaling study of the autocorrelation functions, and compute the associated dynamic critical exponents z. For the variables that describe the size of the walks, in the absence of interactions we find z approximately 2.