{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,1]],"date-time":"2024-09-01T05:07:50Z","timestamp":1725167270929},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.24963\/ijcai.2020\/169","type":"proceedings-article","created":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T12:12:10Z","timestamp":1594210330000},"page":"1216-1222","source":"Crossref","is-referenced-by-count":3,"title":["Optimal Region Search with Submodular Maximization"],"prefix":"10.24963","author":[{"given":"Xuefeng","family":"Chen","sequence":"first","affiliation":[{"name":"University of New South Wales, Australia"}]},{"given":"Xin","family":"Cao","sequence":"additional","affiliation":[{"name":"University of New South Wales, Australia"}]},{"given":"Yifeng","family":"Zeng","sequence":"additional","affiliation":[{"name":"Northumbria University, UK"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Australia"}]},{"given":"Bin","family":"Yao","sequence":"additional","affiliation":[{"name":"Shanghai Jiaotong University, China"}]}],"member":"10584","event":{"number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-PRICAI-2020","name":"Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}","start":{"date-parts":[[2020,7,11]]},"theme":"Artificial Intelligence","location":"Yokohama, Japan","end":{"date-parts":[[2020,7,17]]}},"container-title":["Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T02:13:42Z","timestamp":1594260822000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2020\/169"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2020\/169","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}