Prizing on Paths: A PTAS for the Highway Problem

Details Prizing on Paths: A PTAS for the Highway Problem Prizing on Paths: A PTAS for the Highway Problem

2010-04-18

arxiv.org/abs/1004.3051v1

Computer Science

Data Structures and Algorithms

Scientific paper

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(\log n/\log\log n) [Gamzu,Segev-'10], which improves on the previous-best O(\log 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].

Affiliated with

Also associated with

No associations

Rating

Prizing on Paths: A PTAS for the Highway Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Prizing on Paths: A PTAS for the Highway Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prizing on Paths: A PTAS for the Highway Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-377686