Efficient Set Dominance Checks in Multi-Objective Shortest-Path Algorithms via Vectorized Operations


  • Carlos Hernández Ulloa Universidad San Sebastián
  • Han Zhang University of Southern California
  • Sven Koenig University of Southern California
  • Ariel Felner Ben-Gurion University
  • Oren Salzman Technion




In the multi-objective shortest-path problem (MOSP) we are interested in finding paths between two vertices of a graph while considering multiple objectives. A key procedure, which dominates the running time of many state-of-the-art (SOTA) algorithms for MOSP is set dominance checks (SDC). In SDC, we are given a set X of N-dimensional tuples and a new N-dimensional tuple p and we need to determine whether there exists a tuple q in X such that q dominates p (i.e., if every element in q is lower or equal than the corresponding element in p). In this work, we offer a simple-yet-effective approach to perform SDC in a parallel manner, an approach that can be seamlessly integrated with most SOTA MOSP algorithms. Specifically, by storing states in memory dimension-wise and not state-wise, we can exploit vectorized operations offered by ``Single Instruction/Multiple Data'' (SIMD) instructions to efficiently perform SDC on ubiquitous consumer CPUs. Integrating our approach for SDC allows to dramatically improve the runtime of existing MOSP algorithms.