Constrained Path Search with Submodular Function Maximization

Chen, Xuefeng, Cao, Xin, Zeng, Yifeng, Fang, Yixiang, Wang, Sibo, Lin, Xuemin and Feng, Liang (2022) Constrained Path Search with Submodular Function Maximization. In: 2022 IEEE 38th International Conference on Data Engineering (ICDE 2022): 9–11 May 2022, Virtual Event. roceedings of the International Conference on Data Engineering (ICDE) . IEEE, Piscataway, NJ, pp. 325-337. ISBN 9781665408844, 9781665408837

Preview

Text Constrained Path Search with Submodular Function Maximization.pdf - Accepted Version Download (583kB) | Preview

Abstract

In this paper, we study the problem of constrained path search with submodular function maximization (CPS-SM). We aim to find the path with the best submodular function score under a given constraint (e.g., a length limit), where the submodular function score is computed over the set of nodes in this path. This problem can be used in many applications. For example, tourists may want to search the most diversified path (e.g., a path passing by the most diverse facilities such as parks and museums) given that the traveling time is less than 6 hours. We show that the CPS-SM problem is NP-hard. We first propose a concept called “submodular α -dominance” by utilizing the submodular function properties, and we develop an algorithm with a guaranteed error bound based on this concept. By relaxing the submodular α -dominance conditions, we design another more efficient algorithm that has the same error bound. We also utilize the way of bi-directional path search to further improve the efficiency of the algorithms. We finally propose a heuristic algorithm that is efficient yet effective in practice. The experiments conducted on several real datasets show that our proposed algorithms can achieve high accuracy and are faster than one state-of-the-art method by orders of magnitude.

Actions (login required)

View Item

Downloads