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


Download (528kB) | Preview
Official URL: 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.

Item Type: Book Section
Uncontrolled Keywords: Data Mining: Mining Spatial, Temporal Data Heuristic Search and Game Playing, Combinatorial Search and Optimisation
Subjects: G400 Computer Science
G500 Information Systems
G600 Software Engineering
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Related URLs:
Depositing User: John Coen
Date Deposited: 07 Jul 2020 08:37
Last Modified: 11 May 2023 15:00
URI: https://nrl.northumbria.ac.uk/id/eprint/43672

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics