Fair Transit Stop Placement: A Clustering Perspective and Beyond

Haris Aziz, Ling Gai, Yuhang Guo, Jeremy Vollen
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:4517-4548, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-aziz26a, title = {Fair Transit Stop Placement: A Clustering Perspective and Beyond}, author = {Aziz, Haris and Gai, Ling and Guo, Yuhang and Vollen, Jeremy}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {4517--4548}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/aziz26a/aziz26a.pdf}, url = {https://proceedings.mlr.press/v306/aziz26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Fair Transit Stop Placement: A Clustering Perspective and Beyond %A Haris Aziz %A Ling Gai %A Yuhang Guo %A Jeremy Vollen %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-aziz26a %I PMLR %P 4517--4548 %U https://proceedings.mlr.press/v306/aziz26a.html %V 306 %X 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.
APA
Aziz, H., Gai, L., Guo, Y. & Vollen, J.. (2026). Fair Transit Stop Placement: A Clustering Perspective and Beyond. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:4517-4548 Available from https://proceedings.mlr.press/v306/aziz26a.html.

Related Material