File(s) under permanent embargo
A Fully Polynomial Time Approximation Scheme for Packing While Traveling
conference contribution
posted on 2019-01-01, 00:00 authored by F Neumann, Sergey PolyakovskiySergey Polyakovskiy, M Skutella, L Stougie, J WuUnderstanding the interactions between different combinatorial optimisation problems in real-world applications is a challenging task. 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 (PWT) problem 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 maximising 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.
History
Event
Algorithmic Aspects of Cloud Computing. Symposium (2018 : Helsinki, Finland)Pagination
59 - 72Publisher
SpringerLocation
Helsinki, FinlandPlace of publication
Cham, SwitzerlandPublisher DOI
Start date
2018-08-20End date
2018-08-21ISBN-13
978-3-030-19759-9Language
engAuthor URL
Publication classification
E1 Full written paper - refereedEditor/Contributor(s)
Y Disser, V VerykiosTitle of proceedings
ALGOCLOUD 2018 : Algorithmic Aspects of Cloud Computing.Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC