On the complexity of the highway pricing problem

Alexander Grigoriev, Joyce van Loon, Marc Jochen Uetz

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

Abstract

The highway pricing problem asks for prices to be determined for segments of a single highway such as to maximize the revenue obtainable from a given set of customers with known valuations. The problem is NP-hard and a recent quasi-PTAS suggests that a PTAS might be in reach. Yet, so far it has resisted any attempt for constant-factor approximation algorithms. We relate the tractability of the problem to structural properties of customers' valuations. We show that the problem becomes NP-hard as soon as the average valuations of customers are not homogeneous, even under further restrictions such as monotonicity. Moreover, we derive an efficient approximation algorithm, parameterized along the inhomogeneity of customers' valuations. Finally, we discuss extensions of our results that go beyond the highway pricing problem.
Original languageUndefined
Title of host publicationSOFSEM 2010: Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science
EditorsA. Muscholl, D. Peleg, B. Pokorný, B. Rumpe
Place of PublicationBerlin
PublisherSpringer
Pages465-476
Number of pages12
ISBN (Print)978-3-642-11265-2
DOIs
Publication statusPublished - Jan 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume5901
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • METIS-270714
  • EWI-17262
  • IR-69653

Cite this

Grigoriev, A., van Loon, J., & Uetz, M. J. (2010). On the complexity of the highway pricing problem. In A. Muscholl, D. Peleg, B. Pokorný, & B. Rumpe (Eds.), SOFSEM 2010: Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science (pp. 465-476). [10.1007/978-3-642-11266-9_39] (Lecture Notes in Computer Science; Vol. 5901). Berlin: Springer. https://doi.org/10.1007/978-3-642-11266-9_39