Affordable Access

Publisher Website

Parameterized (in)approximability of subset problems

Authors
Journal
Operations Research Letters
0167-6377
Publisher
Elsevier
Volume
42
Issue
3
Identifiers
DOI: 10.1016/j.orl.2014.03.005
Keywords
  • Approximation
  • Complexity
  • Graph
  • Parameterized Algorithm

Abstract

Abstract 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.

There are no comments yet on this publication. Be the first to share your thoughts.