关键词: 近似算法，流处理，有界聚类，限制树宽图，动态规划

Abstract: 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+s)-approximation in polynomial time violating the given budget by a l+s factor,where e}0 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(less)-approximation violating the budget by a 2}s factor.

Key words: Approximation algorithms, Stream processing, Bounded clustering, Bounded trecwidth graphs, Dynamic