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].
There are better approximation results, all based on dynamic programming, for a number of special cases. In @cite_10 a constant approximation is given for the case that all the paths have roughly the same length. An FPTAS is described by Hartline and Koltun @cite_18 for the case that the highway has constant length (i.e., @math ). This was generalized to the case of constant-length paths in @cite_12 . In @cite_12 the authors also present an FPTAS for the case that budgets are upper bounded by a constant. An FPTAS is also known @cite_10 @cite_8 for the case that paths induce a laminar family In a laminar family of paths, two paths which intersect are contained one in the other. .
@cite_18 @cite_10 @cite_12 @cite_8
2292671995 1546311336 1507209274 2060882019
In the highway problem, we are given an @math -edge path 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 to choose 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 @math -hard only recently [K. M. , in Proceedings of the International Symposium on Algorithmic Game Theory (SAGT), 2009, pp. 275--286]. The best-known approximation is @math [I. Gamzu and D. Segev, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2010, pp. 582--593], which improves on the previous best @math approximation [M.-F. Balcan and A. Blum, in Proceedings of the ACM Conference on Electronic Commerce,... We prove the approximation ratio 8 5 for the metric s,t -path-TSP, and more generally for shortest connected T-joins. The algorithm that achieves this ratio is the simple "Best of Many" version of Christofides' algorithm (1976), suggested by An, Kleinberg and Shmoys (2012), which consists in determining the best Christofides s,t -tour out of those constructed from a family @math of trees having a convex combination dominated by an optimal solution x* of the Held-Karp relaxation. They give the approximation guarantee @math for such an s,t -tour, which is the first improvement after the 5 3 guarantee of Hoogeveen's Christofides type algorithm (1991). Cheriyan, Friggstad and Gao (2012) extended this result to a 13 8-approximation of shortest connected T-joins, for |T|≥4. The ratio 8 5 is proved by simplifying and improving the approach of An, Kleinberg and Shmoys that consists in completing x* 2 in order to dominate the cost of "parity correction" for spanning trees. We partition the edge-set of each spanning tree in @math into an s,t -path (or more generally, into a T-join) and its complement, which induces a decomposition of x*. This decomposition can be refined and then efficiently used to complete x* 2 without using linear programming or particular properties of T, but by adding to each cut deficient for x* 2 an individually tailored explicitly given vector, inherent in x*. A simple example shows that the Best of Many Christofides algorithm may not find a shorter s,t -tour than 3 2 times the incidentally common optima of the problem and of its fractional relaxation. We study the unsplittable flow on a path problem (UFP), which arises naturally in many applications such as bandwidth allocation, job scheduling, and caching. Here we are given a path with nonnegative edge capacities and a set of tasks, which are characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. Not surprisingly, this problem has received a lot of attention in the research community. If the demand of each task is at most a small enough fraction δ of the capacity along its subpath (δ-small tasks), then it has been known for a long time [, ICALP 2003] how to compute a solution of value arbitrarily close to the optimum via LP rounding. However, much remains unknown for the complementary case, that is, when the demand of each task is at least some fraction δ > 0 of the smallest capacity of its subpath (δ-large tasks). For this setting a constant factor approximation, improving on an earlier logarithmic approximation, was found only recently [, FOCS 2011]. In this paper we present a PTAS for δ-large tasks, for any constant δ > 0. Key to this result is a complex geometrically inspired dynamic program. Each task is represented as a segment underneath the capacity curve, and we identify a proper maze-like structure so that each corridor of the maze is crossed by only O(1) tasks in the optimal solution. The maze has a tree topology, which guides our dynamic program. Our result implies a 2 + e approximation for UFP, for any constant e > 0, improving on the previously best 7 + e approximation by We remark that our improved approximation algorithm matches the best known approximation ratio for the considerably easier special case of uniform edge capacities. We provide an improved FPTAS for multiobjective shortest paths—a fundamental (NP-hard) problem in multiobjective optimization—along with a new generic method for obtaining FPTAS to any multiobjective optimization problem with non-linear objectives. We show how these results can be used to obtain better approximate solutions to three related problems, multiobjective constrained [optimal] path and non-additive shortest path, that have important applications in QoS routing and in traffic optimization. We also show how to obtain a FPTAS to a natural generalization of the weighted multicommodity flow problem with elastic demands and values that models several realistic scenarios in transportation and communication networks.