计算机科学 ›› 2016, Vol. 43 ›› Issue (8): 7-12.doi: 10.11896/j.issn.1002-137X.2016.08.002

• 目次 • 上一篇    下一篇

难解问题的固定参数近似算法研究进展

刘运龙,崔梦天   

  1. 湖南师范大学数学与计算机科学学院高性能计算与随机信息处理省部共建教育部重点实验室 长沙410081,西南民族大学计算机科学与技术学院 成都610041
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金项目(61572190,61379019),四川省科技计划项目(2015JY002)资助

Advances in Fixed-parameter Tractable Approximation Algorithms for NP-hard Problems

LIU Yun-long and CUI Meng-tian   

  • Online:2018-12-01 Published:2018-12-01

摘要: 固定参数近似算法采用参数计算方法寻求问题的近似解,是实际中处理难解问题的一种新的有效手段。根据难解问题的参数计算复杂性类别,综述了固定参数可解问题、参数计算复杂性未定问题和W[t]-难问题(t≥1)固定参数近似算法近年来的研究进展。对于上述每一类问题,分别归纳了当前的主要研究结果,分析了其中的主要算法设计技术并探讨了有待研究的相关问题。

关键词: 固定参数近似算法,W[t]-难,分支限界技术

Abstract: Fixed-parameter tractable approximation algorithm produces the approximation solution by using the approach of parameterized computation,which becomes one of the practical approaches to deal with NP-hard problems.In this paper,we investigated the fixed-parameter tractable approximation algorithms for various NP-hard problems according to their parameterized computational complexity.More specifically,we gave a survey on the fixed-parameter tractable approximation algorithms for the fixed-parameter tractable problems,the problems with unknown parameteri-zed computational complexity,and the W[t]-hard problems (t≥1) respectively.For each kind of problems,we summarized typical examples with their results obtained in recent years,analyzed the main techniques employed in the algorithms and discussed some issues to be further studied.

Key words: Fixed-parameter tractable approximation algorithm,W[t]-hard,Branching and searching

