Fare Zone Assignment on Trees

arXiv (Cornell University)

Abstract

Designing fare systems for public transportation networks is a challenging task. A popular approach is to partition the network into fare zones (``zoning'') and fix journey prices depending on the number of traversed zones (``pricing''). In this paper, we focus on finding revenue-optimal solutions to the zoning problem for a given subadditive pricing function. We consider tree networks with $n$ vertices, since trees already pose non-trivial algorithmic challenges. Our main results are efficient algorithms that yield a simple $\mathcal{O}(\log n)$-approximation as well as a more involved $\mathcal{O}(\log n/\log \log n)$-approxi\-ma\-tion. We show that rooted instances, in which all demand arises at a single source, can be solved exactly. We further show APX-hardness for general instances on star graphs. For paths, we prove strong NP-hardness and outline a PTAS. Moreover, we show that computing an optimal solution is in FPT or XP for several natural problem parameters.

Authors 5

1. Martin Hoefer Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University , Aachen , Germany

2. Lennart Kauther Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University , Aachen , Germany

3. Philipp Pabst Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University , Aachen , Germany

4. Britta Peis Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University , Aachen , Germany

5. Khai Van Tran Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University , Aachen , Germany