Article ID Journal Published Year Pages File Type
1142451 Operations Research Letters 2014 4 Pages PDF
Abstract

We discuss approximability and inapproximability in FPT-time for a large class of subset problems   where a feasible solution SS 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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Parameterized (in)approximability of subset problems
Authors
, ,