The Steiner traveling salesman problem with online edge blockages

DOI10.1016/J.EJOR.2014.11.013MaRDI QIDQ319009zbMATH OpenOpenAlexFDO

Authors Weitian Tong, Huili Zhang, Yinfeng Xu, Guohui Lin

Publication date 6 October 2016

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

Full work available at URL https://doi.org/10.1016/j.ejor.2014.11.013

zbMATH Keywords

traveling salesman problemcompetitive ratioonline algorithmonline edge blockageSteiner TSP

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The \(m\)-Steiner traveling salesman problem with online edge blockages
• The Steiner traveling salesman problem with online advanced edge blockages
• Online covering salesman problem
• Algorithms for the on-line travelling salesman
• Online traveling salesman problems with service flexibility

Cites work

• scientific article; zbMATH DE number 432827 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• A Randomized Rounding Approach to the Traveling Salesman Problem
• A cutting plane procedure for the travelling salesman problem on road networks
• A fundamental problem in vehicle routing
• A note on the \(k\)-Canadian traveller problem
• A review of dynamic vehicle routing problems
• Algorithms for the on-line travelling salesman
• Approximating Graphic TSP by Matchings
• Compact formulations of the Steiner traveling salesman problem and related problems
• Design and control of warehouse order picking: a literature review
• Dynamic programming and the graphical traveling salesman problem
• Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses
• Online traveling salesman problems with service flexibility
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
• Shortest paths without a map
• The Canadian Traveller Problem and its competitive analysis
• The Traveling Salesman Problem with Distances One and Two
• The \(k\)-Canadian travelers problem with communication
• The covering Canadian traveller problem
• The traveling salesman problem on a graph and some related integer polyhedra

Cited in

(8)

• An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem
• The \(m\)-Steiner traveling salesman problem with online edge blockages
• On the online multi-agent O-D \(k\)-Canadian traveler problem
• The Steiner traveling salesman problem with online advanced edge blockages
• Online covering salesman problem
• An online optimization approach for post-disaster relief distribution with online blocked edges
• Online routing and searching on graphs with blocked edges
• Weighted online minimum latency problem with edge uncertainty

This page was built for publication: The Steiner traveling salesman problem with online edge blockages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q319009)