An FPTAS for Shortest-Longest Path Problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929704414478336 |
|---|---|
| author | Zhang, Jianwei |
| author_facet | Zhang, Jianwei |
| contents | 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 dynamic programming (DP) and scaling and rounding (SR) techniques to compute an approximation solution with provable performance guarantee. The SLP problem and its solution algorithm have theoretical significance in multicriteria optimization and also have application potential in QoS routing and multi-domain network resource allocation scenarios. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_13488 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An FPTAS for Shortest-Longest Path Problem Zhang, Jianwei Networking and Internet Architecture 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 dynamic programming (DP) and scaling and rounding (SR) techniques to compute an approximation solution with provable performance guarantee. The SLP problem and its solution algorithm have theoretical significance in multicriteria optimization and also have application potential in QoS routing and multi-domain network resource allocation scenarios. |
| title | An FPTAS for Shortest-Longest Path Problem |
| topic | Networking and Internet Architecture |
| url | https://arxiv.org/abs/2404.13488 |