计算机科学 ›› 2016, Vol. 43 ›› Issue (8): 7-12.doi: 10.11896/j.issn.1002-137X.2016.08.002
刘运龙,崔梦天
LIU Yun-long and CUI Meng-tian
摘要: 固定参数近似算法采用参数计算方法寻求问题的近似解,是实际中处理难解问题的一种新的有效手段。根据难解问题的参数计算复杂性类别,综述了固定参数可解问题、参数计算复杂性未定问题和W[t]-难问题(t≥1)固定参数近似算法近年来的研究进展。对于上述每一类问题,分别归纳了当前的主要研究结果,分析了其中的主要算法设计技术并探讨了有待研究的相关问题。
[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! |
|