Approximation of the double traveling salesman problem with multiple stacks

DOI10.1016/J.TCS.2021.05.016MaRDI QIDQ2034797zbMATH OpenOpenAlexFDO

Authors Laurent Alfandari, Sophie Toulouse

Publication date 23 June 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

approximationcomplexitymatching algorithmstraveling salesman problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Efficient algorithms for the double traveling salesman problem with multiple stacks
• Exact solutions to the double travelling salesman problem with multiple stacks
• The double travelling salesman problem with multiple stacks - formulation and heuristic solution approaches
• The double traveling salesman problem with multiple stacks: A variable neighborhood search approach
• A branch-and-bound algorithm for the double travelling salesman problem with two stacks
• A set covering approach for the double traveling salesman problem with multiple stacks
• An exact method for the double TSP with multiple stacks
• Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks
• Approximability of the multiple stack TSP

Cites work

• 35/44-approximation for asymmetric maximum TSP with triangle inequality
• 8/7-approximation algorithm for (1,2)-TSP
• z-approximations
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• A better differential approximation ratio for symmetric TSP
• A branch-and-bound algorithm for the double travelling salesman problem with two stacks
• A Dynamic Programming Approach to Sequencing Problems
• A dynamic programming based local search approach for the double traveling salesman problem with multiple stacks
• A variable neighborhood search heuristic algorithm for the double vehicle routing problem with multiple stacks
• An exact method for the double TSP with multiple stacks
• Approximability of the multiple stack TSP
• Approximation algorithms for some vehicle routing problems
• Approximation results for the weighted \(P_4\) partition problem
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• Deterministic 7/8-approximation for the metric maximum TSP
• Differential approximation of the multiple stacks TSP
• Differential approximation results for the traveling salesman and related problems
• Differential approximation results for the traveling salesman problem with distances 1 and 2
• Efficient algorithms for the double traveling salesman problem with multiple stacks
• Exact algorithms for the double vehicle routing problem with multiple stacks
• Exact solutions to the double travelling salesman problem with multiple stacks
• scientific article; zbMATH DE number 1187152 (Why is no real title available?)
• scientific article; zbMATH DE number 3746840 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1865680 (Why is no real title available?)
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• Improved deterministic approximation algorithms for max TSP
• Minimizing setups in ordered sets of fixed width
• New approximation algorithms for \((1,2)\)-TSP
• New differential approximation algorithm for \(k\)-customer vehicle routing problem
• New formulation and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks
• New neighborhood structures for the double traveling salesman problem with multiple stacks
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• On the Complexity of the Multiple Stack TSP, kSTSP
• Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks
• The design of approximation algorithms
• The double traveling salesman problem with multiple stacks: A variable neighborhood search approach
• The double travelling salesman problem with multiple stacks - formulation and heuristic solution approaches
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• The Traveling Salesman Problem with Distances One and Two
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(13)

• The double traveling salesman problem with multiple stacks: A variable neighborhood search approach
• In memory of Jérôme Monnot
• The \(k\)-delivery traveling salesman problem: revisited
• An LP-based approximation algorithm for the generalized traveling salesman path problem
• Approximability of the multiple stack TSP
• The Uncapacitated Asymmetric Traveling Salesman Problem with Multiple Stacks
• Differential approximation of the multiple stacks TSP
• Exact algorithms for the double vehicle routing problem with multiple stacks
• On the Complexity of the Multiple Stack TSP, kSTSP
• The double traveling salesman problem with partial last‐in‐first‐out loading constraints
• A metaheuristic for the double traveling salesman problem with partial last‐in‐first‐out loading constraints
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• 1.6-approximation algorithm for generalized traveling salesman path problem

This page was built for publication: Approximation of the double traveling salesman problem with multiple stacks

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