Optimal Region Search with Submodular Maximization

Optimal Region Search with Submodular Maximization

Xuefeng Chen, Xin Cao, Yifeng Zeng, Yixiang Fang, Bin Yao

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1216-1222. https://doi.org/10.24963/ijcai.2020/169

Region search is an important problem in location-based services due to its wide applications. In this paper, we study the problem of optimal region search with submodular maximization (ORS-SM). This problem considers a region as a connected subgraph. We compute an objective value over the locations in the region using a submodular function and a budget value by summing up the costs of edges in the region, and aim to search the region with the largest objective score under a budget value constraint. ORS-SM supports many applications such as the most diversified region search. We prove that the problem is NP-hard and develop two approximation algorithms with guaranteed error bounds. We conduct experiments on two applications using three real-world datasets. The results demonstrate that our algorithms can achieve high-quality solutions and are faster than a state-of-the-art method by orders of magnitude.
Keywords:
Data Mining: Mining Spatial, Temporal Data
Heuristic Search and Game Playing: Combinatorial Search and Optimisation