k-supplier问题的贪婪近似算法

Greedy approximation algorithm for the k-supplier problem

给定无向完全图G=(V,E)和正整数k,图G的顶点集V被划分为子集F和子集D=V-F.k-supplier问题主要研究如何寻找F中顶点数不多于k的子集S,使得S中的顶点到D中顶点的最大距离最小.研究了k-supplier问题,得到了一个近似比为3的多项式时间贪婪近似算法,并通过实例验证了该算法的有效性.

An undirected complete graph G=(V,E) and a positive integer k were given.The vertex set V of G was partitioned into subset F and subset D=V-F.The k-supplier problem mainly considers how to find a subset S■F,with the number of vertices not greater than k,such that the maximum distance from the vertices in S to the vertices in D is minimized.Now,we studied the k-supplier problem and we proposed a polynomial time 3-approximation greedy algorithm.We also verify the efficiency of this algorithm by giving an example.