限制树宽图上的有界聚类

• 作者: 周彤 李曙光
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 近似算法 流处理 有界聚类 限制树宽图 动态规划
• 年，卷（期）: 2011,（11）
• 所属期刊栏目: 人工智能
• 页码范围: 241-244
• 分类号: TP301
• 字数: 5696字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2011.11.056

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周彤	山东工商学院研究生处	7	35	4.0	5.0
2	李曙光	山东工商学院计算机科学与技术学院	4	2	1.0	1.0