اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPolymer Dynamics via Cliques: New Conditions for Approximations
246
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition---the clique dynamics condition---, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least $2^{1/alpha}$ for the hard-core model on bipartite $alpha$-expanders.
قيم البحث
اقرأ أيضاً
We consider the median dynamics process in general graphs. In this model, each vertex has an independent initial opinion uniformly distributed in the interval [0,1] and, with rate one, updates its opinion to coincide with the median of its neighbors.
This process provides a continuous analog of majority dynamics. We deduce properties of median dynamics through this connection and raise new conjectures regarding the behavior of majority dynamics on general graphs. We also prove these conjectures on some graphs where majority dynamics has a simple description.
This paper is concerned with transition paths within the framework of the overdamped Langevin dynamics model of chemical reactions. We aim to give an efficient description of typical transition paths in the small temperature regime. We adopt a variat
ional point of view and seek the best Gaussian approximation, with respect to Kullback-Leibler divergence, of the non-Gaussian distribution of the diffusion process. We interpret the mean of this Gaussian approximation as the most likely path and the covariance operator as a means to capture the typical fluctuations around this most likely path. We give an explicit expression for the Kullback-Leibler divergence in terms of the mean and the covariance operator for a natural class of Gaussian approximations and show the existence of minimisers for the variational problem. Then the low temperature limit is studied via $Gamma$-convergence of the associated variational problem. The limiting functional consists of two parts: The first part only depends on the mean and coincides with the $Gamma$-limit of the Freidlin-Wentzell rate functional. The second part depends on both, the mean and the covariance operator and is minimized if the dynamics are given by a time-inhomogenous Ornstein-Uhlenbeck process found by linearization of the Langevin dynamics around the Freidlin-Wentzell minimizer.
Significant progress was made in recent years in the understanding of the proton spin kinetics in polymer melts. Generally, the proton spin kinetics is determined by intramolecular and intermolecular magnetic dipole-dipole contributions of proton spi
ns. During many decades it was postulated that the main contribution is a result of intramolecular magnetic dipole-dipole interactions of protons belonging to the same polymer segment. It appears that this postulate is far from reality. The relative weights of intra- and intermolecular contributions are time dependent and sensitive to details of polymer chain dynamics. It is shown that for isotropic models of polymer dynamics the influence of the intermolecular magnetic dipole-dipole interactions increases faster with increasing evolution time (i.e. decreasing frequency) than the corresponding influence of the intramolecular counterpart. On the other hand, an inverted situation is predicted by the tube-reptation model: here the influence of the intramolecular magnetic dipole-dipole interactions increases faster with time than the contribution from intermolecular interactions. The intermolecular contribution in the proton relaxation of polymer melts can experimentally be isolated using the isotope dilution technique and this opens a new perspective for experimental investigations of polymer dynamics by proton NMR.
Given strong uniqueness for an It^os stochastic equation, we prove that its solution can beconstructed on any probability space by using, for example, Eulers polygonal approximations. Stochastic equations in $mathbb{R}^{d}$ and in domains in $mathbb{
R}^{d}$ are considered. This is almost a copy of an old article in which we correct errors in the original proof of Lemma 4.1 found by Martin Dieckmann in 2013. We present also a new result on the convergence of tamed Euler approximations for SDEs with locally unbounded drifts, which we achieve by proving an estimate for appropriate exponential moments.
Humans are bad with probabilities, and the analysis of randomized algorithms offers many pitfalls for the human mind. Drift theory is an intuitive tool for reasoning about random processes. It allows turning expected stepwise changes into expected fi
rst-hitting times. While drift theory is used extensively by the community studying randomized search heuristics, it has seen hardly any applications outside of this field, in spite of many research questions which can be formulated as first-hitting times. We state the most useful drift theorems and demonstrate their use for various randomized processes, including approximating vertex cover, the coupon collector process, a random sorting algorithm, and the Moran process. Finally, we consider processes without expected stepwise change and give a lemma based on drift theory applicable in such scenarios without drift. We use this tool for the analysis of the gamblers ruin process, for a coloring algorithm, for an algorithm for 2-SAT, and for a version of the Moran process without bias.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
