Fair Transit Stop Placement: A Clustering Perspective and Beyond

We study the transit stop placement (TrSP) problem in general metric spaces, where agents travel between source–destination pairs and may either walk directly or utilize a shuttle service via selected transit stops. We investigate fairness in TrSP through the lens of justified representation (JR) and the core, and uncover a structural correspondence with fair clustering. Specifically, we show that a constant-factor approximation to proportional fairness in clustering can be used to guarantee a constant-factor bi-parameterized approximation to core. We establish a lower bound of $1.366$ on the approximability of JR, and moreover show that no clustering algorithm can approximate JR within a factor better than $3$. Going beyond clustering, we propose the Expanding Cost Algorithm, which achieves a tight $2.414$-approximation for JR, but does not give any bounded core guarantee. In light of this, we introduce a parameterized algorithm that interpolates between these approaches, and enables a tunable trade-off between JR and core. Finally, we complement our results with an experimental analysis using small-market public carpooling data.

We study where to place a limited number of public transit stops in transportation networks so that the placement is fair to agents, who travel between origin–destination pairs. We adopt proportional fairness notions, including justified representation and the core, under which groups of agents with similar travel needs are entitled to influence the outcome in proportion to their size. We build up connections between this task and fair clustering problem. We design approximation algorithms for achieving justified representation and the core and validate our methods on real public carpooling data.