Constrained Path Search with Submodular Function Maximization

Xuefeng Chen, Xin Cao, Yifeng Zeng, Yixiang Fang, Sibo Wang, Xuemin Lin, Liang Feng

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

2 Citations (Scopus)
16 Downloads (Pure)


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.
Original languageEnglish
Title of host publication2022 IEEE 38th International Conference on Data Engineering (ICDE 2022)
Subtitle of host publication9–11 May 2022, Virtual Event
Place of PublicationPiscataway, NJ
Number of pages13
ISBN (Electronic)9781665408837
ISBN (Print)9781665408844
Publication statusPublished - 9 May 2022
Event38th IEEE International Conference on Data Engineering : (ICDE 2022) - (Virtual) Kuala Lumpur, Malaysia
Duration: 9 May 202212 May 2022

Publication series

NameProceedings of the International Conference on Data Engineering (ICDE)
ISSN (Print)1063-6382
ISSN (Electronic)2375-026X


Conference38th IEEE International Conference on Data Engineering
Abbreviated title(ICDE 2022)
City(Virtual) Kuala Lumpur
Internet address


Dive into the research topics of 'Constrained Path Search with Submodular Function Maximization'. Together they form a unique fingerprint.

Cite this