限制树宽图上的有界聚类

摘要

The bounded clustering problem is motivated by system S,a distributed stream processing system developed at IBM Research. Input to the problem is an undirected graph with vertex and edge weights and a subset of vertices called terminals. A cluster is a subset of the vertices. The cost of a cluster is defined as the total vertex weight in the cluster plus the total edge weight at the boundary of the cluster. The goal of the problem is to partition the vertices into clusters of cost at most a given budget B such that each cluster contains at most one terminal and the total cost of the clusters is minimized. For the problem on graphs of bounded tree-width,a pseudo-polynomial time exact algorithm was presented,which can be modified via rounding to yield a (1+e)-approximation in polynomial time violating the given budget by a 1+e factor, where eX) can be made arbitrarily small. For a variant of the problem on graphs of bounded treewidth where each cluster contains exactly one terminal, a polynomial time algorithm was presented that yields a (l+e)-approximation violating the budget by a 2+ε factor.%有界聚类问题源于IBM研究院开发的一个分布式流处理系统,即S系统.问题的输入是一个点赋权和边赋权的无向图,并指定若干个称为终端的顶点.称顶点集合的一个子集为一个子类.子类中所有顶点的权和加上该子类边界上所有边的权和称为该子类的费用.有界聚类问题是要得到所有顶点的一个聚类,要求每个子类的费用不超过给定预算B,每个子类至多包含一个终端,并使得所有子类的总费用最小.对于限制树宽图上的有界聚类问题,给出了拟多项式时间精确算法.利用取整的技巧对该算法进行修正,可在多项式时间之内得到(1+ε)一近似解,其中每个子类的费用不超过(1+ε)B,ε是任意小的正数.如果进一步要求每个子类恰好包含一个终端,则所给算法可在多项式时间之内得到(1+ε)-近似解,其中每个子类的费用不超过(2+ε)B.