Graph bisection problem: approaches from statistical mechanics and theoretical computer science

图二分问题:统计力学和理论计算机科学的方法

基本信息

  • 批准号:
    22300003
  • 负责人:
  • 金额:
    $ 11.65万
  • 依托单位:
  • 依托单位国家:
    日本
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
  • 财政年份:
    2010
  • 资助国家:
    日本
  • 起止时间:
    2010-04-01 至 2014-03-31
  • 项目状态:
    已结题

项目摘要

Statistical mechanics has developed various techniques for analyzing large scale and complicated statistical models through research on complex physical systems such as spin glasses. Recently, much attention has been paid for such methodologies as foundations of efficient approximate algorithms and powerful analytical techniques in information sciences. The main objective of this research project is to deepen the understanding of the effectiveness of such methodologies by collaboration of a physicist and a theoretical computer scientist on a concrete problem. The problem that we focused on was graph bisection problems. We particularly examined the origin of the effectiveness of the ``spectral method'', which is known as a dominant approximate solver for the bisection problem. As a practical application of the graph bisection problem, we also improved an exiting method for the extraction of polarity lexicon from word networks utilizing the knowledge of statistical mechanics.
统计力学通过对自旋玻璃等复杂物理系统的研究,发展了各种分析大规模复杂统计模型的技术。近年来,作为有效近似算法和强大分析技术基础的方法论在信息科学中受到了广泛关注。该研究项目的主要目标是通过物理学家和理论计算机科学家在具体问题上的合作,加深对这种方法的有效性的理解。我们关注的问题是图二分问题。我们特别研究了“谱方法”的有效性的起源,该方法被称为二分法问题的主要近似求解器。作为图二分问题的一个实际应用,我们还利用统计力学的知识改进了现有的从词网络中提取极性词典的方法。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Statistical mechanics approach to compressive sensing
压缩传感的统计力学方法
  • DOI:
  • 发表时间:
    2010
  • 期刊:
  • 影响因子:
    0
  • 作者:
    竹内啓悟;田中利幸;Y. Kabashima
  • 通讯作者:
    Y. Kabashima
Cavity-based robustness analysis of complex networks
复杂网络的基于腔的鲁棒性分析
  • DOI:
  • 发表时间:
    2013
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Uchida;S.;山下俊一;タウフィックラチマン;湯元清文;Y.Kabashima and S.Watanabe
  • 通讯作者:
    Y.Kabashima and S.Watanabe
Statistical Mechanical Analysis of a Compressed Sensing Utilizing Correlated Compression Matrix
利用相关压缩矩阵对压缩感知进行统计力学分析
  • DOI:
  • 发表时间:
    2010
  • 期刊:
  • 影响因子:
    0
  • 作者:
    K.Takeda;Y.Kabashima
  • 通讯作者:
    Y.Kabashima
Cavity approach to complex networks
复杂网络的空腔方法
  • DOI:
  • 发表时间:
    2014
  • 期刊:
  • 影响因子:
    0
  • 作者:
    武田正倫;波部重久;久保田正秀;Y. Kabashima and S. Watanabe
  • 通讯作者:
    Y. Kabashima and S. Watanabe
Average Growth Rate of Low-Density Generator-Matrix Codes Ensembles
低密度生成矩阵码系综的平均增长率
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

KABASHIMA Yoshiyuki其他文献

KABASHIMA Yoshiyuki的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('KABASHIMA Yoshiyuki', 18)}}的其他基金

Management Research on "Deepening and Expansion of Statistical Mechanical Informatics"
“统计机械信息学的深化与拓展”管理研究
  • 批准号:
    18079008
  • 财政年份:
    2006
  • 资助金额:
    $ 11.65万
  • 项目类别:
    Grant-in-Aid for Scientific Research on Priority Areas
Study on replica extension of approximate probability calculation algorithms
近似概率计算算法的副本扩展研究
  • 批准号:
    18079006
  • 财政年份:
    2006
  • 资助金额:
    $ 11.65万
  • 项目类别:
    Grant-in-Aid for Scientific Research on Priority Areas
Research on replica symmetry breaking in sparsely connected spin glass models
稀疏连接自旋玻璃模型中复制对称性破缺的研究
  • 批准号:
    17340116
  • 财政年份:
    2005
  • 资助金额:
    $ 11.65万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
Establishment of statistical mechanical methods in information sciences
信息科学统计力学方法的建立
  • 批准号:
    14084206
  • 财政年份:
    2002
  • 资助金额:
    $ 11.65万
  • 项目类别:
    Grant-in-Aid for Scientific Research on Priority Areas
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了