Submodularity and the traveling salesman problem

DOI10.1016/S0377-2217(98)00175-1zbMATH Open0947.90120MaRDI QIDQ1124707FDOQ1124707

Authors: Yale T. Herer 

Publication date: 25 November 1999

Published in: European Journal of Operational Research (Search for Journal in Brave)

Recommendations

• 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

zbMATH Keywords

heuristicstraveling salesman problemsubmodular function

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• A new algorithm for one-warehouse multi-retailer systems under stationary nested policy
• Traveling salesman games with the Monge property
• Naturally submodular digraphs and forbidden digraph configurations
• Informative path planning as a maximum traveling salesman problem with submodular rewards

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)