Parameterized (in)approximability of subset problems

被引：2
|
作者：
Bonnet, Edouard [1 ]
Paschos, Vangelis Th. [1 ]
机构：
[1] Univ Paris 09, PSL Res Univ, LAMSADE, CNRS UMR 7243, F-75775 Paris 16, France
来源：
OPERATIONS RESEARCH LETTERS | 2014年 / 42卷 / 03期
关键词：
Approximation; Complexity; Graph; Parameterized algorithm; OPTIMIZATION PROBLEMS; APPROXIMATION; ALGORITHMS; APPROXIMABILITY; COMPLEXITY;
D O I：
10.1016/j.orl.2014.03.005
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We discuss approximability and inapproximability in FPT-time for a large class of subset problems where a feasible solution S is a subset of the input data. We introduce the notion of intersective approximability that generalizes the one of safe approximability introduced in Guo et al. (2011) and show strong parameterized inapproximability results for many of the subset problems handled. (C) 2014 Elsevier B.V. All rights reserved.
引用
收藏
页码：222 / 225
页数：4
相关论文
共 50 条
  • [21] Evaluating genetic algorithms through the approximability hierarchy
    Munoz, Alba
    Rubio, Fernando
    JOURNAL OF COMPUTATIONAL SCIENCE, 2021, 53
  • [22] MAXIMUM MINIMAL VERTEX COVER PARAMETERIZED BY VERTEX COVER
    Zehavi, Meirav
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (04) : 2440 - 2456
  • [23] On the approximability of robust spanning tree problems
    Kasperski, Adam
    Zielinski, Pawel
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (4-5) : 365 - 374
  • [24] Parameterized Complexity of Eulerian Deletion Problems
    Cygan, Marek
    Marx, Daniel
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Schlotter, Ildiko
    ALGORITHMICA, 2014, 68 (01) : 41 - 61
  • [25] Parameterized Algorithms for Graph Partitioning Problems
    Shachnai, Hadas
    Zehavi, Meirav
    THEORY OF COMPUTING SYSTEMS, 2017, 61 (03) : 721 - 738
  • [26] Approximability and parameterized complexity of multicover by c-intervals
    van Bevern, Rene
    Chen, Jiehua
    Hueffner, Falk
    Kratsch, Stefan
    Talmon, Nimrod
    Woeginger, Gerhard J.
    INFORMATION PROCESSING LETTERS, 2015, 115 (10) : 744 - 749
  • [27] Extension of some edge graph problems: Standard, parameterized and approximation complexity
    Casel, Katrin
    Fernau, Henning
    Ghadikolaei, Mehdi Khosravian
    Monnot, Jerome
    Sikora, Florian
    DISCRETE APPLIED MATHEMATICS, 2023, 340 : 183 - 201
  • [28] Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
    Ene, Alina
    Vondrak, Jan
    Wu, Yi
    PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013), 2013, : 306 - 325
  • [29] Parameterized counting problems
    McCartin, C
    ANNALS OF PURE AND APPLIED LOGIC, 2006, 138 (1-3) : 147 - 182
  • [30] Completely inapproximable monotone and antimonotone parameterized problems
    Marx, Daniel
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2013, 79 (01) : 144 - 151
12345