pith. sign in

arxiv: 2512.19493 · v3 · submitted 2025-12-22 · 💻 cs.DS · cs.GT· math.OC

Fare Zone Assignment on Trees

Martin Hoefer , Lennart Kauther , Philipp Pabst , Britta Peis , Khai Van Tran This is my paper

Pith reviewed 2026-05-16 20:20 UTC · model grok-4.3

classification 💻 cs.DS cs.GTmath.OC
keywords fare zone assignmentzoning problemapproximation algorithmstree networkssubadditive pricingrevenue maximizationpublic transportation
0
0 comments X

The pith

Efficient algorithms approximate revenue-optimal fare zone assignments on tree networks within O(log n / log log n).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies how to partition tree-shaped transportation networks into fare zones to maximize revenue when journey prices depend on the number of zones crossed under a subadditive pricing rule. It gives a straightforward O(log n)-approximation and a refined O(log n / log log n)-approximation for arbitrary demand on trees. Instances in which all demand originates at a single root vertex admit exact optimal solutions. The work also proves APX-hardness on stars, strong NP-hardness on paths together with a PTAS for paths, and places the problem in FPT or XP for several natural parameters.

Core claim

Our main results are efficient algorithms that yield a simple O(log n)-approximation as well as a more involved O(log n/log log n)-approximation. We show that rooted instances 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.

What carries the argument

Tree-structured dynamic programming that assigns zones by merging contiguous segments while respecting subadditive pricing to maximize collected revenue.

If this is right

  • General demand on trees admits logarithmic-factor revenue approximations.
  • Single-source demand on trees permits exact polynomial-time solutions.
  • Even star networks remain APX-hard for zone assignment.
  • Paths, though strongly NP-hard, allow a polynomial-time approximation scheme.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same techniques may extend to graphs of bounded treewidth by replacing tree DP with standard treewidth DP.
  • Transit operators facing approximately tree-like networks and subadditive tariffs could apply the approximations directly.
  • The parameterized results indicate that exact solutions remain tractable when the number of zones or demand points is small.

Load-bearing premise

The network forms a tree and the pricing function is subadditive.

What would settle it

A concrete tree instance with subadditive pricing on which every polynomial-time algorithm achieves revenue strictly worse than O(log n / log log n) times the optimum, or a rooted instance whose optimum cannot be computed in polynomial time.

Figures

Figures reproduced from arXiv: 2512.19493 by Britta Peis, Khai Van Tran, Lennart Kauther, Martin Hoefer, Philipp Pabst.

