提出公平公交站点布局新算法，兼顾公平性与效率。
Fair Transit Stop Placement: A Clustering Perspective and Beyond
- 将公交站点问题映射为公平聚类，利用聚类近似解保障公平性。
- 证明公平性下界为1.366，现有聚类方法最优仅能逼近3倍。
- 设计可调参数算法，在公平性与集体稳定性间灵活权衡。
我们研究一般度量空间中的公共交通站点布局（TrSP）问题，其中出行者可在起点终点间直接步行或通过选定的中转站乘坐接驳服务。从公正性视角出发，基于合理代表（JR）和核心（core）概念，揭示了该问题与公平聚类间的结构性对应关系。具体地，我们证明：聚类中比例公平性的常数倍近似解，可转化为核心性质的双参数常数倍近似。我们建立了JR问题的近似下界为1.366，并进一步证明任何聚类算法无法在优于3倍的因子内近似JR。超越聚类框架，我们提出扩展代价算法（Expanding Cost Algorithm），实现对JR的紧致2.414-近似，但不保证核心性质。为此，我们引入参数化算法，可在上述两种策略间插值，实现JR与核心之间的可调权衡。最后，我们基于小市场公共拼车数据进行了实验分析。
原文摘要 · Abstract (English)
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 biparameterized 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。