In this paper, we study problems of connecting classes of points via noncrossing structures. Given a set of colored terminal points, we want to find a graph for each color that connects all terminals of its color with the restriction that no two graphs cross each other. We consider these problems both on the Euclidean plane and in planar graphs. On the algorithmic side, we give a Gap-ETH-tight EPTAS for the bicolored noncrossing travelling salesman tours problem as well as for the red-blue-green separation problem (in which we want to separate terminals of three colors with two noncrossing polygons of minimum length), both on the Euclidean plane. This improves the work of Arora and Chang (ICALP 2003) who gave a slower PTAS for the simpler red-blue separation problem. For the case of unweighted plane graphs, we also show a PTAS for the bicolored noncrossing travelling salesman tours problem. All these results are based on our new patching procedure that might be of independent interest. On the negative side, we show that the problem of connecting terminal pairs with noncrossing paths is NP-hard on the Euclidean plane, and that the problem of finding two noncrossing spanning trees is NP-hard in plane graphs.

In the Traveling Salesperson Problem with Neighborhoods (TSPN), we are given a collection of geometric regions in some space. The goal is to output a tour of minimum length that visits at least one point in each region. Even in the Euclidean plane, TSPN is known to be APX-hard [27{, which gives rise to studying more tractable special cases of the problem. In this article, we focus on the fundamental special case of regions that are hyperplanes in the d -dimensional Euclidean space. This case contrasts the much-better understood case of so-called fat regions [20, 40{. While for d = 2, an exact algorithm with a running time of O(n 5 ) is known [34{, settling the exact approximability of the problem for d = 3 has been repeatedly posed as an open question [29, 30, 40, 47{. To date, only an approximation algorithm with guarantee exponential in d is known [30{, and NP-hardness remains open. For arbitrary fixed d , we develop a Polynomial Time Approximation Scheme (PTAS) that works for both the tour and path version of the problem. Our algorithm is based on approximating the convex hull of an optimal tour by a convex polytope of bounded complexity. After enumerating a number of structural properties of these polytopes, a linear program finds one of them that minimizes the length of the tour. As the approximation guarantee approaches 1, our scheme adjusts the complexity of the considered polytopes accordingly. In the analysis of our approximation scheme, we show that our search space includes a sufficiently good approximation of the optimum. To do so, we develop a novel and general sparsification technique that transforms an arbitrary convex polytope into one with a constant number of vertices, and, subsequently, into one of bounded complexity in the above sense. We show that this transformation does not increase the tour length by too much, while the transformed tour visits any hyperplane that it visited before the transformation.

In the Traveling Salesperson Problem with Neighborhoods (TSPN), we are given a collection of geometric regions in some space. The goal is to output a tour of minimum length that visits at least one point in each region. Even in the Euclidean plane, TSPN is known to be APX-hard [20], which gives rise to studying more tractable special cases of the problem. In this paper, we focus on the fundamental special case of regions that are hyperplanes in the d-dimensional Euclidean space. This case contrasts the much-better understood case of so-called fat regions [16, 34]. While for d = 2 an exact algorithm with running time O(n5) is known [28], settling the exact approximability of the problem for d = 3 has been repeatedly posed as an open question [23, 24, 34, 40]. To date, only an approximation algorithm with guarantee exponential in d is known [24], and NP-hardness remains open. For arbitrary fixed d, we develop a Polynomial Time Approximation Scheme (PTAS) that works for both the tour and path version of the problem. Our algorithm is based on approximating the convex hull of the optimal tour by a convex polytope of bounded complexity. Such polytopes are represented as solutions of a sophisticated LP formulation, which we combine with the enumeration of crucial properties of the tour. As the approximation guarantee approaches 1, our scheme adjusts the complexity of the considered polytopes accordingly. In the analysis of our approximation scheme, we show that our search space includes a sufficiently good approximation of the optimum. To do so, we develop a novel and general sparsification technique to transform an arbitrary convex polytope into one with a constant number of vertices and, in turn, into one of bounded complexity in the above sense. Hereby, we maintain important properties of the polytope.

We initiate the study of the following natural geometric optimization problem. The input is a set of axis-aligned rectangles in the plane. The objective is to find a set of horizontal line segments of minimum total length so that every rectangle is stabbed by some line segment. A line segment stabs a rectangle if it intersects its left and its right boundary. The problem, which we call Stabbing, can be motivated by a resource allocation problem and has applications in geometric network design. To the best of our knowledge, only special cases of this problem have been considered so far. Stabbing is a weighted geometric set cover problem, which we show to be NP-hard. While for general set cover the best possible approximation ratio is Theta(log n), it is an important field in geometric approximation algorithms to obtain better ratios for geometric set cover problems. Chan et al. [SODA'12] generalize earlier results by Varadarajan [STOC'10] to obtain sub-logarithmic performances for a broad class of weighted geometric set cover instances that are characterized by having low shallow-cell complexity. The shallow-cell complexity of Stabbing instances, however, can be high so that a direct application of the framework of Chan et al. gives only logarithmic bounds. We still achieve a constant-factor approximation by decomposing general instances into what we call laminar instances that have low enough complexity. Our decomposition technique yields constant-factor approximations also for the variant where rectangles can be stabbed by horizontal and vertical segments and for two further geometric set cover problems.

In the classical k-median problem the goal is to select a subset of at most k facilities in order to minimize the total cost of opened facilities and established connections between clients and opened facilities. We consider the capacitated version of the problem, where a single facility may only serve a limited number of clients. We construct approximation algorithms slightly violating the capacities based on rounding a fractional solution to the standard LP. It is well known that the standard LP (even in the case of uniform capacities) has unbounded integrality gap if we only allow violating capacities by a factor smaller than 2, or if we only allow violating the number of facilities by a factor smaller than 2. It is also known that violating capacities by a factor of 2 + ε is sufficient to obtain constant factor approximation of the connection cost in the case of uniform capacities. In this paper we substantially extend this result in the following two directions. On one hand, we obtain a 2+ε capacity violating algorithm to the more general k-facility location problem with uniform capacities, where opening facilities incurs a location specific opening cost. On the other hand, we show that violating capacities by a slightly bigger factor of 3 + ε is sufficient to obtain constant factor approximation of the connection cost also in the case of the non-uniform hard capacitated k-median problem. Our algorithms first use the clustering of Charikar et al. to partition the facilities into sets of total fractional opening at least 1 — 1/ℓ for some fixed ℓ. Then we exploit the technique of Levi, Shmoys, and Swamy developed for the capacitated facility location problem, which is to locally group the demand from clients to obtain a system of single node demand instances. Next, depending on the setting, we either work with stars of facilities (for non-uniform capacities), or we use a dedicated routing tree on the demand nodes (for non-uniform opening cost), to redistribute the demand that cannot be satisfied locally within the clusters.