Submodularity and the traveling salesman problem

Submodularity and the traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20001855
Country: Netherlands
Volume: 114
Issue: 3
Start Page Number: 489
End Page Number: 508
Publication Date: May 1999
Journal: European Journal of Operational Research
Authors:
Abstract:

In this paper we investigate the relationship between traveling salesman tour lengths and submodular functions. This work is motivated by the one warehouse multi-retailer inventory/distribution problem with traveling salesman tour vehicle routing costs. Our goal is to find a submodular function whose values are close to those of optimal tour lengths through a central warehouse and a group of retailers. Our work shows that a submodular approximation to traveling salesman tour lengths whose error is bounded by a constant does not exist. However, we present heuristics that have errors which grow slowly with the number of retailers for the traveling salesman problem in the Euclidean plane. Furthermore, we perform computational tests that show that our submodular approximations of traveling salesman tour lengths have smaller errors than our theoretical worst case analysis would lead us to believe.

Reviews

Required fields are marked *. Your email address will not be published.