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

加权3-Set Packing的改进算法 被引量：1

Improved Algorithms for Weighted 3-Set Packing
下载PDF
导出
摘要 Packing问题构成了一类重要的NP难问题.对于加权3-SetPacking问题,把问题转化成加权3-SetPacking Augmentation问题进行求解,即主要讨论如何从一个已知的最大加权k-packing求得一个权值最大的(k+1)-packing.通过对问题结构的分析,结合Color-Coding技术,首先给出了一种时间复杂度为O*(10.63k)的参数算法,极大地改进了目前文献中的最好结果O*(12.83k).通过对(k+1)-packing结构的进一步分析,利用集合划分技术将上述结果降到O*(7.563k). Packing problems form an important class of NP-hard problems. In order to solve the weighted 3-set packing problem, this paper converts the problem to the weighted 3-set packing augmentation problem, and mainly works on how to construct a maximum weighted （k＋1）-packing based on a maximum weighted k-packing. This paper gives a theoretical study on the structure of the problem and presents a deterministic algorithm of time O^＊（10.6^3k） with color-coding, which significantly improves the previous best result O^＊（12.8^3k）. After further analyzing the structure of the problem and based on the set dividing method, the above result can be further reduced to O^＊（7.56^3k）.
作者 冯启龙 王建新 陈建二
机构地区 中南大学信息科学与工程学院
出处 《软件学报》 EI CSCD 北大核心 2010年第5期886-898,共13页 Journal of Software
基金 国家自然科学基金(Nos.60433020 60773111) 国家重点基础研究发展计划(973)No.2008CB17107 新世纪优秀人才支持计划No.NCET-05-0683 长江学者和创新团队发展计划No.IRT0661~~
关键词 加权3-setpacking 加权3-setpacking augmentation color-coding weighted 3-set packing weighted 3-set packing augmentation color-coding
分类号 TP301 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献16

  • 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.

同被引文献15

  • 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.
  • 3Flum J, Grohe M. Parameterized complexity theory[M]. Springer-Verlag Berlin Heidelberg, 2006.
  • 4Curticapean R. Countingmatchingofsizekis # WE 13-hard[C]// Proceedings of the 40th International Colloquium on Automata, Languages and Programming(ICALP' 13). 2013 : 352-363.
  • 5Arvind 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.
  • 6Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NP-completeness[M]. W. H. Freeman, New York, 1979.
  • 7Wang 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.
  • 8Abu-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.
  • 9Dahllof V, Jonsson P. An algorithm for counting maximum weighted independent sets and its application [C]//Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA' 02). 2002 : 292-298.
  • 10Liu Yun-long, Chen Jian-er, Wang Jian-xln. On counting 3-D Matchings of size k [J].Algorithmica, 2009,54 : 530-543.

引证文献1

软件学报
2010年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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