Max-Min Dispersion on a Line
Max-Min Dispersion on a Line
复制标题
线上的最大-最小离散度
DOI：
10.1007/s10878-020-00549-5
复制
发表时间：
2020
影响因子：
1
通讯作者：
Tetsuya Araki and Shin-ichi Nakano
中科院分区：
文献类型：
--
作者：
Kong Gil-Tak;Katsunobu Imai;Toru Nakanishi;Tetsuya Araki and Shin-ichi Nakano
给定一个可以放置设施的集合Pofnlocations和一个整数k，我们希望将kfacilities放置在某些位置上，以便最大化指定的目标函数。这个问题被称为k-色散问题。例如，希望消防部门彼此远离。本文给出了一个简单的时间算法来求解最大-最小形式的k-色散问题，如果P是直线上的一组点。如果是一个常数，那么这是一个O（n）时间算法。这是第一个O（n）时间算法来解决最大的mink分散问题的“unsorted”点的一组线。如果P是一条直线上的一组有序点，输入是一个数组，数组中的点的坐标按有序顺序存储，那么只要对上述算法稍加修改，就能及时解决离散问题。这是第一个次线性时间算法来解决的最大-Mink-分散问题的一组排序点的线。
Given a setPofnlocations on which facilities can be placed and an integerk, we want to placekfacilities on some locations so that a designated objective function is maximized. The problem is called thek-dispersion problem. For instance it is desirable to locate fire departments far away each other. In this paper we give a simpletime algorithm to solve the max–min version of thek-dispersion problem ifPis a set of points on a line. Ifkis a constant then this is anO(n) time algorithm. This is the firstO(n) time algorithm to solve the max–mink-dispersion problem for the set of “unsorted” points on a line. IfPis a set of sorted points on a line, and the input is given as an array in which the coordinates of the points are stored in the sorted order, then by slightly modifying the algorithm above one can solve the dispersion problem intime. This is the first sublinear time algorithm to solve the max–mink-dispersion problem for the set of sorted points on a line.