Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Pricing on Paths: A PTAS for the Highway Problem
 
conference paper

Pricing on Paths: A PTAS for the Highway Problem

Grandoni, Fabrizio
•
Rothvoss, Thomas  
2011
SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms
Symposium on Discrete Algorithms (SODA 2011)

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,Sitters-'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]. Better approximations are known for a number of special cases. Finding a constant (or better!) approximation algorithm for the general case is a challenging open problem. 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. The same basic approach provides PTASs also for two generalizations of the problem: the tollbooth problem with a constant number of leaves and the \emph{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].

  • Files
  • Details
  • Metrics
Type
conference paper
Author(s)
Grandoni, Fabrizio
Rothvoss, Thomas  
Date Issued

2011

Published in
SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms
Start page

675

End page

684

Subjects

approximation algorithms

•

pricing problems

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Event nameEvent placeEvent date
Symposium on Discrete Algorithms (SODA 2011)

San Francisco, USA

January 22-25, 2011

Available on Infoscience
November 21, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/58000
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés