一类一维在线单位聚类问题的随机近似算法

Randomized approximation algorithms for a class of one-dimensional online unit clustering problem

在给定的度量空间中,单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题,其在线版本为:给定一个度量空间,其中的n个点会一个接一个的到达任何可能的位置,在点到达的时候必须给该点分配一个单位聚类,而此时未来点的相关信息都是未知的,问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题:在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理,接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法,最后证明了这个组合随机算法的期望竞争比不超过1.5。

In a given metric space,the unit clustering problem is to find a minimum number of unit balls to cover all the given points.It is a well known combinatorial optimization problem and the online version is:Given a set of n points in a given metric space,which arrive one by one at any locations,the point should be assigned to a unit cluster at the time of its arrival without any future information,the goal is to minimize the number of used clusters.In this paper,we consider a class of online unit clustering problem in one dimension with the assumption that the distance between any two adjacent clusters in the offline optimal solution is greater than 0.5.We first present two online algorithms with some lemmas,and then present a combined randomized algorithm which run the two online algorithms with a probability 0.5.We show that the expected competitive ratio of the combined randomized algorithm is at most 1.5.