最小切割代价的限权树分割优化算法

摘要

研究一个在并行与分布式计算环境下兴起的树分割问题:给定一个节点和边均带权值的树T,通过切割树的边,将该树T分割成节点不相邻的子树,使得所有子树的节点权值之和不超过一个给定的上限K,并且使得被割边的权值之和最小.提出了一个能在多项式时间内完成的快速优化算法,包括一个基本的自底向上的结构及其动态规划方案和两个能大量节省计算空间的剪枝方案.实验表明,该算法在性能上相比其他同类算法要快十倍甚至数百倍,因而该算法能更好地应用于大规模并行任务调度的优化.