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 条
  • [41] SLIGHTLY SUPEREXPONENTIAL PARAMETERIZED PROBLEMS
    Lokshtanov, Daniel
    Marx, Daniel
    Saurabh, Saket
    SIAM JOURNAL ON COMPUTING, 2018, 47 (03) : 675 - 702
  • [42] Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems
    Yamakami, Tomoyuki
    ALGORITHMS AND COMPUTATION, 2011, 7074 : 454 - 463
  • [43] Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability
    Amarilli, Antoine
    van Bremen, Timothy
    Meel, Kuldeep S.
    27TH INTERNATIONAL CONFERENCE ON DATABASE THEORY, ICDT 2024, 2024, 290
  • [44] Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized
    Jain, Pallavi
    Kanesh, Lawqueen
    Misra, Pranabendu
    THEORY OF COMPUTING SYSTEMS, 2020, 64 (06) : 1067 - 1093
  • [45] Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized
    Jain, Pallavi
    Kanesh, Lawqueen
    Misra, Pranabendu
    COMPUTER SCIENCE - THEORY AND APPLICATIONS, CSR 2018, 2018, 10846 : 194 - 206
  • [46] Complexity and approximability of k-splittable flows
    Koch, Ronald
    Spenke, Ines
    THEORETICAL COMPUTER SCIENCE, 2006, 369 (1-3) : 338 - 347
  • [47] Approximability of maximum splitting of k-sets and some other Apx-complete problems
    Kann, V
    Lagergren, J
    Panconesi, A
    INFORMATION PROCESSING LETTERS, 1996, 58 (03) : 105 - 110
  • [48] Parameterized Local Search for Max c-Cut
    Garvardt, Jaroslav
    Gruettemeier, Niels
    Komusiewicz, Christian
    Morawietz, Nils
    PROCEEDINGS OF THE THIRTY-SECOND INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2023, 2023, : 5586 - 5594
  • [49] Some Undecidable Problems on Approximability of NP Optimization Problems
    黄雄
    Journal of Computer Science and Technology, 1996, (02) : 126 - 132
  • [50] The approximability of three-dimensional assignment problems with bottleneck objective
    Goossens, Dries
    Polyakovskiy, Sergey
    Spieksma, Frits C. R.
    Woeginger, Gerhard J.
    OPTIMIZATION LETTERS, 2010, 4 (01) : 7 - 16
12345