计算机科学 ›› 2016, Vol. 43 ›› Issue (9): 23-26.doi: 10.11896/j.issn.1002-137X.2016.09.004
刘运龙
LIU Yun-long
摘要： Set Packing参数化计数问题即在一个3-Set Packing实例中统计所有大小为k的不同packing的个数。首先证明了该问题的计算复杂性是#W[1]-难的,表明该问题不大可能存在固定参数可解的精确算法(除非#W[1]=FPT)。然后,通过拓展3-D Matching参数化计数问题的算法对3-Set Packing参数化计数问题提出了一个基于Monte-Carlo自适应覆盖算法和着色技术的随机近似算法。
| [1] McCartin C.Parameterized counting problems[C]∥Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science(MFCS’02).2002:556-567 [2] Flum J,Grohe M.The parameterized complexity of countingproblems[J].SIAM Journal on Computing,2004,33(4):892-922 [3] Zhang Chi-hao,Chen Yi-jia.Counting problems in parameterized complexity[J].TsingHua Science and Technology,2014,19(4):410-420 [4] Flum J, Grohe M.Parameterized complexity theory[M].Springer-Verlag Berlin Heidelberg,2006 [5] Curticapean R.Counting matching of size k is #W[1]-hard[C]∥Proceedings of the 40th International Colloquium on Automata,Languages and Programming(ICALP’13).2013:352-363 [6] Arvind V,Raman V.Approximation algorithms for some para-meterized counting problems[C]∥Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC’02).2002:453-464 [7] Garey M R,Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].W.H.Freeman,New York,1979 [8] Wang Jian-xin,Feng Qi-long.An O*(3.523k) parameterized algorithm for 3-Set Packing[C]∥Proceedings of the 5th International Conference on Theory and Applications of Models of Computation (TAMC’08).2008:82-93 [9] Abu-Khzam F N.A quadratic kernel for 3-Set Packing [C]∥Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC’09).2009:81-87 [10] Feng Qi-long,Wang Jian-xin,Chen Jian-er.Improved algorithms for weighted 3-Set Packing[J].Journal of Software,2010,21(5):886-898(in Chinese) 冯启龙,王建新,陈建二.加权3-Set Packing 的改进算法[J].软件学报,2010,21(5):886-898 [11] Li Shao-hua,Feng Qi-long,Wang Jian-xin,et al.Kernelizaitonfor weighted 3-Set Packing problem[J].Journal of Computer Research and Development,2012,49(8):1781-1786(in Chinese) 李绍华,冯启龙,王建新,等.加权3-Set Packing 问题的核心化[J].计算机研究与发展,2012,49(8):1781-1786 [12] Dahllof V,Jonsson P.An algorithm for counting maximumweighted independent sets and its application [C]∥Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA’02).2002:292-298 [13] Liu Yun-long, Chen Jian-er, Wang Jian-xin.On counting 3-DMatchings of size k [J].Algorithmica,2009,54:530-543 [14] Chen Jian-er,Lu Song-jian,Sze S H,et al.Improved algorithms for path,matching,and packing problems[C]∥Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’07).2007:298-307 [15] Karp R M,Luby M,Madras N.Monte-Carlo approximation algorithms for enumeration problems [J].Journal of Algorithms,1989,10:429-448 [16] Liu Yun-long,Wang Jian-xin.On counting parameterized matching and packing [C]∥Proceedings of the 10th International Frontiers of Algorithmics Workshop (FAW’16).2016:125-134 |
| No related articles found! |
|
||
首页