A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

被引：28
|
作者：
Feldmann, Andreas Emil [1 ]
Karthik, C. S. [2 ]
Lee, Euiwoong [3 ]
Manurangsi, Pasin [4 ]
机构：
[1] Charles Univ Prague, Dept Appl Math KAM, Prague 11800, Czech Republic
[2] Tel Aviv Univ, Dept Comp Sci, IL-6997801 Tel Aviv, Israel
[3] NYU, Courant Inst Math Sci, New York, NY 10012 USA
[4] Google Res, Mountain View, CA 94043 USA
来源：
ALGORITHMS | 2020年 / 13卷 / 06期
基金：
以色列科学基金会;
关键词：
parameterized complexity; approximation algorithms; hardness of approximation; LOCAL SEARCH YIELDS; TOTAL FLOW-TIME; INDEPENDENT SET; K-MEANS; EFFICIENT APPROXIMATION; UNIFIED FRAMEWORK; STEINER TREE; LOWER BOUNDS; INAPPROXIMABILITY; APPROXIMABILITY;
D O I：
10.3390/a13060146
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.
引用
收藏
页数：60
相关论文
共 50 条
  • [31] Parameterized Complexity and Approximation Issues for the Colorful Components Problems
    Dondi, Riccardo
    Sikora, Florian
    PURSUIT OF THE UNIVERSAL, 2016, 9709 : 261 - 270
  • [32] Parameterized complexity and approximation issues for the colorful components problems
    Dondi, Riccardo
    Sikora, Florian
    THEORETICAL COMPUTER SCIENCE, 2018, 739 : 1 - 12
  • [33] Parameterized algorithms and hardness results for some graph motif problems
    Betzler, Nadja
    Fellows, Michael R.
    Komusiewicz, Christian
    Niedermeier, Rolf
    COMBINATORIAL PATTERN MATCHING, 2008, 5029 : 31 - +
  • [34] Analysis Parameterized Algorithms on the Bases of Elasticity to Functions Complexity
    Bykova, Valentina V.
    JOURNAL OF SIBERIAN FEDERAL UNIVERSITY-MATHEMATICS & PHYSICS, 2011, 4 (02): : 195 - 207
  • [35] Reconstructing evolution of natural languages: Complexity and parameterized algorithms
    Kanj, Iyad A.
    Nakhleh, Luay
    Xia, Ge
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2006, 4112 : 299 - 308
  • [36] Paths of bounded length and their cuts: Parameterized complexity and algorithms
    Golovach, Petr A.
    Thilikos, Dimitrios M.
    DISCRETE OPTIMIZATION, 2011, 8 (01) : 72 - 86
  • [37] Parameterized Approximation Algorithms for Sum of Radii Clustering and Variants
    Chen, Xianrun
    Xu, Dachuan
    Xu, Yicheng
    Zhang, Yong
    THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 18, 2024, : 20666 - 20673
  • [38] Parameterized Approximation Algorithms for Some Location Problems in Graphs
    Leitert, Arne
    Dragan, Feodor F.
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2017, PT II, 2017, 10628 : 348 - 361
  • [39] Parameterized and Approximation Algorithms for Coverings Points with Segments in the Plane
    Kowalska, Katarzyna
    Pilipczuk, Michal
    41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024, 2024, 289
  • [40] Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
    Chitnis, Rajesh
    Feldmann, Andreas Emil
    Manurangsi, Pasin
    ACM TRANSACTIONS ON ALGORITHMS, 2021, 17 (02)
12345