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 条
  • [31] Parameterized Complexity of Streaming Diameter and Connectivity Problems
    Oostveen, Jelle J.
    van Leeuwen, Erik Jan
    ALGORITHMICA, 2024, 86 (09) : 2885 - 2928
  • [32] Dynamic Parameterized Problems
    Krithika, R.
    Sahu, Abhishek
    Tale, Prafullkumar
    ALGORITHMICA, 2018, 80 (09) : 2637 - 2655
  • [33] Implicit branching and parameterized partial cover problems
    Amini, Omid
    Fomin, Fedor V.
    Saurabh, Saket
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2011, 77 (06) : 1159 - 1171
  • [34] Dealing with several parameterized problems by random methods
    Feng, Qilong
    Huang, Neng
    Jiang, Xiong
    Wang, Jianxin
    THEORETICAL COMPUTER SCIENCE, 2018, 734 : 94 - 104
  • [35] Approximability of Unsplittable Shortest Path Routing Problems
    Bley, Andreas
    NETWORKS, 2009, 54 (01) : 23 - 46
  • [36] Holant Clones and the Approximability of Conservative Holant Problems
    Backens, Miriam
    Goldberg, Leslie Ann
    ACM TRANSACTIONS ON ALGORITHMS, 2020, 16 (02)
  • [37] On the complexity and approximability of budget-constrained minimum-cost flows
    Holzhauser, Michael
    Krunike, Sven O.
    Thielen, Clemens
    INFORMATION PROCESSING LETTERS, 2017, 126 : 24 - 29
  • [38] Dynamic Parameterized Problems and Algorithms
    Alman, Josh
    Mnich, Matthias
    Williams, Virginia Vassilevska
    ACM TRANSACTIONS ON ALGORITHMS, 2020, 16 (04)
  • [39] Parameterized Resiliency Problems via Integer Linear Programming
    Crampton, Jason
    Gutin, Gregory
    Koutecky, Martin
    Watrigant, Remi
    ALGORITHMS AND COMPLEXITY (CIAC 2017), 2017, 10236 : 164 - 176
  • [40] Parameterized graph cleaning problems
    Marx, Daniel
    Schlotter, Ildiko
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (15) : 3258 - 3267
12345