2019
A Fully Polynomial Time Approximation Scheme for Packing While Traveling
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| doi.org/10.1007/978-3-030-19759-9_5 | |
| Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence | |
| 4th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018 | |
| Organisation | Evolutionary Intelligence |
|
Neumann, F., Polyakovskiy, S., Skutella, M., Stougie, L., & Wu, J. (2019). A Fully Polynomial Time Approximation Scheme for Packing While Traveling. In International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018 (pp. 59–72). doi:10.1007/978-3-030-19759-9_5 |
|
