On the complexity of the highway pricing problem

Grigoriev, Alexander and Loon van, Joyce and Uetz, Marc (2010) On the complexity of the highway pricing problem. In: 36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010, 23-29 Jan, 2010, Špindleruv Mlýn, Czech Republic.

PDF
Restricted to UT campus only: Request a copy
225Kb

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.
Item Type:	Conference or Workshop Item
Copyright:	© 2010 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/69653
Official URL:	http://dx.doi.org/10.1007/978-3-642-11266-9_39
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page