Informative path planning as a maximum traveling salesman problem with submodular rewards

DOI10.1016/j.dam.2015.01.004zbMath1311.05103arXiv1209.3759OpenAlexW2153817623MaRDI QIDQ2345604

Stephen L. Smith, Syed Talha Jawaid

Publication date: 22 May 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1209.3759

zbMATH Keywords

traveling salesman problemsubmodular function maximizationinformative path planning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Signed and weighted graphs (05C22)

Related Items (1)

Spatial coverage in routing and path planning problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Better approximations for max TSP
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
• Maximizing Non-monotone Submodular Functions
• A threshold of ln n for approximating set cover
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• Efficient Informative Sensing using Multiple Robots
• Optimal Value of Information in Graphical Models
• The greedy travelling salesman's problem
• Worst case analysis of greedy type algorithms for independence systems
• An analysis of approximations for maximizing submodular set functions—I
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
• Non-monotone submodular maximization under matroid and knapsack constraints
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Greedy in Approximation Algorithms
• Cooperative forest fire surveillance using a team of small unmanned air vehicles
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Informative path planning as a maximum traveling salesman problem with submodular rewards