期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

3-Set Packing参数化计数问题的复杂性及近似算法

Research on Complexity and Approximation Algorithm for Counting 3-Set Packings of Size k
下载PDF
导出
摘要 3-Set Packing参数化计数问题即在一个3-Set Packing实例中统计所有大小为k的不同packing的个数。首先证明了该问题的计算复杂性是#W[1]-难的,表明该问题不大可能存在固定参数可解的精确算法(除非#W[1]=FPT)。然后,通过拓展3-D Matching参数化计数问题的算法对3-Set Packing参数化计数问题提出了一个基于Monte-Carlo自适应覆盖算法和着色技术的随机近似算法。 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[l]-hard, which indicates that there exists no efficient fixed- parameter tractable algorithm for it（unless # W[l] = 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 algo- rithm is heavily based on the Monte-Carlo self-adjusting coverage algorithm and the recent improved color-coding tech- niques.
作者 刘运龙
机构地区 湖南师范大学数学与计算机科学学院高性能计算与随机信息处理省部共建教育部重点实验室
出处 《计算机科学》 CSCD 北大核心 2016年第9期23-26,共4页 Computer Science
关键词 3-Set PACKING 计数 复杂性 近似算法 3-Set Packing, Counting, Complexity, Approximation algorithm
分类号 TP301 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献16

  • 1McCartin C. Parameterized counting problems[C]//Proceedings of the 27th International Symposium on Mathematical Founda- tions of Computer Science(MFCS'02). 2002:556-567.
  • 2Flum J, Grohe M. The parameterized complexity of counting problems[J]. SIAM Journal on Computing, 2004, 33 (4) : 892- 922.
  • 3Chihao Zhang,Yijia Chen.Counting Problems in Parameterized Complexity[J].Tsinghua Science and Technology,2014,19(4):410-420. 被引量：1
  • 4Flum J, Grohe M. Parameterized complexity theory[M]. Springer-Verlag Berlin Heidelberg, 2006.
  • 5Curticapean R. Countingmatchingofsizekis # WE 13-hard[C]// Proceedings of the 40th International Colloquium on Automata, Languages and Programming(ICALP' 13). 2013 : 352-363.
  • 6Arvind V,Raman V. Approximation algorithms for some para- meterized counting problems[C]//Proceedings of the 13th In- ternational Symposium on Algorithms and Computation (I- SAAC'02). 2002: 453-464.
  • 7Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NP-completeness[M]. W. H. Freeman, New York, 1979.
  • 8Wang Jian-xin, Feng Qi-long. An O ** (3. 523k ) parameterized al- gorithm for 3-Sct Packing[C]//Proceedings of the 5th Interna- tional Conference on Theory and Applications of Models of Computation (TAMC'08). 2008 : 82-93.
  • 9Abu-Khzam F N. A quadratic kernel for 3-Set Packing [C]// Proceedings of the 6th Annual Conference on Theory and Appli- cations of Models of Computation (TAMC'09). 2009:81-87.
  • 10冯启龙,王建新,陈建二.加权3-Set Packing的改进算法[J].软件学报,2010,21(5):886-898. 被引量：1

二级参考文献71

  • 1Chen JE,Liu Y,Lu SJ,Sze SH.Greedy localization and color-coding:Improved matching and packing algorithms.In:Bodlaender H,et al.,eds.Proc.of the 2nd Int'l Workshop on Parameterized and Exact Computation.LNCS 4169,Berlin:Springer-Verlag,2006.84-95.
  • 2Chandra B,Halldorsson M.Greedy local improvement and weighted set packing approximation.Journal of Algorithms,2001,39(2):223-240.[doi:10.1006/jagm.2000.1155].
  • 3Downey R,Fellows M.Parameterized Complexity.New York:Springer-Verlag,1999.215-220.
  • 4Arkin E,Hassin R.On local search for weighted k-set packing.In:Burkard R,et al.,eds.Proc.of the European Symp.on Algorithms.Berlin:Springer-Verlag,1997.13-22.
  • 5Bafna V,Narayan B,Ravi R.Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles).Discrete Applied Mathematics,1996,71(1-3):41-53.[doi:10.1016/S0166-218X(96)00063-7].
  • 6Berman P.A d/2 approximation for maximum weight independent set in d-claw free graphs.In:Halldórsson M,ed.Proc.of the 7th Scandinavian Workshop on Algorithm Theory.LNCS 1851,Berlin:Springer-Verlag,2000.214-219.
  • 7Liu YL,Chen JE,Wang JX.Parameterized algorithms for weighted matching and packing problems.In:Cai JY,et al.,eds.Proc.of the 4th Annual Conf.on Theory and Applications of Models of Computation.LNCS 4484,Berlin:Springer-Verlag,2007.692-702.
  • 8Jia WJ,Zhang CL,Chen JE.An efficient parameterized algorithm for m-set packing.Journal of Algorithms,2004,50(1):106-117.[doi:10.1016/j.jalgor.2003.07.001].
  • 9Koutis I.A faster parameterized algorithm for set packing.Information Processing Letters,2005,94(1):7-9.[doi:10.1016/ j.ipl.2004.12.005].
  • 10Fellows MR,Knauer C,Nishimura N,Ragde P,Rosamond F,Stege U,Thilikos D,Whitesides S.Faster fixed-parameter tractable algorithms for matching and packing problems.In:Albers S,et al.,eds.Proc.of the European Symp.on Algorithms.LNCS 3221,Berlin:Springer-Verlag,2004.311-322.
计算机科学
2016年 第9期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部