Fare Zone Assignment on Trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911620710531072 |
|---|---|
| author | Hoefer, Martin Kauther, Lennart Pabst, Philipp Peis, Britta Van Tran, Khai |
| author_facet | Hoefer, Martin Kauther, Lennart Pabst, Philipp Peis, Britta Van Tran, Khai |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_19493 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fare Zone Assignment on Trees Hoefer, Martin Kauther, Lennart Pabst, Philipp Peis, Britta Van Tran, Khai Data Structures and Algorithms Computer Science and Game Theory Optimization and Control 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. |
| title | Fare Zone Assignment on Trees |
| topic | Data Structures and Algorithms Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/2512.19493 |