文件大小：1.05M
摘要：给定正整数k和非负整数l以及度量空间中的一组设施和着色用户， 着色（k，l）-中值问题旨在选取不超过k个开设设施、在用户集合中移除最多l个异常点并为剩余的每个用户分配一个开设设施， 使得颜色相同的用户对应不同设施， 且用户与对应设施之间的距离之和最小。本文利用新的随机采样方法确定用来选取开设设施的引导点集合， 并围绕引导点为问题实例构造小规模候选解集合。本文基于此为着色（k，l）-中值问题提出了时间复杂度为(（k+l）ε-1)o（k）no（1）的（3+ε）-近似算法， 其中，n为问题实例中设施与用户数量之和。这是关于着色（k，l）-中值问题的第一个具有性能保证的求解算法。该算法与此前人们在不考虑着色约束的情况下提出的固定参数近似算法有相同的时间复杂度和近似比。
文章目录
1 引言
2 相关工作
3 基本定义及引理
4 算法概述
4.1 引导点选取方法
4.2 基于引导点集合的求解算法
5 引导点挖掘
5.1 随机采样算法
5.2 算法分析
6 基于引导点的候选解构造算法
6.1 开设设施选取
6.2 候选解构造
7 着色■-中值问题的求解算法
8 总结
