A Fully Polynomial Time Approximation Scheme for Packing While Traveling

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

doi:10.1007/978-3-030-19759-9_5

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 proceeding › Conference contribution › Academic › peer-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 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	https://doi.org/10.1007/978-3-030-19759-9_5
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.

Access to Document

10.1007/978-3-030-19759-9_5

A Fully Polynomial Time Approximation Scheme for Packing While TravelingFinal published version, 302 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

Neumann, F., Polyakovskiy, S., Skutella, M., Stougie, L., & Wu, J. (2019). A Fully Polynomial Time Approximation Scheme for Packing While Traveling. In V. S. Verykios, & Y. Disser (Eds.), Algorithmic Aspects of Cloud Computing: 4th International Symposium, ALGOCLOUD 2018, Helsinki, Finland, August 20–21, 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 et al. / A Fully Polynomial Time Approximation Scheme for Packing While Traveling. Algorithmic Aspects of Cloud Computing: 4th International Symposium, ALGOCLOUD 2018, Helsinki, Finland, August 20–21, 2018, Revised Selected Papers. editor / Vassilios S. Verykios ; Yann Disser. 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",

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 = "Verykios, {Vassilios S.} and Yann Disser",

booktitle = "Algorithmic Aspects of Cloud Computing",

address = "Germany",

note = "4th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018 ; Conference date: 20-08-2018 Through 21-08-2018",

}

Neumann, F, Polyakovskiy, S, Skutella, M, Stougie, L & Wu, J 2019, A Fully Polynomial Time Approximation Scheme for Packing While Traveling. in VS Verykios & Y Disser (eds), Algorithmic Aspects of Cloud Computing: 4th International Symposium, ALGOCLOUD 2018, Helsinki, Finland, August 20–21, 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 et al.
Algorithmic Aspects of Cloud Computing: 4th International Symposium, ALGOCLOUD 2018, Helsinki, Finland, August 20–21, 2018, Revised Selected Papers. ed. / Vassilios S. Verykios; Yann Disser. 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 proceeding › Conference contribution › Academic › peer-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

Y1 - 2019

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

AN - SCOPUS:85065775034

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

A2 - Verykios, Vassilios S.

A2 - Disser, Yann

PB - Springer Verlag

T2 - 4th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018

Y2 - 20 August 2018 through 21 August 2018

ER -

Neumann F, Polyakovskiy S, Skutella M, Stougie L, Wu J. A Fully Polynomial Time Approximation Scheme for Packing While Traveling. In Verykios VS, Disser Y, editors, Algorithmic Aspects of Cloud Computing: 4th International Symposium, ALGOCLOUD 2018, Helsinki, Finland, August 20–21, 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)). Epub 2019 Apr 28. doi: 10.1007/978-3-030-19759-9_5

A Fully Polynomial Time Approximation Scheme for Packing While Traveling

Abstract

Publication series

Conference

Funding

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this