A study on approximation of isomorphism problems

同构问题的近似研究

• 批准号: 24800082
• 负责人: YOSHIDA Yuichi
• 金额: $ 1.91万
• 依托单位: National Institute of Informatics
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Research Activity Start-up
• 财政年份: 2012
• 资助国家: 日本
• 起止时间: 2012-08-31 至 2014-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-24800082/
• 关键词: 同型性判定問題; 性質検査; 近似アルゴリズム; 制約充足問題; 割り当て問題; 同型性判定; スペクトル解析; 国際情報交換(アメリカ合衆国)

The problems of deciding whether given two objects, such as graphs and functions, are "essentially" the same or not is called the isomorphism problems. The isomorphism problems have been studied intensively, but whether they are tractable in polynomial time remains open. In this project, I considered a variant of the isomorphism problems in which we compute how close two objects are instead of whether they are the same or not. I obtained several new results about this variant under the paradigms called "property testing" and "approximation algorithms".

判定给定的两个对象（如图和函数）是否“本质”相同的问题称为同构问题。同构问题已被深入研究，但它们是否在多项式时间内易于处理仍然是开放的。在这个项目中，我考虑了同构问题的一个变体，其中我们计算两个对象有多接近，而不是它们是否相同。我得到了几个新的结果，这个变种下的范式称为“属性测试”和“近似算法”。

项目成果

A Characterization of Locally Testable Affine-Invariant Properties through Decomposition Theorems

通过分解定理表征局部可测试的仿射不变性质

• 发表时间: 2013
• 作者: Hashizume;K.;Phung-Duc;T.;Kasahara;S.;and Takahashi;Y.;苅谷康太;吉田悠一
• 通讯作者: 吉田悠一

Testing Supermodular-cut Condition

测试超模切割条件

• 发表时间: 2013
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Shin-ichi Tanigawa;Yuichi Yoshida
• 通讯作者: Yuichi Yoshida

Semi-strong coloring of intersecting hypergraphs

相交超图的半强着色

• 发表时间: 2013
• 期刊: Combinatorics Probability and Computing
• 影响因子: 0.9
• 作者: Eric Blais;Amit Weinstein;Yuichi Yoshida
• 通讯作者: Yuichi Yoshida

Robust approximation of CSPs : Universal algebra meets optimization

CSP 的鲁棒逼近：通用代数遇上优化

• 发表时间: 2013
• 作者: A. Fleurence;Y. Yoshida;C.-C. Lee;T. Ozaki;Y. Yamada-Takamura;and Y. Hasegawa;Yuichi Yoshida
• 通讯作者: Yuichi Yoshida

制約充足問題に対するサブリニアタイムアルゴリズム

约束满足问题的次线性时间算法

• 发表时间: 2012
• 作者: 石井佑弥,里園翔太,上ノ瀬亮平,福田光男;Yuichi Yoshida
• 通讯作者: Yuichi Yoshida