Hybrid Method for Bounded Cost Check-in Deployments: Theory and Practice
提出混合贪婪算法解决有限预算下最大化覆盖最短路径的难题，理论证明其近似比优于现有下界，并给出基于皮尔逊相关的算法选择准则。
This article introduces the maximum coverage of shortest paths under limited cost (MCLC) problem, a novel optimization task focused on deploying nodes to cover the maximum number of shortest paths within a network under a strict budget. While crucial in many real-world scenarios, this problem is computationally challenging. We propose a novel hybrid greedy (HG) algorithm, which integrates two novel greedy operations—coverage-first and contribution-first—with new refinement techniques. We prove that the proposed HG algorithm achieves a worst case approximation ratio that doubles the state-of-the-art lower bound, a significant theoretical improvement for large-scale networks. To guide practical application, we analyze the tradeoff between coverage and cost-efficiency. We derive a new Pearson correlation-based criterion that accurately predicts when and why our proposed HG approach will outperform other methods, providing a valuable guideline for algorithm selection. Extensive experiments on both synthetic and real-world networks validate our theoretical findings and confirm the practical superiority of our approach.