TY - GEN
T1 - Packing cars into narrow roads
T2 - 27th Annual European Symposium on Algorithms, ESA 2019
AU - Grandoni, Fabrizio
AU - Wiese, Andreas
N1 - Publisher Copyright:
© Fabrizio Grandoni and Andreas Wiese.
PY - 2019/9
Y1 - 2019/9
N2 - In the Highway problem, we are given a path with n edges (the highway), and a set of m drivers, each one characterized by a subpath and a budget. For a given assignment of edge prices (the tolls), the highway owner collects from each driver the total price of the associated path when it does not exceed drivers’s budget, and zero otherwise. The goal is to choose the prices to maximize the total profit. A PTAS is known for this (strongly NP-hard) problem [Grandoni,Rothvoss-SODA’11,SICOMP’16]. In this paper we study the limited supply generalization of Highway, that incorporates capacity constraints. Here the input also includes a capacity ue ≥ 0 for each edge e; we need to select, among drivers that can afford the required price, a subset such that the number of drivers that use each edge e is at most ue (and we get profit only from selected drivers). To the best of our knowledge, the only approximation algorithm known for this problem is a folklore O(log m) approximation based on a reduction to the related Unsplittable Flow on a Path problem (UFP). The main result of this paper is a PTAS for limited supply highway. As a second contribution, we study a natural generalization of the problem where each driver i demands a different amount di of capacity. Using known techniques, it is not hard to derive a QPTAS for this problem. Here we present a PTAS for the case that drivers have uniform budgets. Finding a PTAS for non-uniform-demand limited supply highway is left as a challenging open problem.
AB - In the Highway problem, we are given a path with n edges (the highway), and a set of m drivers, each one characterized by a subpath and a budget. For a given assignment of edge prices (the tolls), the highway owner collects from each driver the total price of the associated path when it does not exceed drivers’s budget, and zero otherwise. The goal is to choose the prices to maximize the total profit. A PTAS is known for this (strongly NP-hard) problem [Grandoni,Rothvoss-SODA’11,SICOMP’16]. In this paper we study the limited supply generalization of Highway, that incorporates capacity constraints. Here the input also includes a capacity ue ≥ 0 for each edge e; we need to select, among drivers that can afford the required price, a subset such that the number of drivers that use each edge e is at most ue (and we get profit only from selected drivers). To the best of our knowledge, the only approximation algorithm known for this problem is a folklore O(log m) approximation based on a reduction to the related Unsplittable Flow on a Path problem (UFP). The main result of this paper is a PTAS for limited supply highway. As a second contribution, we study a natural generalization of the problem where each driver i demands a different amount di of capacity. Using known techniques, it is not hard to derive a QPTAS for this problem. Here we present a PTAS for the case that drivers have uniform budgets. Finding a PTAS for non-uniform-demand limited supply highway is left as a challenging open problem.
KW - Approximation algorithms
KW - Highway problem
KW - Pricing problems
KW - Unsplittable flow on a path
UR - https://www.scopus.com/pages/publications/85074832484
U2 - 10.4230/LIPIcs.ESA.2019.54
DO - 10.4230/LIPIcs.ESA.2019.54
M3 - Conference contribution
AN - SCOPUS:85074832484
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 27th Annual European Symposium on Algorithms, ESA 2019
A2 - Bender, Michael A.
A2 - Svensson, Ola
A2 - Herman, Grzegorz
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 9 September 2019 through 11 September 2019
ER -