| 树上推广的Multicut问题的近似算法 |
| |
| 引用本文： | 张鹏.树上推广的Multicut问题的近似算法[J].计算机研究与发展,2008,45(7). |
| |
| 作者姓名： | 张鹏 |
| |
| 作者单位： | 山东大学计算机科学与技术学院,济南,250101 |
| |
| 基金项目： | 国家自然科学基金，国家自然科学基金 |
| |
| 摘 要： | 给定边上有费用的树T,终端集合族X={S1,S2,…,Sl},推广的Multicut问题询问费用最小边集,使得在树上删除边集中的边能够断开每一个终端集,推广的Multicut问题有其独立的研究意义因为该问题分别是经典的Multicut问题和Multiway Cut问题的自然推广,同时也是推广的SteinForest问题的对偶问题,树上推广的Multicut问题的完全版本可以归约到树上经典的Multicut问题似求解,对于该问题的Prize-collecting版本,给出了原始-对偶的3倍近似算法,对于该问题的k版本通过非一致的途径给出了近似比为min{2(l-k 1),k}的近似算法,以及找到了该问题的k版本与k-稠密子图问题之间的一个有趣的联系,从而证明了将k版本的树上推广的Multicut问题近似O(n1/6-g)以内是困难的(对某个小的常数ε>0).
|
| 关 键 词： | 树 线性规划 近似算法 组合优化 |
Approximation Algorithms for Generalized Multicut in Trees |
| |
| Zhang Peng.Approximation Algorithms for Generalized Multicut in Trees[J].Journal of Computer Research and Development,2008,45(7). |
| |
| Authors: | Zhang Peng |
| |
| Affiliation: | Zhang Peng(School of Computer Science , Technology,Sh,ong University,Jinan 250101) |
| |
| Abstract: | |
| |
| Keywords: | Multicut |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
