Submodularity and the traveling salesman problem

Programming involving graphs or networks (90C35) Transportation, logistics and supply chain management (90B06) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (3)

Naturally submodular digraphs and forbidden digraph configurations ⋮ A new algorithm for one-warehouse multi-retailer systems under stationary nested policy ⋮ Traveling salesman games with the Monge property

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Vehicle scheduling on a tree with release and handling times
On some balanced, totally balanced and submodular delivery games
Naturally submodular digraphs and forbidden digraph configurations
The shortest path and the shortest road through n points
Outline of an algorithm for integer solutions to linear programs
A Dynamic Programming Approach to Sequencing Problems
One Warehouse Multiple Retailer Systems with Vehicle Routing Costs
Spacefilling curves and the planar travelling salesman problem
The traveling salesman problem on a graph and some related integer polyhedra
Bounds and Heuristics for Capacitated Routing Problems
98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Multi-Retailer Systems
Simple Power-of-Two Policies are Close to Optimal in a General Class of Production/Distribution Networks with General Joint Setup Costs
An Analysis of Several Heuristics for the Traveling Salesman Problem
An analysis of approximations for maximizing submodular set functions—I
Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP
Heuristics for a One-Warehouse Multiretailer Distribution Problem with Performance Bounds
A 98%-Effective Lot-Sizing Rule for a Multi-Product, Multi-Stage Production / Inventory System
The Traveling-Salesman Problem
The multi-level uncapacitated facility location problem is not submodular

This page was built for publication: Submodularity and the traveling salesman problem