Evaluating FPTASes for the Multi-Objective Shortest Path Problem
Thomas Breugem · 2014
We discuss three FPTASes for the Multi-Objective Shortest Path problem. Two of which are known in the literature, the third is a newly proposed FPTAS, aimed at exploiting small Pareto curves. The FPTASes are analyzed, empirically, based on worst case complexity, average case complexity and smoothed complexity. We also analyze the size of the Pareto curve under different conditions.