A Fully Polynomial Time Approximation Scheme for Packing While Traveling

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

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

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 - 4th International Symposium, ALGOCLOUD 2018, Revised Selected Papers
EditorsYann Disser, Vassilios S. Verykios
PublisherSpringer Verlag
Pages59-72
Number of pages14
ISBN (Print)9783030197582
DOIs
Publication statusPublished - 1 Jan 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
CountryFinland
CityHelsinki
Period20/08/1821/08/18

Fingerprint

Fully Polynomial Time Approximation Scheme
Memory architecture
Computer architecture
Combinatorial optimization
Dynamic programming
Packing
Polynomials
Costs
Knapsack Problem
Real-world Applications
Combinatorial Optimization Problem
Experimental Investigation
Interaction
Dynamic Programming
Baseline
High Performance
Benchmark
Computing
Range of data

Cite this

Neumann, F., Polyakovskiy, S., Skutella, M., Stougie, L., & Wu, J. (2019). A Fully Polynomial Time Approximation Scheme for Packing While Traveling. In Y. Disser, & V. S. Verykios (Eds.), Algorithmic Aspects of Cloud Computing - 4th International Symposium, ALGOCLOUD 2018, Revised Selected Papers (pp. 59-72). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11409 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-19759-9_5
Neumann, Frank ; Polyakovskiy, Sergey ; Skutella, Martin ; Stougie, Leen ; Wu, Junhua. / A Fully Polynomial Time Approximation Scheme for Packing While Traveling. Algorithmic Aspects of Cloud Computing - 4th International Symposium, ALGOCLOUD 2018, Revised Selected Papers. editor / Yann Disser ; Vassilios S. Verykios. Springer Verlag, 2019. pp. 59-72 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{cca1f5074b2945459b716f1c56f1490e,
title = "A Fully Polynomial Time Approximation Scheme for Packing While Traveling",
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{\^A} (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{\^A} (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.",
author = "Frank Neumann and Sergey Polyakovskiy and Martin Skutella and Leen Stougie and Junhua Wu",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/978-3-030-19759-9_5",
language = "English",
isbn = "9783030197582",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "59--72",
editor = "Yann Disser and Verykios, {Vassilios S.}",
booktitle = "Algorithmic Aspects of Cloud Computing - 4th International Symposium, ALGOCLOUD 2018, Revised Selected Papers",
address = "Germany",

}

Neumann, F, Polyakovskiy, S, Skutella, M, Stougie, L & Wu, J 2019, A Fully Polynomial Time Approximation Scheme for Packing While Traveling. in Y Disser & VS Verykios (eds), Algorithmic Aspects of Cloud Computing - 4th International Symposium, ALGOCLOUD 2018, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11409 LNCS, Springer Verlag, pp. 59-72, 4th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018, Helsinki, Finland, 20/08/18. https://doi.org/10.1007/978-3-030-19759-9_5

A Fully Polynomial Time Approximation Scheme for Packing While Traveling. / Neumann, Frank; Polyakovskiy, Sergey; Skutella, Martin; Stougie, Leen; Wu, Junhua.

Algorithmic Aspects of Cloud Computing - 4th International Symposium, ALGOCLOUD 2018, Revised Selected Papers. ed. / Yann Disser; Vassilios S. Verykios. Springer Verlag, 2019. p. 59-72 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11409 LNCS).

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

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/1/1

Y1 - 2019/1/1

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

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 - 4th International Symposium, ALGOCLOUD 2018, Revised Selected Papers

A2 - Disser, Yann

A2 - Verykios, Vassilios S.

PB - Springer Verlag

ER -

Neumann F, Polyakovskiy S, Skutella M, Stougie L, Wu J. A Fully Polynomial Time Approximation Scheme for Packing While Traveling. In Disser Y, Verykios VS, editors, Algorithmic Aspects of Cloud Computing - 4th International Symposium, ALGOCLOUD 2018, Revised Selected Papers. Springer Verlag. 2019. p. 59-72. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-19759-9_5