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.
The systematic study of parameterized approximation as a field was initiated independently by three separate publications @cite_10 @cite_5 @cite_7 . A very good introduction to the area including key definitions as well as a survey of earlier results that fit into the picture was given by Marx @cite_24 . In particular, Marx also defined a so-called that, given input @math will run for @math time and return (say, for a maximization problem) a solution of value at least @math if the optimum is at least @math . As mentioned earlier, Marx pointed out that a standard FPT-approximation scheme that finds a solution of value at least @math in time @math if @math is not interesting to study: By setting @math we can decide the decision problem @math ?'' in FPT time. Thus, such a scheme is not helpful if the decision problem is 1 -hard and therefore unlikely to have an FPT-algorithm. Nevertheless, PASs can be useful in this case, as they imply standard FPT-approximation algorithms with ratio @math for each fixed @math despite 1 -hardness.
@cite_24 @cite_5 @cite_10 @cite_7
1980809300 2773392011 2118980874 1516574938
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 ). Given a directed graph @math and a list @math of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of @math that contains a directed @math path for every @math . The special case Directed Steiner Tree (when we ask for paths from a root @math to terminals @math ) is known to be fixed-parameter tractable parameterized by the number of terminals, while the special case Strongly Connected Steiner Subgraph (when we ask for a path from every @math to every other @math ) is known to be W[1]-hard. We systematically explore the complexity landscape of directed Steiner problems to fully understand which other special cases are FPT or W[1]-hard. Formally, if @math is a class of directed graphs, then we look at the special case of Directed Steiner Network where the list @math of requests form a directed graph that is a member of @math . Our main result is a complete characterization of the classes @math resulting in fixed-parameter tractable special cases: we show that if every pattern in @math has the combinatorial property of being "transitively equivalent to a bounded-length caterpillar with a bounded number of extra edges," then the problem is FPT, and it is W[1]-hard for every recursively enumerable @math not having this property. This complete dichotomy unifies and generalizes the known results showing that Directed Steiner Tree is FPT [Dreyfus and Wagner, Networks 1971], @math -Root Steiner Tree is FPT for constant @math [Such 'y, WG 2016], Strongly Connected Steiner Subgraph is W[1]-hard [, SIAM J. Discrete Math. 2011], and Directed Steiner Network is solvable in polynomial-time for constant number of terminals [Feldman and Ruhl, SIAM J. Comput. 2006], and moreover reveals a large continent of tractable cases that were not known before. There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of such problems, the current fastest algorithm is the best possible under some complexity assumptions. To bypass this difficulty, (SODA 2017) introduced the concept of fully polynomial FPT algorithms. For a problem with the current best time complexity @math , the goal is to design an algorithm running in @math time for a parameter @math and a constant @math . In this paper, we investigate the complexity of graph problems in P parameterized by tree-depth, a graph parameter related to tree-width. We show that a simple divide-and-conquer method can solve many graph problems, including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle, Replacement Paths, and 2-hop Cover, in @math time or @math time, where @math is the tree-depth of the input graph. Because any graph of tree-width @math has tree-depth at most @math , our algorithms also run in @math time or @math time. These results match or improve the previous best algorithms parameterized by tree-width. Especially, we solve an open problem of fully polynomial FPT algorithm for Weighted Matching parameterized by tree-width posed by We study approximation algorithms for several variants of the MaxCover problem, with the focus on algorithms that run in FPT time. In the MaxCover problem we are given a set N of elements, a family S of subsets of N, and an integer K. The goal is to find up to K sets from S that jointly cover (i.e., include) as many elements as possible. This problem is well-known to be NP-hard and, under standard complexitytheoretic assumptions, the best possible polynomial-time approximation algorithm has approximation ratio (1 − 1 ). We first consider a variant of MaxCover with bounded element frequencies, i.e., a variant where there is a constant p such that each element belongs to at most p sets in S. For this case we show that there is an FPT approximation scheme (i.e., for each β there is a β-approximation algorithm running in FPT time) for the problem of maximizing the number of covered elements, and a randomized FPT approximation scheme for the problem of minimizing the number of elements left uncovered (we take K to be the parameter). Then, for the case where there is a constant p such that each element belongs to at least p sets from S, we show that the standard greedy approximation algorithm achieves approximation ratio exactly 1 − e −max(pK kSk,1) . We conclude by considering an unrestricted variant of MaxCover, and show approximation algorithms that run in exponential time and combine an exact algorithm with a greedy approximation. Some of our results improve currently known results for MaxVertexCover. The subspace approximation problem Subspace( @math , @math ) asks for a @math -dimensional linear subspace that fits a given set of points optimally, where the error for fitting is a generalization of the least squares fit and uses the @math norm instead. Most of the previous work on subspace approximation has focused on small or constant @math and @math , using coresets and sampling techniques from computational geometry. In this paper, extending another line of work based on convex relaxation and rounding, we give a polynomial time algorithm, , with the approximation guarantee roughly @math , where @math is the @math -th moment of a standard normal random variable N(0,1). We show that the convex relaxation we use has an integrality gap (or "rank gap") of @math , for any constant @math . Finally, we show that assuming the Unique Games Conjecture, the subspace approximation problem is hard to approximate within a factor better than @math , for any constant @math . We consider the @math -Center problem and some generalizations. For @math -Center a set of @math center vertices needs to be found in a graph @math with edge lengths, such that the distance from any vertex of @math to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded highway dimension, as proposed by [SODA 2010]. We show both approximation and fixed-parameter hardness results, and how to overcome them using fixed-parameter approximations, where the two paradigms are combined. In particular, we prove that for any @math computing a @math -approximation is W[2]-hard for parameter @math and NP-hard for graphs with highway dimension @math . The latter does not rule out fixed-parameter @math -approximations for the highway dimension parameter @math , but implies that such an algorithm must have at least doubly exponential running time in @math if it exists, unless the ETH fails. On the positive side, we show how to get below the approximation factor of @math by combining the parameters @math and @math : we develop a fixed-parameter @math -approximation with running time @math . Additionally we prove that, unless P=NP, our techniques cannot be used to compute fixed-parameter @math -approximations for only the parameter @math . We also provide similar fixed-parameter approximations for the weighted @math -Center and @math -Partition problems, which generalize @math -Center. We describe a new approximation algorithm for Max Cut. Our algorithm runs in @math time, where @math is the number of vertices, and achieves an approximation ratio of @math . In instances in which an optimal solution cuts a @math fraction of edges, our algorithm finds a solution that cuts a @math fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a @math fraction of edges, our spectral partitioning algorithm finds a set @math of vertices and a bipartition @math of @math such that at least a @math fraction of the edges incident on @math have one endpoint in @math and one endpoint in @math . (This can be seen as an analogue of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, var... We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds @math on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a @math -approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex @math is at most @math . This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly @math -Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost @math -edge-connected subgraph with at least @math vertices, which we call the @math -subgraph problem. This generalizes some well-studied classical problems such as the @math -MST and the minimum cost @math -edge-connected subgraph problems. We give a polylogarithmic approximation for the @math -subgraph problem. However, by relating it to the Densest @math -Subgraph problem, we provide evidence that the @math -subgraph problem might be hard to approximate for arbitrary @math . We study constant-time approximation algorithms for bounded-degree graphs, which run in time independent of the number of vertices @math . We present an algorithm that decides whether a vertex is contained in a some fixed maximal independent set with expected query complexity @math , where @math is the degree bound. Using this algorithm, we show constant-time approximation algorithms with certain multiplicative error and additive error @math for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to @math and @math . Our approximation algorithm for the maximum matching problem can be transformed to a two-sided error tester for the property of having a perfect matching. On the contrary, we show that every one-sided error tester for the property requires at least @math queries. In this paper we design polynomial time approximation algorithms for several parameterized problems such as Odd Cycle Transversal, Almost 2-SAT, Above Guarantee Vertex Cover and Deletion q-Horn Backdoor Set Detection. Our algorithm proceeds by first reducing the given instance to an instance of the d-Skew-Symmetric Multicut problem, and then computing an approximate solution to this instance. Our algorithm runs in polynomial time and returns a solution whose size is bounded quadratically in the parameter, which in this case is the solution size, thus making it useful as a first step in the design of kernelization algorithms. Our algorithm relies on the properties of a combinatorial object called (L,k)-set, which builds on the notion of (L,k)-components, defined by a subset of the authors to design a linear time FPT algorithm for Odd Cycle Transversal. The main motivation behind the introduction of this object in their work was to replicate in skew-symmetric graphs, the properties of important separators introduced by Marx [2006] which has played a very significant role in several recent parameterized tractability results. Combined with the algorithm of Reed, Smith and Vetta, our algorithm also gives an alternate linear time algorithm for Odd Cycle Transversal. Furthermore, our algorithm significantly improves upon the running time of the earlier parameterized approximation algorithm for Deletion q-Horn Backdoor Set Detection which had an exponential dependence on the parameter; albeit at a small cost in the approximation ratio. We consider the k-Center problem and some generalizations. For k-Center a set of kcenter vertices needs to be found in a graph G with edge lengths, such that the distance from any vertex ofi¾?G to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded highway dimension, as proposed by [ICALP 2011]. We show both approximation and fixed-parameter hardness results, and how to overcome them using fixed-parameter approximations. In particular, we prove that for any @math computing a @math -approximation is W[2]-hard for parameter k, and NP-hard for graphs with highway dimension @math . The latter does not rule out fixed-parameter @math -approximations for the highway dimension parameteri¾?h, but implies that such an algorithm must have at least doubly exponential running time in h if it exists, unless the ETH fails. On the positive side, we show how to get below the approximation factor ofi¾?2 by combining the parameters k andi¾?h: we develop a fixed-parameter 3 2-approximation with running time @math . We also provide similar fixed-parameter approximations for the weightedk-Center and @math -Partition problems, which generalize k-Center. We give a 7.18-approximation algorithm for the minimum latency problem that uses only @math calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the @math -minimum spanning tree ( @math -MST) problem which is called as a black box for each value of @math . Their algorithm can achieve an approximation factor of 10.77 while making @math PCST calls, a factor of 8.98 using @math PCST calls, or a factor of @math using @math PCST calls, via the @math -MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here @math denotes the number of nodes in the instance, and @math is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in @math time, the overall running time of our algorithm is @math . We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only @math PCST calls, and derandomize it to obtain a deterministic algorithm with factor @math , using @math PCST calls. The basic idea for our improvement is that we do not treat the @math -MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate @math -MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate @math -MSTs for all values of @math , even though we have them only for some values of @math that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem. We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . Let G=(V,E) be a weighted undirected graph where all weights are at least one. We consider the following generalization of feedback set problems. Let @math be a subset of the vertices. A cycle is called interesting if it intersects the set S. A subset feedback edge (vertex) set is a subset of the edges (vertices) that intersects all interesting cycles. In minimum subset feedback problems the goal is to find such sets of minimum weight. This problem has a variety of applications, among them genetic linkage analysis and circuit testing. The case in which S consists of a single vertex is equivalent to the multiway cut problem, in which the goal is to separate a given set of terminals. Hence, the subset feedback problem is NP-complete and also generalizes the multiway cut problem. We provide a polynomial time algorithm for approximating the subset feedback edge set problem that achieves an approximation factor of two. This implies a @math -approximation algorithm for the subset feedback vertex set problem, where @math is the maximum degree in G. We also consider the multicut problem and show how to achieve an @math approximation factor for this problem, where @math is the value of the optimal fractional solution. To achieve the @math factor we employ a bootstrapping technique. A central theme in distributed network algorithms concerns understanding and coping with the issue of locality . Despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for . In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard @math model of computation and define @math (for local decision ) as the class of decision problems that can be solved in @math communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class @math , containing all languages for which there exists a randomized algorithm that runs in @math rounds, accepts correct instances with probability at least @math and rejects incorrect ones with probability at least @math . We show that @math is a threshold for the containment of @math in @math . More precisely, we show that there exists a language that does not belong to @math for any @math but does belong to @math for any @math such that @math . On the other hand, we show that, restricted to hereditary languages, @math , for any function @math and any @math such that @math . In addition, we investigate the impact of non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with non-determinism that enables to decide languages . Finally, we introduce the notion of local reduction, and establish some completeness results. We consider the over-time version of the Max-Min Fair Allocation problem. Given a time horizon @math , with at each time t a set of demands and a set of available resources that may change over the time defining instance @math , we seek a sequence of solutions @math that (1) are near-optimal at each time t , and (2) as stable as possible (inducing small modification costs). We focus on the impact of the knowledge of the future on the quality and the stability of the returned solutions by distinguishing three settings: the off-line setting where the whole set of instances through the time horizon is known in advance, the on-line setting where no future instance is known, and the k -lookahead setting where at time t , the instances at times @math are known. We first consider the case without restrictions where the set of resources and the set of agents are the same for all instances and where every resource can be allocated to any agent. For the off-line setting, we show that the over-time version of the problem is much harder than the static one, since it becomes @math -hard even for families of instances for which the static problem is trivial. Then, we provide a @math -approximation algorithm for the off-line setting using as subroutine a ρ-approximation algorithm for the static version. We also give a @math -competitive algorithm for the online setting using also as subroutine a ρ-approximation algorithm for the static version. Furthermore, for the case with restrictions, we show that in the off-line setting it is possible to get a polynomial-time algorithm with the same approximation ratio as in the case without restrictions. For the online setting, we prove that it is not possible to find an online algorithm with bounded competitive ratio. For the 1-lookahead setting however, we give a @math -approximation algorithm using as subroutine a ρ-approximation algorithm for the static version. The bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes a 1 ,…, a n in (0,1]. Using uniform sampling, which selects a random element from the input list each time, we develop a randomized @math time (1+e )-approximation scheme for the bin packing problem. We show that every randomized algorithm with uniform random sampling needs @math time to give an (1+e )-approximation. For each function s (n ): N →N , define ∑(s (n )) to be the set of all bin packing problems with the sum of item sizes equal to s (n ). We show that ∑(n b ) is NP-hard for every b ∈(0,1]. This implies a dense sublinear time hierarchy of approximation schemes for a class of NP-hard problems, which are derived from the bin packing problem. We also show a randomized streaming approximation scheme for the bin packing problem such that it needs only constant updating time and constant space, and outputs an (1+e )-approximation in @math time. Let S (δ )-bin packing be the class of bin packing problems with each input item of size at least δ . This research also gives a natural example of NP-hard problem (S (δ )-bin packing) that has a constant time approximation scheme, and a constant time and space sliding window streaming approximation scheme, where δ is a positive constant. The Euclidean @math -means problem is a classical problem that has been extensively studied in the theoretical computer science, machine learning and the computational geometry communities. In this problem, we are given a set of @math points in Euclidean space @math , and the goal is to choose @math centers in @math so that the sum of squared distances of each point to its nearest center is minimized. The best approximation algorithms for this problem include a polynomial time constant factor approximation for general @math and a @math -approximation which runs in time @math . At the other extreme, the only known computational complexity result for this problem is NP-hardness [ADHP'09]. The main difficulty in obtaining hardness results stems from the Euclidean nature of the problem, and the fact that any point in @math can be a potential center. This gap in understanding left open the intriguing possibility that the problem might admit a PTAS for all @math . In this paper we provide the first hardness of approximation for the Euclidean @math -means problem. Concretely, we show that there exists a constant @math such that it is NP-hard to approximate the @math -means objective to within a factor of @math . We show this via an efficient reduction from the vertex cover problem on triangle-free graphs: given a triangle-free graph, the goal is to choose the fewest number of vertices which are incident on all the edges. Additionally, we give a proof that the current best hardness results for vertex cover can be carried over to triangle-free graphs. To show this we transform @math , a known hard vertex cover instance, by taking a graph product with a suitably chosen graph @math , and showing that the size of the (normalized) maximum independent set is almost exactly preserved in the product graph using a spectral analysis, which might be of independent interest. Given a set @math of m unit disks and a set @math of n points in the plane, the discrete unit disk cover problem is to select a minimum cardinality subset @math to cover @math . This problem is NP-hard [14] and the best previous practical solution is a 38-approximation algorithm by [5]. We first consider the line-separable discrete unit disk cover problem (the set of disk centers can be separated from the set of points by a line) for which we present an O(n(log n + m))-time algorithm that finds an exact solution. Combining our line-separable algorithm with techniques from the algorithm of [5] results in an O(m2n4) time 22-approximate solution to the discrete unit disk cover problem. We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were @math for both directed and undirected graphs, and @math for undirected graphs with @math , where @math is the number of nodes in the input graph. Our first algorithm has approximation ratio @math , which is @math except for very large values of @math , namely, @math . This algorithm is based on a new result on @math -connected @math -critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio @math for all values of @math . Combining these two gives an algorithm with approximation ratio @math , which asymptotically improves the best known approximation guarantee for directed graphs for all values of @math , and for undirected graphs for @math . Moreover, this is the first algorithm that has an approximation guarantee better than @math for all values of @math . Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation.