Submodularity and the traveling salesman problem

✍ Scribed by Yale T. Herer

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 339 KB
• Volume: 114
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(98)00175-1

✦ Synopsis

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 ®nd 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.