Paper Info
Title
Constrained Path Search with Submodular Function Maximization
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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\alpha$</tex> -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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\alpha$</tex> -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.
Year
DOI
Venue
2022
10.1109/ICDE53745.2022.00029
2022 IEEE 38th International Conference on Data Engineering (ICDE)
Keywords
DocType
ISSN
constrained path search,submodular maximization
Conference
1063-6382
ISBN
Citations 
PageRank 
978-1-6654-0884-4
0
0.34
References 
Authors
22
7
Name
Order
Citations
PageRank
Xuefeng Chen1394.55
xin cao283741.10
Yifeng Zeng341543.27
Yixiang Fang422723.06
Sibo Wang500.34
Xuemin Lin65585307.32
Liang Feng700.34