# A Fully Polynomial Time Approximation Scheme for Packing While Traveling

arXiv: https://arxiv.org/abs/1702.05217 · HTML: https://mlsanity.com/paper/1702.05217/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2017.

## Built on by (most cited first, 1 of 1)

- [Efficiently solving the thief orienteering problem with a max-min ant colony optimization approach](https://mlsanity.com/paper/2109.13103/) (2021)

## Abstract (arXiv)

Understanding 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.