FPTASes for the Multi-Objective Shortest Path Problem

We discuss two FPTASes for the Multi-Objective Shortest Path problem. The first one is known in the literature, the second is a newly proposed FPTAS, aimed at exploiting small Pareto curves. Together with an exact labeling algorithm, 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.  

Please note: Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.