• 人工智能 •

### 限制树宽图上的有界聚类

1. (山东工商学院计算机科学与技术学院　烟台264005)(山东工商学院研究生处　烟台264005)
• 出版日期:2018-12-01 发布日期:2018-12-01

### Bounded Clustering on Bounded Tree-width Graphs

• Online:2018-12-01 Published:2018-12-01

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.

 No related articles found!
Viewed
Full text

Abstract

Cited

Shared
Discussed