A Fully Polynomial Time Approximation Scheme for Packing While Traveling

Frank Neumann*, Sergey Polyakovskiy, Martin Skutella, Leen Stougie, Junhua Wu

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

43 Downloads (Pure)

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 languageEnglish
Title of host publicationAlgorithmic Aspects of Cloud Computing
Subtitle of host publication4th International Symposium, ALGOCLOUD 2018, Helsinki, Finland, August 20–21, 2018, Revised Selected Papers
EditorsVassilios S. Verykios, Yann Disser
PublisherSpringer Verlag
Pages59-72
Number of pages14
ISBN (Electronic)9783030197599
ISBN (Print)9783030197582
DOIs
Publication statusPublished - 2019
Event4th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018 - Helsinki, Finland
Duration: 20 Aug 201821 Aug 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11409 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018
Country/TerritoryFinland
CityHelsinki
Period20/08/1821/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.

Fingerprint

Dive into the research topics of 'A Fully Polynomial Time Approximation Scheme for Packing While Traveling'. Together they form a unique fingerprint.

Cite this