| 3-Set Packing参数化计数问题的复杂性及近似算法 |
| |
| 引用本文： | 刘运龙. 3-Set Packing参数化计数问题的复杂性及近似算法[J]. 计算机科学, 2016, 43(9): 23-26 |
| |
| 作者姓名： | 刘运龙 |
| |
| 作者单位： | 湖南师范大学数学与计算机科学学院高性能计算与随机信息处理省部共建教育部重点实验室 长沙410081 |
| |
| 摘 要： | Set Packing参数化计数问题即在一个3-Set Packing实例中统计所有大小为k的不同packing的个数。首先证明了该问题的计算复杂性是#W[1]-难的,表明该问题不大可能存在固定参数可解的精确算法(除非#W[1]=FPT)。然后,通过拓展3-D Matching参数化计数问题的算法对3-Set Packing参数化计数问题提出了一个基于Monte-Carlo自适应覆盖算法和着色技术的随机近似算法。
|
| 关 键 词： | 3-Set Packing 计数 复杂性 近似算法 |
| 收稿时间： | 2015-12-23 |
| 修稿时间： | 2016-01-24 |
Research on Complexity and Approximation Algorithm for Counting 3-Set Packings of Size k |
| |
| LIU Yun-long. Research on Complexity and Approximation Algorithm for Counting 3-Set Packings of Size k[J]. Computer Science, 2016, 43(9): 23-26 |
| |
| Authors: | LIU Yun-long |
| |
| Affiliation: | Key Laboratory of High Performance Computing and Stochastic Information Processing,Ministry of Education of China, College of Mathematics and Computer Science, Hunan Normal University,Changsha 410081,China |
| |
| Abstract: | Counting 3-Set Packings of size k is to count distinct packings of size k in a given instance of 3-Set Packing.We first showed that the complexity of this problem is #W[1]-hard,which indicates that there exists no efficient fixed-parameter tractable algorithm for it(unless #W[1]=FPT).Subsequently,by extending the algorithm for counting 3-D Matchings of size k,we obtained a generalized approximation algorithm for counting 3-Set Packings of size k.This algorithm is heavily based on the Monte-Carlo self-adjusting coverage algorithm and the recent improved color-coding techniques. |
| |
| Keywords: | 3-Set Packing Counting Complexity Approximation algorithm |
|
| 点击此处可从《计算机科学》浏览原始摘要信息 |
|
点击此处可从《计算机科学》下载全文 |
