A (9+ε, 9+ε)-approximate Pareto set for the Traveling Thief Problem and a (2e+ε)-approximation for Weighted TSP are computable in polynomial time.
The travelling thief problem: The first step in the transition from theoretical problems to realistic problems
4 Pith papers cite this work, alongside 141 external citations. Polarity classification is still indexing.
4
Pith papers citing it
141
external citations · external index
citation-role summary
background 1
citation-polarity summary
years
2026 4roles
background 1polarities
unclear 1representative citing papers
CoEvo-AHD is an LLM-driven dual-population co-evolutionary method for automated heuristic design in bi-component coupled combinatorial optimization that achieves competitive results on TTP and TPP.
New O(n²) dynamic programming algorithm for path-metric TTP tour optimization with fixed packing, plus NP-hardness on stars and constant-factor approximations for star and general metrics with linear costs.
Introduces TTP with time windows, creates new benchmarks from existing TTP instances, and shows a new heuristic outperforms adapted TSP and TTP methods on many instances.
citing papers explorer
-
Approximation Algorithms for the Traveling Thief Problem
A (9+ε, 9+ε)-approximate Pareto set for the Traveling Thief Problem and a (2e+ε)-approximation for Weighted TSP are computable in polynomial time.
-
LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization
CoEvo-AHD is an LLM-driven dual-population co-evolutionary method for automated heuristic design in bi-component coupled combinatorial optimization that achieves competitive results on TTP and TPP.
-
Effective Traveling for Metric Instances of the Traveling Thief Problem
New O(n²) dynamic programming algorithm for path-metric TTP tour optimization with fixed packing, plus NP-hardness on stars and constant-factor approximations for star and general metrics with linear costs.
-
The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics
Introduces TTP with time windows, creates new benchmarks from existing TTP instances, and shows a new heuristic outperforms adapted TSP and TTP methods on many instances.