论文标题
通过集团的聚合物动力学：近似的新条件
Polymer Dynamics via Cliques: New Conditions for Approximations
论文作者
论文摘要
抽象聚合物模型是加权对象的系统，称为聚合物，配备了不兼容的关系。与此类模型相关的一个重要数量是分区函数，它是所有兼容聚合物集的加权总和。各种近似问题减少了近似聚合物模型的分配函数。存在这种近似算法的核心是相应聚合物模型的重量条件。通过复杂分析或概率参数得出此类条件。我们遵循后一条路径并建立新的条件---集团动态条件---比文献中的限制性较小。我们引入了一个新的马尔可夫链，其中集团动力学条件暗示了通过利用不兼容的聚合物集团来快速混合的，这些聚合物自然而然地由算法问题转换为聚合物模型。这导致了几种近似算法的改进参数范围，例如在两部分$α$ -Expanders上的硬核模型的$ 2^{1/α} $的倍数。
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/α}$ for the hard-core model on bipartite $α$-expanders.
