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 条
  • [1] DUAL PARAMETERIZATION AND PARAMETERIZED APPROXIMABILITY OF SUBSET GRAPH PROBLEMS
    Bonnet, Edouard
    Paschos, Vangelis Th.
    RAIRO-OPERATIONS RESEARCH, 2017, 51 (01) : 261 - 266
  • [2] Approximability of scheduling problems with resource consuming jobs
    Gyoergyi, Peter
    Kis, Tamas
    ANNALS OF OPERATIONS RESEARCH, 2015, 235 (01) : 319 - 336
  • [3] Parameterized analysis and crossing minimization problems
    Zehavi, Meirav
    COMPUTER SCIENCE REVIEW, 2022, 45
  • [4] Parameterized Complexity and Approximability of Coverability Problems in Weighted Petri Nets
    Watel, Dimitri
    Weisser, Marc-Antoine
    Barth, Dominique
    APPLICATION AND THEORY OF PETRI NETS AND CONCURRENCY, PETRI NETS 2017, 2017, 10258 : 330 - 349
  • [5] On the approximability of minmax (regret) network optimization problems
    Kasperski, Adam
    Zieliniski, Pawel
    INFORMATION PROCESSING LETTERS, 2009, 109 (05) : 262 - 266
  • [6] Complexity and Approximability of Parameterized MAX-CSPs
    Holger Dell
    Eun Jung Kim
    Michael Lampis
    Valia Mitsou
    Tobias Mömke
    Algorithmica, 2017, 79 : 230 - 250
  • [7] Complexity and Approximability of Parameterized MAX-CSPs
    Dell, Holger
    Kim, Eun Jung
    Lampis, Michael
    Mitsou, Valia
    Moemke, Tobias
    ALGORITHMICA, 2017, 79 (01) : 230 - 250
  • [8] Parameterized approximability of maximizing the spread of influence in networks''
    Bazgan, Cristina
    Chopin, Morgan
    Nichterlein, Andre
    Sikora, Florian
    JOURNAL OF DISCRETE ALGORITHMS, 2014, 27 (27) : 54 - 65
  • [9] On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
    Gunda, Spoorthy
    Jain, Pallavi
    Lokshtanov, Daniel
    Saurabh, Saket
    Tale, Prafullkumar
    ACM TRANSACTIONS ON COMPUTATION THEORY, 2021, 13 (04)
  • [10] BUYING CHEAP IS EXPENSIVE: APPROXIMABILITY OF COMBINATORIAL PRICING PROBLEMS
    Briest, Patrick
    Krysta, Piotr
    SIAM JOURNAL ON COMPUTING, 2011, 40 (06) : 1554 - 1586
12345