Max-Min 3-Dispersion Problems

被引：0

作者：

Horiyama, Takashi ^{[1
]}

Nakano, Shin-ichi ^{[2
]}

Saitoh, Toshiki ^{[3
]}

Suetsugu, Koki ^{[4
]}

Suzuki, Akira ^{[6
]}

Uehara, Ryuhei ^{[7
]}

Uno, Takeaki ^{[5
]}

Wasa, Kunihiro ^{[8
]}

机构：

[1] Hokkaido Univ, Sapporo, Hokkaido 0600814, Japan

[2] Gunma Univ, Dept Comp Sci, Fac Engn, Kiryu, Gumma 3768515, Japan

[3] Kyushu Inst Technol, Iizuka, Fukuoka 8208502, Japan

[4] Natl Inst Informat, Takeaki Uno Lab, Tokyo 1018430, Japan

[5] Natl Inst Informat, Tokyo 1018430, Japan

[6] Tohoku Univ, Grad Sch Informat Sci, Sendai, Miyagi 9808579, Japan

[7] JAIST, Sch Informat Sci, Nomi 9231292, Japan

[8] Toyohashi Univ Technol, Toyohashi, Aichi 4418580, Japan

来源：

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2021年 / E104A卷 / 09期

关键词：

algorithms; dispersion problem; facility location; APPROXIMATION ALGORITHMS; DISPERSION;

D O I：

10.1587/transfun.2020DMP0003

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper, we consider the 3-dispersion problem when P is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the L-infinity metric, and an O(n) time algorithm to solve the 3-dispersion problem in the L-1 metric. Also, we give an O(n(2) log n) time algorithm to solve the 3-dispersion problem in the L-2 metric.

引用

页码：1101 / 1107

页数：7

共 22 条

[1] Efficient algorithms for geometric optimization [J].

Agarwal, PK ;

Sharir, M .

ACM COMPUTING SURVEYS, 1998, 30 (04) :412-458

[2]

Akagi T., 2016, IPSJ SIG Technical Reports, 2016-AL-158-3

[3] Exact Algorithms for the Max-Min Dispersion Problem [J].

Akagi, Toshihiro ;

Araki, Tetsuya ;

Horiyama, Takashi ;

Nakano, Shin-ichi ;

Okamoto, Yoshio ;

Otachi, Yota ;

Saitoh, Toshiki ;

Uehara, Ryuhei ;

Uno, Takeaki ;

Wasa, Kunihiro .

FRONTIERS IN ALGORITHMICS (FAW 2018), 2018, 10823 :263-272

[4] Max-Min Dispersion on a Line [J].

Araki, Tetsuya ;

Nakano, Shin-ichi .

COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2018), 2018, 11346 :672-678

[5]

Baur C., 1998, Approximation Algorithms for Combinatorial Optimization. International Workshop APPROX'98. Proceedings, P63, DOI 10.1007/BFb0053964

[6] An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs [J].

Birnbaum, Benjamin ;

Goldman, Kenneth J. .

ALGORITHMICA, 2009, 55 (01) :42-59

[7]

Cevallos A, 2017, PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P130

[8] Approximation algorithms for dispersion problems [J].

Chandra, B ;

Halldórsson, MM .

JOURNAL OF ALGORITHMS, 2001, 38 (02) :438-465

[9]

Drezner Z., 1995, Facility location: a survey of applications and methods

[10]

Drezner Z., 2004, FACILITY LOCATION AP

← 1 2 3 →