TY - GEN
T1 - A Fully Polynomial Time Approximation Scheme for Packing While Traveling
AU - Neumann, Frank
AU - Polyakovskiy, Sergey
AU - Skutella, Martin
AU - Stougie, Leen
AU - Wu, Junhua
PY - 2019
Y1 - 2019
N2 - Understanding the interaction between different combinatorial optimization problems is a challenging task of high relevance for numerous real-world applications including modern computer and memory architectures as well as high performance computing. Recently, the Traveling Thief Problem (TTP), as a combination of the classical traveling salesperson problem and the knapsack problem, has been introduced to study these interactions in a systematic way. We investigate the underlying non-linear Packing While Traveling Problem (PWTP) of the TTP where items have to be selected along a fixed route. We give an exact dynamic programming approach for this problem and a fully polynomial time approximation scheme (FPTAS) when maximizing the benefit that can be gained over the baseline travel cost. Our experimental investigations show that our new approaches outperform current state-of-the-art approaches on a wide range of benchmark instances.
AB - Understanding the interaction between different combinatorial optimization problems is a challenging task of high relevance for numerous real-world applications including modern computer and memory architectures as well as high performance computing. Recently, the Traveling Thief Problem (TTP), as a combination of the classical traveling salesperson problem and the knapsack problem, has been introduced to study these interactions in a systematic way. We investigate the underlying non-linear Packing While Traveling Problem (PWTP) of the TTP where items have to be selected along a fixed route. We give an exact dynamic programming approach for this problem and a fully polynomial time approximation scheme (FPTAS) when maximizing the benefit that can be gained over the baseline travel cost. Our experimental investigations show that our new approaches outperform current state-of-the-art approaches on a wide range of benchmark instances.
UR - http://www.scopus.com/inward/record.url?scp=85065775034&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85065775034&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-19759-9_5
DO - 10.1007/978-3-030-19759-9_5
M3 - Conference contribution
AN - SCOPUS:85065775034
SN - 9783030197582
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 59
EP - 72
BT - Algorithmic Aspects of Cloud Computing
A2 - Verykios, Vassilios S.
A2 - Disser, Yann
PB - Springer Verlag
T2 - 4th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018
Y2 - 20 August 2018 through 21 August 2018
ER -