{"ID":2826323,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.19493","arxiv_id":"2512.19493","title":"Fare Zone Assignment on Trees","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.","short_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...","url_abs":"https://arxiv.org/abs/2512.19493","url_pdf":"https://arxiv.org/pdf/2512.19493v3","authors":"[\"Martin Hoefer\",\"Lennart Kauther\",\"Philipp Pabst\",\"Britta Peis\",\"Khai Van Tran\"]","published":"2025-12-22T15:49:24Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.GT\",\"math.OC\"]","methods":"[]","has_code":false}