Optimal Region Search with Submodular Maximization

Chen, Xuefeng, Cao, Xin, Zeng, Yifeng, Fang, Yixiang and Yao, Bin (2020) Optimal Region Search with Submodular Maximization. In: IProceedings of the Twenty-ninth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence, Palo Alto, pp. 1216-1222. ISBN 9780999241165

Preview

Text ijcai20_tree.pdf Download (528kB) | Preview

Abstract

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.

Actions (login required)

View Item

Downloads