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 条
  • [21] Gehrlein stability in committee selection: parameterized hardness and algorithms
    Sushmita Gupta
    Pallavi Jain
    Sanjukta Roy
    Saket Saurabh
    Meirav Zehavi
    Autonomous Agents and Multi-Agent Systems, 2020, 34
  • [22] Gehrlein Stability in Committee Selection: Parameterized Hardness and Algorithms
    Gupta, Sushmita
    Jain, Pallavi
    Roy, Sanjukta
    Saurabh, Saket
    Zehavi, Meirav
    AAMAS '19: PROCEEDINGS OF THE 18TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS, 2019, : 511 - 519
  • [23] Parameterized Approximation Algorithms for Weighted Vertex Cover
    Mandal, Soumen
    Misra, Pranabendu
    Rai, Ashutosh
    Saurabh, Saket
    LATIN 2024: THEORETICAL INFORMATICS, PT II, 2024, 14579 : 177 - 192
  • [24] Parameterized and Approximation Algorithms for the Load Coloring Problem
    F. Barbero
    G. Gutin
    M. Jones
    B. Sheng
    Algorithmica, 2017, 79 : 211 - 229
  • [25] Parameterized approximation algorithms for weighted vertex cover
    Mandal, Soumen
    Misra, Pranabendu
    Rai, Ashutosh
    Saurabh, Saket
    THEORETICAL COMPUTER SCIENCE, 2024, 1021
  • [26] Parameterized and Approximation Algorithms for the Load Coloring Problem
    Barbero, F.
    Gutin, G.
    Jones, M.
    Sheng, B.
    ALGORITHMICA, 2017, 79 (01) : 211 - 229
  • [27] Approximation algorithms for some parameterized counting problems
    Arvind, V
    Raman, V
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2002, 2518 : 453 - 464
  • [28] Approximation algorithms and hardness for domination with propagation
    Aazami, Ashkan
    Stilp, Michael D.
    APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 2007, 4627 : 1 - +
  • [29] APPROXIMATION ALGORITHMS AND HARDNESS FOR DOMINATION WITH PROPAGATION
    Aazami, Ashkan
    Stilp, Kael
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (03) : 1382 - 1399
  • [30] On the hardness of labeled correlation clustering problem: A parameterized complexity view
    Liu, Xianmin
    Li, Jianzhong
    Gao, Hong
    THEORETICAL COMPUTER SCIENCE, 2016, 609 : 583 - 593
12345