Submodularity and the traveling salesman problem
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.
- A note on the traveling salesman problem
- Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP
- Heuristics and bounds for the travelling salesman location problem on the plane
- The traveling salesman problem on a graph and some related integer polyhedra
- Informative path planning as a maximum traveling salesman problem with submodular rewards
- 98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Multi-Retailer Systems
- A 98%-Effective Lot-Sizing Rule for a Multi-Product, Multi-Stage Production / Inventory System
- A Dynamic Programming Approach to Sequencing Problems
- An analysis of approximations for maximizing submodular set functions—I
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Bounds and Heuristics for Capacitated Routing Problems
- Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Heuristics for a One-Warehouse Multiretailer Distribution Problem with Performance Bounds
- scientific article; zbMATH DE number 3908167 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 3895002 (Why is no real title available?)
- scientific article; zbMATH DE number 3193293 (Why is no real title available?)
- Naturally submodular digraphs and forbidden digraph configurations
- On some balanced, totally balanced and submodular delivery games
- One Warehouse Multiple Retailer Systems with Vehicle Routing Costs
- Outline of an algorithm for integer solutions to linear programs
- Simple Power-of-Two Policies are Close to Optimal in a General Class of Production/Distribution Networks with General Joint Setup Costs
- Spacefilling curves and the planar travelling salesman problem
- The multi-level uncapacitated facility location problem is not submodular
- The shortest path and the shortest road through n points
- The traveling salesman problem on a graph and some related integer polyhedra
- The traveling-salesman problem
- Vehicle scheduling on a tree with release and handling times
This page was built for publication: Submodularity and the traveling salesman problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124707)
