The Steiner traveling salesman problem with online edge blockages

DOI10.1016/j.ejor.2014.11.013zbMath1346.90794OpenAlexW1986937309MaRDI QIDQ319009

Weitian Tong, Yin-Feng Xu, Hui-Li Zhang, Guo-Hui 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

competitive ratiotraveling salesman problemonline algorithmonline edge blockageSteiner TSP

Mathematics Subject Classification ID

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

Related Items (8)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compact formulations of the Steiner traveling salesman problem and related problems
• 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
• Design and control of warehouse order picking: a literature review
• A note on the \(k\)-Canadian traveller problem
• The Canadian Traveller Problem and its competitive analysis
• A cutting plane procedure for the travelling salesman problem on road networks
• A review of dynamic vehicle routing problems
• The \(k\)-Canadian travelers problem with communication
• The covering Canadian traveller problem
• Online traveling salesman problems with service flexibility
• Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• The traveling salesman problem on a graph and some related integer polyhedra
• A fundamental problem in vehicle routing
• Dynamic programming and the graphical traveling salesman problem
• The Traveling Salesman Problem with Distances One and Two
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Approximating Graphic TSP by Matchings
• Algorithms for the on-line travelling salesman

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