4H-02
直線上のmin-sum r-cellular Clustering
○小川航平，中野眞一，宮田洋行，赤木俊裕（群馬大）
様々な制約のもとで, 指定したコストが最適になるように, 施設を配置する問題を施設配置問題という. 様々な施設配置問題が研究されてきた. 本文は, 最近提案された2つの施設配置問題を扱う. 距離空間に点集合Pが与えられたとき, これらを, それぞれがr点以上からなる部分集合(クラスタ) に, 指定したコストが最小になるように分割する問題を, 一般に, r-gather問題と呼ぶ. これらの問題は一般にNP完全である. 本文は, 直線上に点集合Pが与えられたとき, 2つのr-gather問題を解くアルゴリズムを与える.
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会