In the highway problem, we are given an n-edge line graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the associated path, when it does not exceed the budget of the driver, and zero otherwise. The goal is choosing weights so as to maximize the profit. A lot of research has been devoted to this apparently simple problem. The highway problem was shown to be strongly NP-hard only recently [Elbassioni,Raman,Ray-'09]. The best-known approximation is O( n n) [Gamzu,Segev-'10], which improves on the previous-best O( n) approximation [Balcan,Blum-'06]. In this paper we present a PTAS for the highway problem, hence closing the complexity status of the problem. Our result is based on a novel randomized dissection approach, which has some points in common with Arora's quadtree dissection for Euclidean network design [Arora-'98]. The basic idea is enclosing the highway in a bounding path, such that both the size of the bounding path and the position of the highway in it are random variables. Then we consider a recursive O(1)-ary dissection of the bounding path, in subpaths of uniform optimal weight. Since the optimal weights are unknown, we construct the dissection in a bottom-up fashion via dynamic programming, while computing the approximate solution at the same time. Our algorithm can be easily derandomized. We demonstrate the versatility of our technique by presenting PTASs for two variants of the highway problem: the tollbooth problem with a constant number of leaves and the maximum-feasibility subsystem problem on interval matrices. In both cases the previous best approximation factors are polylogarithmic [Gamzu,Segev-'10,Elbassioni,Raman,Ray,Sitters-'09].
The technique behind our PTAS resembles Arora's quadtree dissection for Euclidean network design @cite_14 . The basic idea there is enclosing the set of input points into a bounding box, then recursively partition it in a constant number of boxes. This dissection is then randomly shifted. On the resulting random dissection, one applies dynamic programming. We similarly enclose the highway in a bounding path, and partition the latter. Like in Arora's approach, the dissection is randomly shifted. Differently from that case and crucially for our analysis, the size of the bounding path is a random variable as well. Another major difference is that the dissection is not uniform with respect to input properties, but with respect to the optimal weights: for this reason the dissection is constructed in a bottom-up, rather than top-down, fashion via dynamic programming (while computing the approximate solution in parallel).
@cite_14
2165142526
We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed c > 1 and given any n nodes in R 2 , a randomized version of the scheme finds a (1 + 1 c )-approximation to the optimum traveling salesman tour in O(n (log n ) O(c) ) time. When the nodes are in R d , the running time increases to O(n (log n ) (O( d c)) d-1 ). For every fixed c, d the running time is n • poly(log n ), that is nearly linear in n . The algorithmm can be derandomized, but this increases the running time by a factor O(n d ). The previous best approximation algorithm for the problem (due to Christofides) achieves a 3 2-aproximation in polynomial time. We also give similar approximation schemes for some other NP-hard Euclidean problems: Minimum Steiner Tree, k -TSP, and k -MST. (The running times of the algorithm for k -TSP and k -MST involve an additional multiplicative factor k .) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. We also give efficient approximation schemes for Euclidean Min-Cost Matching, a problem that can be solved exactly in polynomial time. All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as e p for p ≥ 1 or other Minkowski norms). They also have simple parallel (i.e., NC) implementations.