著者

上土井 陽子 若林 真一 吉田 典可

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.48, pp.17-22, 1995-11-17

参考文献数

5

---

グラフの最小コストk分割問題は枝に正の重みを持つ無向グラフG=(V,E)の節点集合Vを互いに非連結なk個の節点集合に分割する最小コスト分割を求める問題である.この問題は巡回セールスマン問題やVLSI設計で用いられるクラスタリング問題等の組合せ問題の定式化において用いられる重要な組合せ問題の一つである.Goldschmidtらはグラフの最小コストk分割問題に対し,n=|V|とするとき,O(n^<k^2>の計算時間のアルゴリズムを提案している.本稿では最小コストk分割問題に対する多項式計算時間のアルゴリズムを提案する.提案アルゴリズムでは最大流-最小コストカットアルゴリズムをO(n^<k-1>)回適用する.

著者

齋藤 忠志 大谷 純 上土井 陽子 吉田 典可

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.99, no.724, pp.25-32, 2000-03-22

被引用文献数

2

---

オンラインに逐次発生するジョブをネットワーク上のどの資源に割り当てると効率良い処理が行えるかを考える負荷分散問題であるオンラインスケジューリング問題について考察する。Aspnesらにより8-competitive ratioをもつオンラインアルゴリズムSLOWFITが提案されている。理論的にはSLOWFITは効率の良い手法であるが、実験的には貪欲法GREEDYが良質な解を得ている。本稿ではSLOWFITに導入されているステージの概念とダブリング・トリックに注目して、新しい2つのオンラインスケジューリングアルゴリズムを提案する。シミュレーション実験により、提案手法の有効性を検証する。

著者

中村 朋健 上土井 陽子 若林 真一 吉田 典可

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.468, pp.31-37, 2003-11-18

---

近年,巨大なデータベースが世界中の至るところで作成され,そこから役立つ情報を抽出するデータマイニング技術が実用に供されるようになった.規則性の見え難いデータベースからデータベースの性質を見つけ出す場合に,類似したデータ要素を集めるクラスタリングは有効である.特に,大規模な高次元データベースからの知識抽出において,実時間性や即時応答性が要求される分野ではメモリ使用量が少なく高速なクラスタリングが要求される.本稿では,実社会データを想定した高次元かつ疎なデータ空間を対象に,処理時間とデータ要素数が線形関係であるクラスタリング手法を提案する.また,数次元の入力データに対して提案手法を適用し,与えた評価基準により提案手法を評価する.提案手法では入力のデータ空間を階層的に不均一なサイズのセルに区切り,パラメータにより密と判断された隣接したセルを結合させることで,類似したデータ要素を集めるアルゴリズムである.