Pith. sign in

REVIEW 3 minor 29 references

Fare Zone Assignment on Trees

T0 review · 0 major / 3 minor · reviewed 2026-05-16 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read Efficient algorithms approximate revenue-optimal fare zone assignments on tree networks within O(log n / log log n).

desk verdict The paper gives a simple O(log n) approximation plus a tighter O(log n/log log n) one for fare zone assignment on trees under subadditive pricing, with exact solutions for rooted instances and matching hardness results. read the letter →

arxiv 2512.19493 v3 submitted 2025-12-22 cs.DS cs.GTmath.OC

Martin Hoefer , Lennart Kauther , Philipp Pabst , Britta Peis , Khai Van Tran This is my paper · ORCID
classification cs.DScs.GTmath.OC
keywords farezoneassignmentzoningproblemapproximationalgorithmstreenetworkssubadditivepricingrevenuemaximizationpublictransportation
topics The Hierarchy Problem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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

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.

Watch

Extended reading notes

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.

Load-bearing premise

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

Editorial extensions

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.

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 2 assumptions · 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.

assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fare Zone Assignment on Trees." pith.science (2026). https://pith.science/paper/2512.19493

@misc{pith2026251219493,
  author       = {Pith},
  title        = {Pith review of: Fare Zone Assignment on Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2512.19493}},
  note         = {Machine review of arXiv:2512.19493}
}
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.

Figures

Figures reproduced from arXiv: 2512.19493 by the authors.

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. 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 decomposition proce… view at source ↗
Figure 3
Figure 3. An illustration of the construction used [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (7 more)
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]
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 li…
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 t…
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 commoditi…
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]
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]
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]

Discussion (0). Continue with ORCID to comment.

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

Show all 29 references
  1. [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

    2008

  2. [10]

    Derrible

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

    2012

  3. [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

    2010

  4. [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,

  5. [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

    2012

  6. [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

    1983

  7. [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

    2017

  8. [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

    2016

  9. [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 Applie...

    2005

  10. [18]

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

    2004

  11. [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

    2022

  12. [20]

    Otto and N

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

    2017

  13. [21]

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

    2005

  14. [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...

    2024

  15. [23]

    Schöbel and R

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

    2025

  16. [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...

    2024

  17. [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 considern...

  18. [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 p...

  19. [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...

  20. [28]

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

  21. [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 ...

Pith tools

Reviewed May 16, 2026 · model on record in the stance chip above.