Abstract
C. Hernandez, H. Zhang, S. Koenig, A. Felner and O. Salzman. Efficient Set Dominance Checks in Multi-Objective Shorter-Path Algorithms via Vectorized Operations [Short Paper]. In Symposium on Combinatorial Search (SoCS), pages (in print), 2024.Abstract: 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 a 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.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.