Exact Algorithms for the Max-Min Dispersion Problem

• Akagi, Toshihiro

• Araki, Tetsuya

• Horiyama, Takashi

• Nakano, Shin-Ichi

• Okamoto, Yoshio

• Otachi, Yota

• Saitoh, Toshiki

• Uehara, Ryuhei

• Uno, Takeaki

• Wasa, Kunihiro

抄録

Given a set P of n elements, and a function d that assigns a non-negative real number d(p, q) for each pair of elements p,q∈P, we want to find a subset S⊆P with |S|=k such that cost(S)=min{d(p,q)∣p,q∈S} is maximized. This is the max-min k-dispersion problem. In this paper, exact algorithms for the max-min k-dispersion problem are studied. We first show the max-min k-dispersion problem can be solved in O(n^<ωk>/^3logn) time. Then, we show two special cases in which we can solve the problem quickly.

Frontiers in Algorithmics,12th International Workshop, FAW 2018, Guangzhou, China, May 8-10, 2018, Proceedings

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/15857

収録刊行物

• Lecture Notes in Computer Science

  Lecture Notes in Computer Science 10823 263-272, 2018-03-21

  Springer

キーワード

• dispersion problem
• polynomial time algorithm

詳細情報

• CRID: 1050001202672831744
• NII論文ID: 120006648104
• ISSN: 03029743
• ISSN: 16113349
• DOI: 10.1007/978-3-319-78455-7_20
• Web Site: http://hdl.handle.net/10119/15857
• Web Site: https://link.springer.com/content/pdf/10.1007/978-3-319-78455-7_20
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN