Hypervelocity information extraction from huge informations

从海量信息中超高速信息提取

• 批准号: 21500014
• 负责人: ITO Hiro
• 金额: $ 2.75万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500014/
• 关键词: アルゴリズム理論; 定数時間アルゴリズム; グラフアルゴリズム; グラフ; ネットワーク; アルゴリズム; 定数時間; 乱択; マトロイド; ナップザック問題; オンラインアルゴリズム; ユニットディスクグラフ; FPT; 計算複雑さ; 下界値; 性質検査; 近似アルゴリズム

We investigated fast algorithms for treating big data, and lower bounds about them. Especially, algorithms that see only constant number of data of the given instance are mainly investigated. We obtained fast constant-time algorithms for approximating the size of the maximum independent set and the maximum matching of graphs, a testing outerplanarity of graphs, approximating the rank of sparsity matroids, and approximating the solution of the knapsack problem. And we presented new tools for showing linear lower bounds for testing algorithms. Moreover, we considered to parametrize unit disk graphs by the area, and gave some FPT algorithms and lower bounds on some problems on them.

我们研究了处理大数据的快速算法及其下限。特别是，主要研究仅查看给定实例的恒定数量数据的算法。我们获得了快速常数时间算法来近似最大独立集的大小和图的最大匹配、测试图的外平面性、近似稀疏拟阵的秩以及近似背包问题的解。我们还提出了新的工具来显示测试算法的线性下限。此外，我们考虑了按面积对单位圆盘图进行参数化，并给出了一些FPT算法和一些问题的下界。

项目成果

Query-number preserving reductions and linear lower bounds for testing

保留查询数减少和测试的线性下限

• 发表时间: 2010
• 期刊: IEICE Transactions
• 作者: J.Akiyama;H.Ito;M.Kobayashi;G.Nakamura;YOSHIDA Yuichi and ITO Hiro
• 通讯作者: YOSHIDA Yuichi and ITO Hiro

Complexity of the stamp folding problem, Proceedings of The 5th Annual International Conference on Combinatorial Optimization and Applications(COCOA 2011)

邮票折叠问题的复杂性，第五届组合优化与应用国际会议论文集（COCOA 2011）

• 发表时间: 2011
• 期刊: LNCS
• 作者: UMESATO Takuya;SAITOH Toshiki;UEHARA Ryuhei;and ITO Hiro
• 通讯作者: and ITO Hiro

定数時間アルゴリズムとその基本定理(前編)-密グラフモデルと正則性補題, ERATOセミナー

恒定时间算法及其基本定理（第 1 部分）- 密集图模型和正则引理，ERATO 研讨会

• 发表时间: 2011
• 作者: T. Ogiro;A. Alhazov;T. Tanizawa;K. Morita;伊藤大雄
• 通讯作者: 伊藤大雄

定数時間アルゴリズムとその基本定理(前編)---密グラフモデルと正則性補題

常数时间算法及其基本定理（第1部分）---稠密图模型和正则引理

• 发表时间: 2011
• 作者: A. Alhazov;K. Morita;伊藤大雄
• 通讯作者: 伊藤大雄

Constant-time algorithms for sparsity matroids

稀疏拟阵的恒定时间算法

• 发表时间: 2012
• 期刊: Proc. of The 39th International Colloquium on Automata, Language and Programming (ICALP 2012) (1), LNCS
• 作者: Hiro Ito Shin-ichi Tanigawa;Yuichi Yoshida
• 通讯作者: Yuichi Yoshida