限制树宽图上的有界聚类

摘要：

有界聚类问题源于IBM研究院开发的一个分布式流处理系统,即S系统.问题的输入是一个点赋权和边赋权的无向图,并指定若干个称为终端的顶点.称顶点集合的一个子集为一个子类.子类中所有顶点的权和加上该子类边界上所有边的权和称为该子类的费用.有界聚类问题是要得到所有顶点的一个聚类,要求每个子类的费用不超过给定预算B,每个子类至多包含一个终端,并使得所有子类的总费用最小.对于限制树宽图上的有界聚类问题,给出了拟多项式时间精确算法.利用取整的技巧对该算法进行修正,可在多项式时间之内得到(1+ε)一近似解,其中每个子类的费用不超过(1+ε)B,ε是任意小的正数.如果进一步要求每个子类恰好包含一个终端,则所给算法可在多项式时间之内得到(1+ε)-近似解,其中每个子类的费用不超过(2+ε)B.

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

所属期刊栏目：38

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金60970105;国家自然科学基金青年基金11161035;山东省信息产业发展专项资金项目2008X00039;山东省软科学研究计划2010RKGA1057,2011RKGBS040

在线出版日期：2012-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：241-244