Submodularity and the traveling salesman problem (Q1124707)

Consider a central warehouse and a set \(V\) of retailers. For \(S \subseteq V\) let \(T(S)\) the length of an optimal traveling salesman tour through the retailers in \(S\) and the warehouse. The problem investigated is to find a submodular function \(K(S)\) and a small \(\alpha\) such that \(T(S)\leq K(S)\leq \alpha T(S)\) for all \(S\subseteq V\). It is shown that there exists no constant \(c\) such that \(\alpha\leq c\) for all planar graphs modeling the connections between the retailers. However, when the facilities lie in the Euclidean plane the problem can be solved. Heuristics for calculating submodular functions are presented whose error grow slowly with the number of retailers. Computational tests show that the submodular approximations of the traveling salesman tour lengths have much smaller errors than the theoretical worst case analysis indicates.