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.