[1] Hochbaum D S.Approximation algorithms for NP-hard problems [M].PWS Publishing Company,Boston,MA,1997
[2] Cygan M,Kowalik L,Pilipczuk M,et al.Exponential-time approximation of hard problems [EB/OL].http://arxiv.org/abs/0810.4934v1
[3] Escoffier B,Paschos V T,Tourniaire E.Moderately exponential time and fixed parameter approximation algorithms [J].Optimization,2013,62(8):1019-1036
[4] Downey R G,Fellows M R.Parameterized Complexity [M].Springer,New York,1999
[5] Downey R G,Fellows M R,McCartin C.Parameterized approximation algorithms [C]∥Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC’06).2006:121-129
[6] Chen Y,Grohe M,Grüber M.On parameterized approximability [C]∥Proceedings of the 2nd International Workshop on Parame-terized and Exact Computation (IWPEC’06).2006:109-120
[7] Cai L,Huang X.Fixed-parameter approximation:conceptualframework and approximability results [C]∥Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC’06).2006:96-108
[8] Marx D.Parameterized complexity and approximation algo-rithms [J].The Computer Journal,2008,51(1):60-78
[9] Grohe M,Grüber M.Parameterized approximability of the disjoint cycle problem [C]∥Proceedings of the 34th International Colloquium on Automata,Languages and Programming (ICALP’07,Track A).2007:363-374
[10] Brankovic L,Fernau H.Combining two worlds:parameterised approximation for vertex cover [C]∥Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC’10).2010:390-402
[11] Brankovic L,Fernau H.Parameterized approximation algorithms for hitting set [C]∥Proceedings of the 9th International Workshop on Approximation and Online Algorithms (WAOA’11).2011:63-76
[12] Fellows M R,Kulik A,Rosamond F,et al.Parameterized approximation via fidelity preserving transformations [C]∥Proceedings of the 39th International Colloquium on Automata,Languages and Programming (ICALP’12).2012:351-362
[13] Kolay S,Misra P,Ramanujan M S,et al.Parameterized approximations via d-skew-symmetric multicut [C]∥Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS’14).2014:457-468
[14] Escoffier B,Monnot J,Paschos V T,et al.New results on polynomial inapproximability and fixed parameter approximability of edge dominating set [C]∥Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC’12).2012:25-36
[15] Bar-Yehuda R.One for the price of two:a unified approach for approximating covering problems[J].Algorithmica,2000,27:131-144
[16] Chen J,Kanj I A,Jia W.Vertex cover:further observations and further improvements [J].Journal Algorithms,2001,41:280-301
[17] Gaspers S,Ordyniak S,Ramanujan M S,et al.Backdoors to q-Horn [C]∥Proceedings of the 30th Symposium on Theoretical Aspects of Computer Science (STACS’13).2013:67-79
[18] Ford Jr L R,Fulkerson D R.Maximal flow through a network [J].Canadian Journal of Mathematics,1956,8:399-404
[19] Kociumaka T,Pilipczuk M.Faster deterministic feedback vertex set [J].Information Processing Letters,2014,114(10):556-560
[20] Liu Yun-long,Wang Jian-xin,Xu Chao,et al.An efficientbranching strategy based on structural relationship among multiple forbidden induced subgraphs [J].Journal of Combinatorial Optimization,2015,29(1):257-275
[21] Liu Yun-long,Wang Jian-xin,You Jie,et al.Edge deletion problems:branching facilitated by modular decomposition [J].Theoretical Computer Science,2015,573:63-70
[22] Downey R G,Fellows M R.Fundamentals of ParameterizedComplexity [M].Springer,2013
[23] Gaspers S,Szeider S.Backdoors to acyclic SAT [C]∥Procee-dings of the 39th International Colloquium on Automata,Languages and Programming (ICALP’12).2012:363-374
[24] Gaspers S,Szeider S.Strong backdoors to nested satisfiability [C]∥Proceedings of the 15th International Conference on Theo-ry and Applications of Satisfiability Testing (SAT’12).2012:72-85
[25] Gaspers S,Szeider S.Strong backdoors to bounded treewidth SAT [C]∥Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS’13).2013:489-498
[26] Marx D,Razgon I.Constant ratio fixed-parameter approximation of the edge multicut problem [J].Information Processing Letters,2009,109 (20):1161-1166
[27] Bousquet N,Daligault J,Thomassé S.Multicut is FPT [C]∥Proceedings of the 43th Annual ACM Symposium on Theory of Computing (STOC’11).2011:459-468
[28] Ramanujan M S,Saurabh S.Linear time parameterized algo-rithms via skew-symmetric multicut [C]∥Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14).2014:1739-1748
[29] Bodlaender H L.On disjoint cycles [J].International Journal of Foundations of Computer Science,1994,5(1):59-68
[30] Chitnis R,Hajiaghayi M T,Kortsarz G.Fixed-parameter and approximation algorithms:a new look [C]∥Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC’13).2013:110-122
[31] Arvind V,Raman V.Approximation algorithms for some parameterized counting problems [C]∥Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC’02).2002:453-464
[32] Chen Jian-er,Liu Yang,Lu Song-jian,et al.A fixed-parameter algorithm for the directed feedback vertex set problem [C]∥Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC’08).2008:177-186
[33] Karp R M,Luby M,Madras N.Monte-Carlo approximation algorithms for enumeration problems [J].Journal of Algorithms,1989,10:429-448
[34] Liu Yun-long,Chen Jian-er,Wang Jian-xin.On counting 3-Dmatchings of size k [J].Algorithmica,2009,54:530-543
[35] Chen Jian-er,Lu Songjian,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
[36] Liu Yun-long,Wang Jian-xin,Chen Jian-er.Improved parameteri-zed algorithm for the Multicut problem [J].Journal of Software,2010,21(7):1515-1523(in Chinese) 刘运龙,王建新,陈建二.Multicut问题参数算法的改进[J].软件学报,2010,21(7):1515-1523
[37] Marx D.Can you beat treewidth? [J].Theory of Computing,2010,6:85-112
[38] Fellows M R,Guo J,Marx D,et al.Data reduction and problem kernels (Dagstuhl Seminar 12241) [R].Dagstuhl Reports,2012,2(6):26-50

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!