Packing and Covering with Segments We study three fundamental geometric optimization problems xe2x80x93 independent set, piercing set, and dominating set xe2x80x93 on sets of axisparallel segments in the plane. We consider special cases in which the segments are either unit length or they are anchored on an inclined line (a line with slope (1)). When the segments are anchored on both sides, we prove that all three problems are NPcomplete (Throughout, we refer to NPcompleteness of problems, as the decision versions of the NPhard optimization problems we consider are all readily seen to be in NP.); NPcompleteness was known for the corresponding problems with axisparallel rectangles anchored on an inclined line (Correa et al. 4, Mudgal and Pandit 9, Pandit 10). Further, we prove that the dominating set problem with unit segments in the plane is NPcomplete. When the input segments are anchored on one side of the inclined line, there are polynomialtime algorithms for the independent set and piercing set problems.

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1eps)approximations in f(k,eps)nO(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 maximumcardinality subset of pairwise nonoverlapping rectangles. This problem is NPhard and also W1hard Marx, ESAu002705. The bestknown polynomialtime approximation factor is O(loglog n) Chalermsook and Chuzhoy, SODAu002709 and it admits a QPTAS Adamaszek and Wiese, FOCSu002713; Chuzhoy and Ene, FOCSu002716. Here we present a parameterized approximation scheme (PAS) for MISR, i.e. an algorithm that, for any given constant epsu003e0 and integer ku003e0, in time f(k,eps)ng(eps), either outputs a solution of size at least k(1eps), or declares that the optimum solution has size less than k. 2) In the (2dimensional) geometric knapsack problem (TDK) we are given an axisaligned square knapsack and a collection of axisaligned 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 NPhard, and the bestknown polynomialtime approximation factors are 558325eps and 43eps, resp. Galvez et al., FOCSu002717. These problems admit a QPTAS for polynomially bounded item sizes Adamaszek and Wiese, SODAu002715. We show that both variants are W1hard. Furthermore, we present a PAS for TDKR. For all considered problems, getting time f(k,eps)nO(1), rather than f(k,eps)ng(eps), would give FPT time fu0027(k)nO(1) exact algorithms using eps1(k1), contradicting W1hardness.