RESUMEN
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. We also show that the average optimal cost is not a self-averaging quantity by explicitly computing the variance of its distribution in the thermodynamic limit. Moreover, we prove that the cost of the optimal cycle is not smaller than twice the cost of the optimal assignment of the same set of points. Interestingly, this bound is saturated in the thermodynamic limit.
RESUMEN
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. By using a numerical solution of the saddle-point equations, we provide predictions that are confirmed by numerical simulations.
RESUMEN
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.e., fluctuations averaged along the drive, are Gaussian, irrespective of this being actually the case in the stationary state. Strong numerical evidence is provided, in remarkable agreement with that theory, both for the driven and undriven lattice gases, which therefore turn out to display the same short-time dynamics.
RESUMEN
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. We analytically obtain the average optimal cost in the asymptotic regime of very large number of points N and some correlation functions for a power-law-type cost function in the form c(z)=z^{p}, both in the p>1 case and in the p<0 case. The scaling of the optimal mean cost with the number of points is N^{-p/2} for the assignment and N^{-p} for the matching when p>1, whereas in both cases it is a constant when p<0. Finally, our predictions are compared with the results of numerical simulations.
RESUMEN
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., noninteracting, effective theory, both for the nonequilibrium lattice gases and, to some extent, their equilibrium counterpart. Such a superuniversal behavior is observed only at short times after a critical quench, while the various models display their distinct behaviors in the stationary states, described by the corresponding, known universality classes.
RESUMEN
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. By numerical and analytical calculations of the particle current as a function of the density and of the driving field, we identify (i) an abrupt breakdown transition between insulating and conducting states, (ii) current quantization into discrete phases where a finite current flows with infinite differential resistivity, and (iii) a fractal hierarchy of excitations, related to the Farey sequences of number theory. We argue that the origin of these effects is the competition between scales, which also causes the counterintuitive phenomenon that crystalline states can melt by increasing the density.
RESUMEN
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. A previous ansatz for the matching problem on the flat hypertorus is obtained as a particular case.
RESUMEN
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. E 90, 012118 (2014)] to evaluate the average optimal matching cost. We consider both the grid-Poisson matching problem and the Poisson-Poisson matching problem. We also show that the correlation function is strictly related to the Green's function of the Laplace operator on the hypertorus.
RESUMEN
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.
RESUMEN
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.
RESUMEN
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. The error is approximately 1%-2% below the overlap concentration and rises at most to 5%-10% in the limit of very large polymer concentrations.
RESUMEN
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. For the radius of gyration, comparison with field-theoretical predictions shows that the relative error should be at most 5% in the limit of very large polymer concentrations.
RESUMEN
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.e., related to order-parameter fluctuations with wave vector perpendicular to the direction of the field) differ from the mean-field behavior--both predicted and observed in the DLG. In sharp contrast to the case of the DLG, FSS can be established only for rectangular lattices where the dimension in the direction of the field grows as the second power of the other dimension. Further, the transverse Binder cumulant does not vanish at the critical point.
RESUMEN
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). It follows that, in two dimensions, this fermionic model is perturbatively asymptotically free.
RESUMEN
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. Rev. Lett. 88, 047203 (2002)], we find a first-order transition for p>p(c) and no finite-temperature phase transitions for p
RESUMEN
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.2 in two dimensions and z approximately 2.1 in three dimensions. At the theta point in two dimensions we have z approximately 2.3.