Figure 1
Figure 1. Figure 1: An instance of FZA with eight commodities, each with [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A decomposition T = {T1, . . . , T6} of some fragment T. The vertices {v1, . . . , v5} are border vertices, and the skeleton (bold blue edges) is the subtree spanned by the border vertices. Three commodities (indicated by light blue dotted lines) lie in T entirely. Only commodity 1 is not separated by T . 4.1 The Skeleton of a Fragment Recall that we can treat each fragment on each level j of the decomposi… view at source ↗
Figure 3
Figure 3. Figure 3: An illustration of the construction used [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An example of the Single Density algorithm with unit-weight com [PITH_FULL_IMAGE:figures/full_fig_p024_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An almost balanced 6-decomposition T = {T1, . . . , T6} of some fragment T. The larger red vertices {v1, . . . , v5} are border vertices, and the skeleton (shown bold and in blue) is the subtree spanned by the border vertices. Three commodities 1, 2, 3 (indicated by light blue dotted lines) lie entirely in T. Only commodity 1 is not separated by T . To compute the cut set FALG, we run two different algorit… view at source ↗
Figure 6
Figure 6. Figure 6: The instance I(σ1, p, r) constructed in the distribution phase of the al￾gorithm for the skeleton case. The considered fragment T consists of five seg￾ments σ1, . . . , σ5 with prices stemming from the guessing phase. Bold, solid lines represent active segments while the inactive segments (σ2 and σ5) correspond to dashed lines. I(σ, p, r) contains commodities 2 and 4. Commodity 1 is not contained as its ot… view at source ↗
Figure 7
Figure 7. Figure 7: An illustration of the con￾struction used in the proof of Theorem 4 for the formula φ = (x1 ∨ x¯2) ∧ (¯x1 ∨ x¯2). Solid lines indicate clause commodities en￾forcing a valid variable assign￾ment. The remaining commodi￾ties (indicated by solid lines) are clause commodities. v x1 x¯1 x2 x¯2 Proof (of Theorem 4). Given a Boolean formula φ with variables x1, ..., xn and clauses C1, ..., Cm (consisting of two li… view at source ↗
Figure 8
Figure 8. Figure 8: An illustration of the variable-assignment gadget corresponding to literal [PITH_FULL_IMAGE:figures/full_fig_p047_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Depicted are the commodities enforcing a valid assignment in the proof of [PITH_FULL_IMAGE:figures/full_fig_p047_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: FZA-instance constructed in the proof of Theorem 5 for [PITH_FULL_IMAGE:figures/full_fig_p048_10.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies the fare zone assignment problem on tree networks with n vertices under subadditive pricing functions, with the goal of maximizing revenue by partitioning the tree into zones. It presents a simple O(log n)-approximation algorithm and a more involved O(log n / log log n)-approximation for general instances, an exact algorithm for rooted instances (single-source demand), APX-hardness on stars, strong NP-hardness on paths together with a PTAS, and FPT/XP membership for several natural parameters.

Significance. If the claims hold, the work provides useful algorithmic tools for a practical transportation design problem on trees. The exact algorithm for rooted instances and the parameterized results are directly applicable to special cases, while the approximation guarantees and hardness results (including the PTAS on paths) delineate tractability boundaries. The use of standard techniques such as tree DP and rounding is a strength, but the results remain conditional on the subadditive pricing and tree topology assumptions.

minor comments (3)
  1. Abstract: the hyphenation in 'O(log n/log log n)-approxi-ma-tion' should be removed for readability.
  2. The manuscript would benefit from an explicit statement of the running times of the approximation algorithms and the PTAS, preferably in the abstract or introduction.
  3. It is unclear from the abstract whether the O(log n / log log n) approximation improves on the simple O(log n) algorithm in all regimes or only asymptotically; a short comparison paragraph would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and recommendation for minor revision. We appreciate the recognition that our O(log n) and O(log n/log log n) approximation algorithms, exact algorithm for rooted instances, APX-hardness on stars, strong NP-hardness and PTAS on paths, and FPT/XP results provide useful tools for the fare zone assignment problem on trees under subadditive pricing.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's core results consist of standard algorithmic constructions: dynamic programming for exact solutions on rooted tree instances, greedy set-cover-style rounding yielding the O(log n) approximation, a more refined rounding or LP-based method for the O(log n / log log n) bound, and classical NP-hardness reductions (APX-hardness on stars, strong NP-hardness on paths). These steps are derived from first-principles analysis of the subadditive pricing objective on trees and do not reduce to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain is self-contained against external benchmarks of tree DP and approximation algorithms.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the assumption that the input is a tree network and the pricing function is subadditive; no free parameters or invented entities are introduced.

axioms (2)
  • domain assumption The transportation network is a tree with n vertices.
    Explicitly stated as the focus of the paper since trees pose non-trivial challenges.
  • domain assumption The pricing function is subadditive.
    Given as part of the problem setup for revenue optimization.

pith-pipeline@v0.9.0 · 5484 in / 1176 out tokens · 27647 ms · 2026-05-16T20:20:39.877850+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Angeloudis and D

    P. Angeloudis and D. Fisk. Large subway systems as complex networks.Physica A: Statistical Mechanics and its Applications, 367:553–558, 2006

    work page 2006

  2. [2]

    Ausiello, P

    G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi.Complexity and Approximation. 2003

    work page 2003

  3. [3]

    Babel and H

    L. Babel and H. Kellerer. Design of tariff zones in public transportation networks: theoretical results and heuristics.Mathematical Methods of Operations Research, 58(3):359–374, December 2003

    work page 2003

  4. [4]

    Balcan, A

    M.-F. Balcan, A. Blum, and Y. Mansour. Item pricing for revenue maximization. InProceedings of the 9th ACM Conference on Electronic Commerce, EC ’08, page 50–59, New York, NY, USA, 2008. Association for Computing Machinery

    work page 2008

  5. [5]

    Böhnlein, S

    T. Böhnlein, S. Kratsch, and O. Schaudt. Revenue maximization in Stackelberg Pricing Games: beyond thecombinatorial setting.Math. Program., 187(1):653–695, 2021

    work page 2021

  6. [6]

    Briest, M

    P. Briest, M. Hoefer, and P. Krysta. Stackelberg Network Pricing Games. In S. Al- bers and P. Weil, editors,25th International Symposium on Theoretical Aspects of Computer Science, volume 1 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 133–142, Dagstuhl, Germany, 2008. Schloss Dagstuhl – Leibniz- Zentrum für Informatik

    work page 2008

  7. [7]

    Briest and P

    P. Briest and P. Krysta. Single-minded unlimited supply pricing on sparse in- stances. InProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA ’06, page 1093–1102, USA, 2006. Society for Industrial and Applied Mathematics

    work page 2006

  8. [8]

    Cardinal, E

    J. Cardinal, E. D. Demaine, S. Fiorini, G. Joret, S. Langerman, I. Newman, and O. Weimann. The stackelberg minimum spanning tree game. InProceedings of the 10th International Conference on Algorithms and Data Structures, WADS’07, page 64–76, Berlin, Heidelberg, 2007. Springer-Verlag

    work page 2007

  9. [9]

    Cheung and C

    M. Cheung and C. Swamy. Approximation algorithms for single-minded envy-free profit-maximization problems with limited supply. In2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 35–44, 2008

    work page 2008

  10. [10]

    Derrible

    S. Derrible. Network centrality of metro systems.PLOS ONE, 7(7):1–10, 07 2012

    work page 2012

  11. [11]

    Derrible and C

    S. Derrible and C. Kennedy. The complexity and robustness of metro networks. Physica A: Statistical Mechanics and its Applications, 389(17):3678–3691, 2010

    work page 2010

  12. [12]

    Elbassioni, R

    K. Elbassioni, R. Raman, S. Ray, and R. Sitters. On profit-maximizing pricing for the highway and tollbooth problems. InProceedings of the 2nd International Sym- posium on Algorithmic Game Theory, SAGT ’09, page 275–286, Berlin, Heidelberg,

    work page

  13. [13]

    Elbassioni, R

    K. Elbassioni, R. Raman, S. Ray, and R. Sitters. On the complexity of the highway problem.Theoretical Computer Science, 460:70–77, 2012

    work page 2012

  14. [14]

    G. N. Frederickson and D. B. Johnson. Finding kth paths and p-centers by gen- erating and searching good data structures.Journal of Algorithms, 4(1):61–80, 1983

    work page 1983

  15. [15]

    Gamzu and D

    I. Gamzu and D. Segev. A sublogarithmic approximation for tollbooth pricing on trees.Mathematics of Operations Research, 42(2):377–388, 2017

    work page 2017

  16. [16]

    Grandoni and T

    F. Grandoni and T. Rothvoß. Pricing on paths: A ptas for the highway problem. SIAM Journal on Computing, 45(2):216–231, 2016

    work page 2016

  17. [17]

    Guruswami, J

    V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSh- erry. On profit-maximizing envy-free pricing. InProceedings of the Sixteenth An- nual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05, page 1164–1173, USA, 2005. Society for Industrial and Applied Mathematics. Fare Zone Assignment on Trees 15

    work page 2005

  18. [18]

    H. W. Hamacher and A. Schöbel. Design of zone tariff systems in public trans- portation.Operations Research, 52(6):897–908, 2004

    work page 2004

  19. [19]

    Müller, K

    S. Müller, K. Haase, and L. Reyes-Rubiano. Revenue maximizing tariff zone plan- ning for public transportation.SSRN Electronic Journal, 01 2022

    work page 2022

  20. [20]

    Otto and N

    B. Otto and N. Boysen. Zone-based tariff design in public transportation networks. Networks, 69(4):349–366, 2017

    work page 2017

  21. [21]

    S. Roch, G. Savard, and P. Marcotte. An approximation algorithm for Stackelberg network pricing.Networks, 46(1):57–67, 2005

    work page 2005

  22. [22]

    Schiewe, A

    P. Schiewe, A. Schöbel, and R. Urban. A Bi-Objective Optimization Model for Fare Structure Design in Public Transport. In P. C. Bouman and S. C. Konto- giannis, editors,24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024), volume 123 ofOpen Ac- cess Series in Informatics (OASIcs), pages 15:1–15:19, ...

    work page 2024

  23. [23]

    Schöbel and R

    A. Schöbel and R. Urban. Fare structure design in public transport, 2025

    work page 2025

  24. [24]

    Turko and J

    A. Turko and J. Byrka. Sublogarithmic approximation for tollbooth pricing on a cactus. In G. Schäfer and C. Ventre, editors,Algorithmic Game Theory, pages 297–314, Cham, 2024. Springer Nature Switzerland. 16 Hoefer, Kauther, Pabst, Peis, Tran A Parameterized Algorithms for FZA on Paths In this section, we present parameterized algorithms for FZA when rest...

    work page 2024

  25. [25]

    thinned-out

    =n O(cong(I)) table entries, as clearly we haveui + 3∈ O(n)for alli. To compute a single table entry, we need to choose the best table entry for all possible values ofY| K3(e(j)), and compute the marginal gain made by the new edgee (j). For the first part, we need to considernO(cong(I)) many entries, as |K3(e(j))| ≤cong(I). Computing the marginal gain mad...

    work page

  26. [26]

    Combining this withui ≤8we conclude thatE[rev i(Fj)]≥ 1 3200 revi(F ∗). ⊓ ⊔ D Sublogarithmic Approximation Algorithm This section is dedicated to the full proof of the approximation guarantee and running time of the algorithm for the sublogarithmic approximation. That is, we prove Theorem 3.There is an efficient algorithm to compute anO logn log logn -app...

    work page

  27. [27]

    nice” commodities for which the randomization has some “favorable

    Lastly, for every commodityi, we denote byI(P i)the set ofinner segments, i.e., all segmentsσ∈Σ(S)for whichσ⊆P i. We call the remaining (at most two) segments thatPi intersectsouter segments ofi. We partitionMinto two sets of commoditiesi, based on whetherF∗ makes more cuts on the inner or outer segments ofi. Formally those sets are defined as M(i) ={i∈M|...

    work page

  28. [28]

    Three cuts in block (B) and no cuts in blocks (A) and (C)

    work page

  29. [29]

    For now, we assume thatMis sufficiently large such that each subpath corre- sponding to a variable-assignment gadget contains exactly3cuts

    One cut in each block (A), (B), and (C). For now, we assume thatMis sufficiently large such that each subpath corre- sponding to a variable-assignment gadget contains exactly3cuts. We give the details on how to chooseMlater. In the following, we interpret literallasTRUE if we choose the cut pattern(0−3−0)w.r.t. the blocks (A), (B), and (C) and otherwise, ...

    work page