课题基金 / 基金详情

Research on Algorithms for Random Generation of Discrete Objects

Research on Algorithms for Random Generation of Discrete Objects
离散对象随机生成算法研究
批准号：
20740056
负责人：
KIJIMA Shuji
金额：
$2.16万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2008
资助国家：
日本
项目状态：
已结题
起止时间：
2008 至 2010
来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20740056/
关键词：
応用数学アルゴリズム確率論マルコフ連鎖グラフ論離散数学乱択アルゴリズムマルコフ連鎖モンテカルロ法列挙コーダルグラフ分配束

项目摘要

项目成果

KIJIMA Shuji的其他基金

相似基金

相关文献

中文摘要
翻译
本文主要研究组合对象的随机抽样算法。本研究从计算复杂性理论的角度出发，试图探讨多项式时间算法是否存在于不同的对象上。对于弦图三明治、排队网络、部分有序集理想、Tutte多项式等，我们得到了多项式时间算法和不可能算法的一些计算复杂度结果。
英文摘要
This research is concerned with algorithms for random sampling of combinatorial objects. From a computational complexity theoretical viewpoint, this research tries to figure out whether polynomial time algorithms exist for several objects. For chorda graph sandwiches, queuing networks, ideals of partially ordered sets, Tutte polynomials etc, we obtained some computational complexity results on polynomial time algorithms and impossibility.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
How Slow, or Fast, Are Standard Random Walks? - Analyses of Hitting and Cover Times on Tree
标准随机游走有多慢或多快？
DOI： 10.1007/978-3-642-02427-6_18
发表时间： 2011
期刊： 20th Annual Symposium on Foundations of Computer Science (sfcs 1979)
影响因子： --
作者： [Yoshiaki Nonaka, H. Ono, S. Kijima, M. Yamashita]
通讯作者： M. Yamashita
一般化メディアン安定結婚問題に対する乱択近似アルゴリズム
广义中值稳定婚姻问题的随机逼近算法
DOI： --
发表时间： 2008
期刊：
影响因子： --
作者： [中丸麻由子, 小池心平, 辻本昌弘, 来嶋秀治,根本俊男]
通讯作者： 来嶋秀治,根本俊男
Upper and Lower Bounds of Space Complexity of Self-Stabilizing Leader Election in Mediated Population Protocol
介导群体协议中自稳定领导者选举的空间复杂度上下界
DOI： 10.1007/978-3-642-17653-1_35
发表时间： 2010
期刊： OPODIS
影响因子： --
作者： [Ryu Mizoguchi, Hirotaka Ono, Shuji Kijima, Masafumi Yamashita]
通讯作者： Masafumi Yamashita
A polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise
用于 Q-Ising 的多项式时间完美采样器，具有与顶点无关的噪声
DOI： --
发表时间： 2011
期刊： J. Comb. Optim
影响因子： --
作者： [Masaki Yamamoto, Shuji Kijima, Yasuko Matsui]
通讯作者： Yasuko Matsui
共 20 条
    Deterministic Random Walk
    • 批准号：
      23650007
    • 项目类别：
      Grant-in-Aid for Challenging Exploratory Research
    • 资助金额：
      $2.33万
    • 财政年份：
      2012
    • 负责人：
      KIJIMA Shuji
    • 依托单位：
      Kyushu University
    海外基金