MC2LS: Towards Efficient Collective Location Selection in Competition: (Extended Abstract)
Meng Wang, Mengfei Zhao, Hui Li, Jiangtao Cui, Bo Yang, Tao Xue · 2025
Collective Location Selection (CLS) aims to identify$k$optimal sites for facility establishment to collectively maximize user attraction. Traditional CLS approaches often overlook user mobility and inter-facility competition, critical factors in real-world scenarios. This paper introduces MC2LS, the first effort on CLS that addresses these gaps by considering user mobility and peer competition. Solving MC2LS is nontrivial due to its NP-hardness. To overcome the challenge of pruning multi-point users with highly overlapping minimum boundary rectangles (MBRs), we develop a position count threshold and two square-based pruning rules. We propose IQuad-tree, a user-MBR-free index, to benefit the hierarchical and batch-wise properties of the pruning rules. We present an$(1-\frac{1}{e})$-approximate greedy solution to MC2LS, and empirical studies demonstrate the superiority of our proposed solution over the state-of-the-art techniques.