• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Sampling and Counting Crossing-Free Matchings.
【24h】

Sampling and Counting Crossing-Free Matchings.

机译：采样和计数无交叉匹配。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Sampling of combinatorial structures is an important statistical tool used in applications in a number of areas ranging from statistical physics, data mining, to biological sciences. Of comparable importance is the computation of the cor- responding partition function, which, in the case of the uniform distribution, is equivalent to the problem of counting all such structures. For self-reducible combinatorial structures, once we can produce an almost uniform sample from them, then we can approximately count them.;Using a Markov chain Monte Carlo method, this thesis presents polynomial-time algorithms to approximately count and almost uniformly sample crossing-free matchings for certain input classes of graphs. Since the problem in its generality appears to be difficult, we made natural restrictions on the in- put graphs. Namely, we consider vertices arranged in a grid in the plane, where edges are line segments connecting the vertices and a matching is crossing-free if no two matching edges intersect. For appropriate bounds on the dimensions of the grid and the edge lengths, we show that a natural Markov chain is rapidly mixing and that the problem is self-reducible.
机译：组合结构的采样是重要的统计工具，广泛用于从统计物理学，数据挖掘到生物科学的许多领域。具有相当重要意义的是相应分区函数的计算，在均匀分布的情况下，它等同于计算所有此类结构的问题。对于自简化组合结构，一旦我们可以从它们中产生几乎均匀的样本，就可以对其进行近似计数。；本文使用马尔可夫链蒙特卡洛方法，提出了多项式时间算法来近似计数并近似均匀地对样本进行交叉。图的某些输入类别的免费匹配。由于一般性问题似乎很困难，因此我们对输入图进行了自然限制。即，我们考虑在平面中以网格排列的顶点，其中边是连接顶点的线段，并且如果没有两个匹配边相交，则匹配是不交叉的。对于网格尺寸和边长的适当边界，我们显示出自然的马尔可夫链正在迅速混合，并且该问题是可自行解决的。

著录项

  • 作者

    Sun, Wenbo.;

  • 作者单位

    Rochester Institute of Technology.;

  • 授予单位 Rochester Institute of Technology.;
  • 学科 Computer science.
  • 学位 M.S.
  • 年度 2016
  • 页码 55 p.
  • 总页数 55
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 公共建筑;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号