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.
For the special case of where all input objects are squares a PTAS is known @cite_16 but there can be no EPTAS @cite_27 . Recently, @cite_1 found polynomial-time algorithms for and with approximation ratio smaller than @math (also for the weighted case). For the special case that all input objects are squares there is a PTAS @cite_19 and even an EPTAS @cite_15 .
@cite_1 @cite_19 @cite_27 @cite_15 @cite_16
1510609119 1972853793 2567804199 2963006872 1986978101 2031666601 2144614313 2057087699 2180828828 2281706401 2018541722 2054505111 2140566134 1998375208 2142607374 1571257748 2963782499 2091602684 2031347356 2059819407
An EPTAS (efficient PTAS) is an approximation scheme where e does not appear in the exponent of n, i.e., the running time is f(e)nc. We use parameterized complexity to investigate the possibility of improving the known approximation schemes for certain geometric problems to EPTAS. Answering an open question of Alber and Fiala [2], we show that Maximum Independent Set is W[1]-complete for the intersection graphs of unit disks and axis-parallel unit squares in the plane. A standard consequence of this result is that the @math time PTAS of [11] for Maximum Independent Set on unit disk graphs cannot be improved to an EPTAS. Similar results are obtained for the problem of covering points with squares. 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. An important question in theoretical computer science is to determine the best possible running time for solving a problem at hand. For geometric optimization problems, we often understand their complexity on a rough scale, but not very well on a finer scale. One such example is the two-dimensional knapsack problem for squares. There is a polynomial time (1 + ϵ)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1 ϵ, i.e., Ω(n221 ϵ). A double or triple exponential dependence on 1 ϵ is inherent in how this and several other algorithms for other geometric problems work. In this paper, we present an EPTAS for knapsack for squares, i.e., a (1+ϵ)-approximation algorithm with a running time of Oϵ(1)·nO(1). In particular, the exponent of n in the running time does not depend on ϵ at all! Since there can be no FPTAS for the problem (unless P = NP) this is the best kind of approximation scheme we can hope for. To achieve this improvement, we introduce two new key ideas: We present a fast method to guess the Ω(221 ϵ) relatively large squares of a suitable near-optimal packing instead of using brute-force enumeration. Secondly, we introduce an indirect guessing framework to define sizes of cells for the remaining squares. In the previous PTAS each of these steps needs a running time of Ω(n221 ϵ) and we improve both to Oϵ(1) · nO(1). We complete our result by giving an algorithm for two-dimensional knapsack for rectangles under (1 + ϵ)-resource augmentation. In this setting, we also improve the best known running time of Ω(n1 ϵ1 ϵ) to Oϵ(1) · nO(1) and compute even a solution with optimal profit, in contrast to the best previously known polynomial time algorithm for this setting that computes only an approximation. We believe that our new techniques have the potential to be useful for other settings as well. 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. We present a polynomial time approximation scheme (PTAS) for the minimum feedback arc set problem on tournaments. A simple weighted generalization gives a PTAS for Kemeny-Young rank aggregation. Abstract We address a variant of the classical knapsack problem in which an upper bound is imposed on the number of items that can be selected. This problem arises in the solution of real-life cutting stock problems by column generation, and may be used to separate cover inequalities with small support within cutting-plane approaches to integer linear programs. We focus our attention on approximation algorithms for the problem, describing a linear-storage Polynomial Time Approximation Scheme (PTAS) and a dynamic-programming based Fully Polynomial Time Approximation Scheme (FPTAS). The main ideas contained in our PTAS are used to derive PTAS's for the knapsack problem and its multi-dimensional generalization which improve on the previously proposed PTAS's. We finally illustrate better PTAS's and FPTAS's for the subset sum case of the problem in which profits and weights coincide. We study a geometric version of the Red-Blue Set Cover problem originally proposed by (2000) 1: given a red point set, a blue point set, and a set of objects, we want to choose a subset of objects to cover all the blue points, while minimizing the number of red points covered. We prove that the problem is NP-hard even when the objects are unit squares in 2D, and we give the first polynomial-time approximation scheme (PTAS) for this case. The technique we use simplifies and unifies previous PTASs for the weighted geometric set cover problem and the unique maximum coverage problem for 2D unit squares. We present the first monotone randomized polynomial-time approximation scheme (PTAS) for minimizing the makespan of parallel related machines ( @math ), the paradigmatic problem in single-parameter algorithmic mechanism design. This result immediately gives a polynomial-time, truthful (in expectation) mechanism whose approximation guarantee attains the best-possible one for all polynomial-time algorithms (assuming @math ). Our algorithmic techniques are flexible and also yield a monotone deterministic quasi-PTAS for @math and a monotone randomized PTAS for max-min scheduling on related machines. Many problems in bioinformatics are about finding strings that approximately represent a collection of given strings. We look at more general problems where some input strings can be classified as outliers. The Close to Most Strings problem is, given a set S of the same-length strings, and a parameter d, find a string x that maximizes the number of ''non-outliers'' within Hamming distance d of x. We prove that this problem has no polynomial-time approximation scheme (PTAS) unless NP has randomized polynomial-time algorithms, correcting a decade-old erroneous proof made previously in the literature. The Most Strings with Few Bad Columns problem is to find a maximum-size subset of input strings so that the number of non-identical positions is at most k; we show it has no PTAS unless P=NP. We also observe Closest to k Strings has no efficient PTAS (EPTAS) unless a parameterized complexity hierarchy collapses. In sum, outliers help model problems associated with using biological data, but we show the problem of finding an approximate solution is computationally difficult. 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. We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P = NP, it is not possible to get Fully Polynomial Time Approximation Algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in ℝ3 and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local-search algorithm which iterates over local improvements only. We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P=NP, it is not possible to get Fully Polynomial Time Approximation Algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in Re3 and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local search algorithm which iterates over local improvements only. We consider (uniform) sparsest cut, optimal linear arrangement and the precedence constrained scheduling problem 1 |prec| SigmawjCj-So far, these three notorious NP-hard problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approximation scheme (PTAS), unless NP-complete pmblems can be solved in randomized subexponential time. Furthermore, we prove that the scheduling problem is as-hard to approximate as vertex cover when the so-called fixed cost, that is present in all feasible solutions, is subtracted from the objective function. In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight subset of pairwise non-overlapping rectangles. Due to many applications, e.g. in data mining, map labeling and admission control, the problem has received a lot of attention by various research communities. We present the first (1 + e)-approximation algorithm for the MWISR problem with quasipolynomial running time 2poly(log n e). In contrast, the best known polynomial time approximation algorithms for the problem achieve superconstant approximation ratios of O(log log n) (unweighted case) and O(log n log log n) (weighted case). Key to our results is a new geometric dynamic program which recursively subdivides the plane into polygons of bounded complexity. We provide the technical tools that are needed to analyze its performance. In particular, we present a method of partitioning the plane into small and simple areas such that the rectangles of an optimal solution are intersected in a very controlled manner. Together with a novel application of the weighted planar graph separator theorem due to [4] this allows us to upper bound our approximation ratio by 1 + e. Our dynamic program is very general and we believe that it will be useful for other settings. In particular, we show that, when parametrized properly, it provides a polynomial time (1 + e)-approximation for the special case of the MWISR problem when each rectangle is relatively large in at least one dimension. Key to this analysis is a method to tile the plane in order to approximately describe the topology of these rectangles in an optimal solution. This technique might be a useful insight to design better polynomial time approximation algorithms or even a PTAS for the MWISR problem. In particular, note that our results imply that the MWISR problem is not APX-hard, unless NP ⊆ DTIME(2polylog (n)). We consider the special case of the traveling salesman problem (TSP) in which the distance metric is the shortest-path metric of a planar unweighted graph. We present a polynomial-time approximation scheme (PTAS) for this problem. Assuming that NP spl nsube spl cap sub spl epsi > 0 BPTIME(2 sup n spl epsi ), we show that graph min-bisection, densest subgraph and bipartite clique have no PTAS. We give a reduction from the minimum distance of code problem (MDC). Starting with an instance of MDC, we build a quasi-random PCP that suffices to prove the desired inapproximability results. In a quasi-random PCP, the query pattern of the verifier looks random in some precise sense. Among the several new techniques introduced, we give a way of certifying that a given polynomial belongs to a given subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial and it can be checked by reading a constant number of its values. We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of studies on this problem, focusing on exact and approximation algorithms, and it is thus natural to consider whether these algorithms are best possible in terms of the running time. Under the Exponential Time Hypothesis (ETH), we achieve the following results in this paper: • The scheduling problem on a constant number m of identical machines, which is denoted as Pm||Cmax, is known to admit a fully polynomial time approximation scheme (FPTAS) of running time O(n) + (1 e)O(m) (indeed, the algorithm works for an even more general problem where machines are unrelated). We prove this algorithm is essentially the best possible in the sense that a (1 e)O(m1-δ) + nO(1) time FPTAS for any δ > 0 implies that ETH fails. • The scheduling problem on an arbitrary number of identical machines, which is denoted as P||Cmax, is known to admit a polynomial time approximation scheme (PTAS) of running time 2O(1 e2 log3(1 e))+nO(1). We prove this algorithm is nearly optimal in the sense that a 2O((1 e)1-δ+nO(1) time PTAS for any δ > 0 implies that ETH fails, leaving a small room for improvement. In addition, we also consider exact algorithms for the scheduling problem and prove the following result: • The traditional dynamic programming algorithm for P||Cmax is known to run in 2O(n) time. We prove this is essentially the best possible in the sense that even if we restrict that there are n jobs and the processing time of each job is bounded by O(n), an exact algorithm of running time 22O(n1-δ) for any δ > 0 implies that ETH fails. To obtain these results we will provide two new reductions from 3SAT, one for Pm||Cmax and another for P||Cmax. Indeed, the new reductions explore the structure of scheduling problems and can also lead to other interesting results. For example, using the framework of our reduction for P||Cmax, [5] are able to prove the APX-hardness of the scheduling problem in which the matrix of job processing times P = (pij)mxn is of rank 3, solving the open problem mentioned in [2]. Assuming that NP @math @math BPTIME( @math ), we show that graph min-bisection, dense @math -subgraph, and bipartite clique have no polynomial time approximation scheme (PTAS). We give a reduction from the minimum distance of code (MDC) problem. Starting with an instance of MDC, we build a quasi-random probabilistically checkable proof (PCP) that suffices to prove the desired inapproximability results. In a quasi-random PCP, the query pattern of the verifier looks random in a certain precise sense. Among the several new techniques we introduce, the most interesting one gives a way of certifying that a given polynomial belongs to a given linear subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial, and it can be checked probabilistically by reading a constant number of its values. We consider the problem of scheduling jobs that are given as groups of non-intersecting segments on the real line. Each job J j is associated with an interval, I j , which consists of up to t segments, for some t ≥ 1, a positive weight, w j , and two jobs are in conflict if any of their segments intersect. Such jobs show up in a wide range of applications, including the transmission of continuous-media data, allocation of linear resources (e.g. bandwidth in linear processor arrays), and in computational biology geometry. The objective is to schedule a subset of non-conflicting jobs of maximum total weight.In a single machine environment, our problem can be formulated as the problem of finding a maximum weight independent set in a t-interval graph (the special case of t = 1 is an ordinary interval graph). We show that, for t ≥ 2, this problem is APX-hard, even for highly restricted instances. Our main result is a 2t-approximation algorithm for general instances, based on a novel fractional version of the Local Ratio technique. Previously, the problem was considered only for proper union graphs, a restricted subclass of t-interval graphs, and the approximation factor achieved was (2t - 1 + 1 2t). A bi-criteria polynomial time approximation scheme (PTAS) is developed for the subclass of t-union graphs.In the online case, we consider uniform weight jobs that consist of at most two segments. We show that when the resulting 2-interval graph is proper, a simple greedy algorithm is 3-competitive, while any randomized algorithm has competitive ratio at least 2.5. For general instances, we give a randomized O(log2 R)-competitive (or O((log R)2+e)-competitive) algorithm, where R is the known (unknown) ratio between the longest and the shortest segment in the input sequence. We consider the computation of the volume of the union of high-dimensional geometric objects. While showing that this problem is #P-hard already for very simple bodies, we give a fast FPRAS for all objects where one can (1) test whether a given point lies inside the object, (2) sample a point uniformly, and (3) calculate the volume of the object in polynomial time. It suffices to be able to answer all three questions approximately. We show that this holds for a large class of objects. It implies that Klee's measure problem can be approximated efficiently even though it is #P-hard and hence cannot be solved exactly in polynomial time in the number of dimensions unless P=NP. Our algorithm also allows to efficiently approximate the volume of the union of convex bodies given by weak membership oracles. For the analogous problem of the intersection of high-dimensional geometric objects we prove #P-hardness for boxes and show that there is no multiplicative polynomial-time 2^d^^^1^^^-^^^@e-approximation for certain boxes unless NP=BPP, but give a simple additive polynomial-time @e-approximation.