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.
A central goal of parameterized approximation is to settle the status of problems like Dominating Set or Clique , which are hard to approximate and also parameterized intractable. Recently, Chen and Lin @cite_28 made important progress by showing that Dominating Set admits no constant-factor approximation with running time @math unless @math . Generally, for problems without exact FPT-algorithms, the goal is to find out whether one can beat inapproximability bounds by allowing FPT-time in some parameter; see e.g. @cite_32 @cite_9 @cite_21 @cite_13 @cite_6 @cite_17 @cite_3 @cite_4 @cite_8 ).
@cite_4 @cite_8 @cite_28 @cite_9 @cite_21 @cite_32 @cite_6 @cite_3 @cite_13 @cite_17
2949062889 2963456765 2766474417 1995073517
A Fixed-Parameter Tractable ( ) @math -approximation algorithm for a minimization (resp. maximization) parameterized problem @math is an FPT algorithm that, given an instance @math computes a solution of cost at most @math (resp. @math ) if a solution of cost at most (resp. at least) @math exists; otherwise the output can be arbitrary. For well-known intractable problems such as the W[1]-hard Clique and W[2]-hard Set Cover problems, the natural question is whether we can get any -approximation. It is widely believed that both Clique and Set-Cover admit no FPT @math -approximation algorithm, for any increasing function @math . Assuming standard conjectures such as the Exponential Time Hypothesis (ETH) eth-paturi and the Projection Games Conjecture (PGC) r3 , we make the first progress towards proving this conjecture by showing that 1. Under the ETH and PGC, there exist constants @math such that the Set Cover problem does not admit an FPT approximation algorithm with ratio @math in @math time, where @math is the size of the universe and @math is the number of sets. 2. Unless @math , for every @math there exists a constant @math such that Clique has no FPT cost approximation with ratio @math in @math time, where @math is the number of vertices in the graph. In the second part of the paper we consider various W[1]-hard problems such as , , Directed Steiner Network and . For all these problem we give polynomial time @math -approximation algorithms for some small function @math (the largest approximation ratio we give is @math ). We prove that there is no fpt-algorithm that can approximate the dominating set problem with any constant ratio, unless FPT = W[1]. Our hardness reduction is built on the second author's recent W[1]-hardness proof of the biclique problem [25]. This yields, among other things, a proof without the PCP machinery that the classical dominating set problem has no polynomial time constant approximation under the exponential time hypothesis. We investigate the existence of approximation algorithms for maximization of submodular functions, that run in a fixed parameter tractable (FPT) time. Given a non-decreasing submodular set function v:2 X →R v : 2 X → R the goal is to select a subset S of K elements from X such that v(S) v ( S ) is maximized. We identify three properties of set functions, referred to as p -separability properties, and we argue that many real-life problems can be expressed as maximization of submodular, p -separable functions, with low values of the parameter p . We present FPT approximation schemes for the minimization and maximization variants of the problem, for several parameters that depend on characteristics of the optimized set function, such as p and K . In 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. To date this has remained the best algorithm, and whether it can or cannot be improved has become a major open problem in scheduling theory. We address this problem by establishing a quite surprising relation between the approximability of the considered problem and that of scheduling precedence constrained jobs on a single machine to minimize weighted completion time. More specifically, we prove that if the single machine problem is hard to approximate within a factor of @math , then the considered parallel machine problem, even in the case of unit processing times, is hard to approximate within a factor of @math , where @math tends to 0 as @math tends to 0. Combining this with Bansal and Khot's recent hardness result for the single machine problem gives that it is NP-hard to improve upon the approximation ratio obtained by Graham, assuming a new variant of the unique games conjecture.