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算法和一些问题的下界。

项目成果

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

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

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

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

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

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

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

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

KASAHARA Shoji, and KAWAHARA Jun, An online algorithm optimally self-tuning to congestion for power management problems, Proceedings of the 9th Workshop on Approximation and Online Algorithms(WAOA 2011)

KASAHARA Shoji 和 KAWAHARA Jun，一种针对电源管理问题的拥塞优化自调整的在线算法，第九届近似和在线算法研讨会论文集（WAOA 2011）

• 发表时间: 2012
• 期刊: LNCS
• 作者: Wolfgang BEIN;HATTA Naoki;Nelson HERNANDEZ-CONS;ITO Hiro
• 通讯作者: ITO Hiro