Poster: An FPTAS for Shortest-Longest Path Problem
Jianwei Zhang, Xin Li, Bowen Cui, Chunling Yang · 2024
Motivated by multi-domain Service Function Chain (SFC) orchestration, we define the Shortest-Longest Path (SLP) problem, prove its hardness, and design an efficient Fully Polynomial Time Approximation Scheme (FPTAS) using the scaling and rounding technique to compute an approximation solution with provable performance guarantee.