text: The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1+eps)-approximations in f(k,eps)n^ O(1) time where k is some parameter of the input. We obtain the following results on parameterized approximability: 1) In the maximum independent set of rectangles problem (MISR) we are given a collection of n axis parallel rectangles in the plane. Our goal is to select a maximum-cardinality subset of pairwise non-overlapping rectangles. This problem is NP-hard and also W[1]-hard [Marx, ESA'05]. The best-known polynomial-time approximation factor is O(loglog n) [Chalermsook and Chuzhoy, SODA'09] and it admits a QPTAS [Adamaszek and Wiese, FOCS'13; Chuzhoy and Ene, FOCS'16]. Here we present a parameterized approximation scheme (PAS) for MISR, i.e. an algorithm that, for any given constant eps>0 and integer k>0, in time f(k,eps)n^ g(eps) , either outputs a solution of size at least k (1+eps), or declares that the optimum solution has size less than k. 2) In the (2-dimensional) geometric knapsack problem (TDK) we are given an axis-aligned square knapsack and a collection of axis-aligned rectangles in the plane (items). Our goal is to translate a maximum cardinality subset of items into the knapsack so that the selected items do not overlap. In the version of TDK with rotations (TDKR), we are allowed to rotate items by 90 degrees. Both variants are NP-hard, and the best-known polynomial-time approximation factors are 558 325+eps and 4 3+eps, resp. [, FOCS'17]. These problems admit a QPTAS for polynomially bounded item sizes [Adamaszek and Wiese, SODA'15]. We show that both variants are W[1]-hard. Furthermore, we present a PAS for TDKR. For all considered problems, getting time f(k,eps)n^ O(1) , rather than f(k,eps)n^ g(eps) , would give FPT time f'(k)n^ O(1) exact algorithms using eps=1 (k+1), contradicting W[1]-hardness.
  @cite_29: A polynomial time approximation scheme (PTAS) for an optimization problem A is an algorithm that given in input an instance of A and e > 0 finds a (1 + e)-approximate solution in time that is polynomial for each fixed e. Typical running times are nO(1e) or 21eO(1) n. While algorithms of the former kind tend to be impractical, the latter ones are more interesting. In several cases, the development of algorithms of the second type required considerably new, and sometimes harder, techniques. For some interesting problems, only nO(1e) approximation schemes are known. Under likely assumptions, we prove that for some problems (including natural ones) there cannot be approximation schemes running in time f(1 ϵ) n p0(1), no matter how fast function f grows. Our result relies on a connection with Parameterized Complexity Theory, and we show that this connection is necessary.
  @cite_33: In the Closest String problem one is given a family S of equal-length strings over some fixed alphabet, and the task is to find a string y that minimizes the maximum Hamming distance between y and a string from S. While polynomial-time approximation schemes (PTASes) for this problem are known for a long time [; J. ACM'02], no efficient polynomial-time approximation scheme (EPTAS) has been proposed so far. In this paper, we prove that the existence of an EPTAS for Closest String is in fact unlikely, as it would imply that FPT=W[1], a highly unexpected collapse in the hierarchy of parameterized complexity classes. Our proof also shows that the existence of a PTAS for Closest String with running time f(eps) n^o(1 eps), for any computable function f, would contradict the Exponential Time Hypothesis.
  @cite_25: Given n length-L strings S = s1, …, s n over a constant size alphabet Σ together with an integer l, where l ≤ L, the objective of Consensus Patterns is to find a length-l string s, a substring t i of each s i in S such that ∑ ∀ id(t i , s) is minimized. Here d(x, y) denotes the Hamming distance between the two strings x and y. Consensus Patterns admits a PTAS [, JCSS 2002] is fixed parameter tractable when parameterized by the objective function value [Marx, SICOMP 2008], and although it is a well-studied problem, improvement of the PTAS to an EPTAS seemed elusive. We prove that Consensus Patterns does not admit an EPTAS unless FPT=W[1], answering an open problem from [, STACS 2002, Combinatorica 2006]. To the best of our knowledge, Consensus Patterns is the first problem that admits a PTAS, and is fixed parameter tractable when parameterized by the value of the objective function but does not admit an EPTAS under plausible complexity assumptions. The proof of our hardness of approximation result combines parameterized reductions and gap preserving reductions in a novel manner.
  @cite_23: 
summary: One of the first fruitful connections between parameterized complexity and approximability was observed independently by Bazgan @cite_23 and Cesati and Trevisan @cite_29 : They showed that EPTASs, i.e., @math -approximation algorithms with @math time, imply fixed-parameter tractability for the decision version. Thus, proofs for 1 -hardness of the decision version became a strong tool for ruling out improvements of PTASs, with running time @math , to EPTASs. More recently, @cite_25 improved this approach by directly proving 1 -hardness of obtaining a @math -approximation, thus bypassing the requirement of a 1 -hard decision version (see also @cite_33 ).