著者

チャンドラバルン ハルダースソンマグナス

出版者

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

雑誌

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

巻号頁・発行日

vol.1995, no.32, pp.69-76, 1995-03-17

参考文献数

12

---

散乱問題は,点の集合を可能な限り互いに離して配置する問題である.この問題は,施設の位置の選定や経営決定学の分野に,多くの応用をもつ.現在までの重要な研究は,二つの特定の散乱の尺度に着目してきている.我々は,現実の問題に動機づけられ,いくつかの自然な遠隔の尺度を導入し,考察する.そして,自明でないパーフォマンスの境界をもつ,最初のアルゴリズムを示す.Dispersion problems involve arranging a set of points as far away from each other as possible. They have numerous applications in the location of facilities and in management decision science. Must work to date has focused on two particular measures of the dispersion. We study and introduce several natural measures of remoteness, motivated by real-life problems, and present the first algorithms with non-trivial performance bounds.