Optimal Region Search with Submodular Maximization

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationIJCAI-PRICAI 2020
Subtitle of host publicationProceedings of the Twenty-ninth International Joint Conference on Artificial Intelligence
Place of PublicationPalo Alto
PublisherAssociation for the Advancement of Artificial Intelligence Press
Number of pages7
Publication statusAccepted/In press - 19 Apr 2020
EventInternational Joint Conference on Artificial Intelligence -
Duration: 5 Jan 202110 Jan 2021


ConferenceInternational Joint Conference on Artificial Intelligence


Dive into the research topics of 'Optimal Region Search with Submodular Maximization'. Together they form a unique fingerprint.

Cite this