Abstract
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.
Original language | English |
---|---|
Title of host publication | Algorithmic Aspects of Cloud Computing |
Subtitle of host publication | 4th International Symposium, ALGOCLOUD 2018, Helsinki, Finland, August 20–21, 2018, Revised Selected Papers |
Editors | Vassilios S. Verykios, Yann Disser |
Publisher | Springer Verlag |
Pages | 59-72 |
Number of pages | 14 |
ISBN (Electronic) | 9783030197599 |
ISBN (Print) | 9783030197582 |
DOIs | |
Publication status | Published - 2019 |
Event | 4th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018 - Helsinki, Finland Duration: 20 Aug 2018 → 21 Aug 2018 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 11409 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 4th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018 |
---|---|
Country/Territory | Finland |
City | Helsinki |
Period | 20/08/18 → 21/08/18 |
Funding
Acknowledgements. The first, second, and fifth author were supported by Australian Research Council grants DP130104395 and DP140103400. The third author is supported by the Einstein Foundation Berlin in the framework of Matheon.