Optimal Region Search with Submodular Maximization

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

*Corresponding author for this work

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

4 Citations (Scopus)
5 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the Twenty-ninth International Joint Conference on Artificial Intelligence
Place of PublicationPalo Alto
PublisherInternational Joint Conferences on Artificial Intelligence
Pages1216-1222
Number of pages7
ISBN (Print)9780999241165
DOIs
Publication statusPublished - Jul 2020
EventIJCAI-PRICAI2020, the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence! IJCAI-PRICAI2020 - Yokahama, Japan
Duration: 7 Jan 202115 Jan 2021
https://ijcai20.org/

Conference

ConferenceIJCAI-PRICAI2020, the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence! IJCAI-PRICAI2020
Country/TerritoryJapan
CityYokahama
Period7/01/2115/01/21
Internet address

Fingerprint

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

Cite this