How to select constraints that help algorithms approximately solve constraint satisfaction problems

如何选择有助于算法近似解决约束满足问题的约束

• 批准号: 24500011
• 负责人: YAMAKAMI TOMOYUKI
• 金额: $ 3.41万
• 依托单位: University of Fukui
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2012
• 资助国家: 日本
• 起止时间: 2012-04-01 至 2015-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-24500011/
• 关键词: 制約充足問題; 最適化問題; 数え上げ問題; アルゴリズムの効率; ＃P完全; 対数領域計算; プッシュダウンオートマトン; ２極値定理; リスト行列グラフ分割問題; 時間計算量; プッシュダウン・オートマトン; 制約充足問題の最適解探索; 解の数え上げ問題; 対数領域計算可能性; 固定長領域計算量; リスト分割数え上げ問題; 時間・領域計算量; 解法アルゴリズムの効率; 小型計算機端末; 最適解近似アルゴリズム; 多項式時間; 近似保存還元性; Holant問

项目成果

Counting list matrix partitions of graphs

计算图的列表矩阵分区

• 发表时间: 2014
• 作者: Andreas Goebel; Leslie Ann Goldberg; Colin McQuillan; David Richerby;Tomoyuki Yamakami
• 通讯作者: Tomoyuki Yamakami

Counting list matrix partitions of graphs

计算图的列表矩阵分区

• 发表时间: 2015
• 影响因子: 1.6
• 作者: A. Goebel; L. A. Goldberg; C. McQuillan; D. Richerby;T. Yamakami
• 通讯作者: T. Yamakami

Interactive proofs with quantum finite automata

量子有限自动机的交互式证明

• DOI: 10.1016/j.tcs.2014.11.030
• 发表时间: 2015
• 影响因子: 1.1
• 作者: H. Nishimura;T. Yamakami
• 通讯作者: T. Yamakami

Not all multi-valued partial CFL functions are refined by single-valued functions (extended abstract)

并非所有多值部分 CFL 函数都由单值函数细化（扩展摘要）

• DOI: 10.1007/978-3-662-44602-7_12
• 发表时间: 2014
• 作者: T. Yamakami

研究成果に関するＷＥＢページ

有关研究结果的网页