Lower bounds for symmetricK-peripatetic salesman problems

DOI10.1080/02331939108843650MaRDI QIDQ5749147zbMATH OpenOpenAlexFDO

Authors Jeroen B. J. M. De Kort

Publication date 1991

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331939108843650

zbMATH Keywords

edge-disjoint Hamiltonian cyclesK-Peripatetic Salesmanlower boundsroutingtraveling salesman

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Programming involving graphs or networks (90C35)

Recommendations

• Bounds for the symmetric 2-peripatetic salesman problem
• On the generalized 2-peripatetic salesman problem
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• Approximating the metric 2-peripatetic salesman problem
• New lower bounds for the symmetric travelling salesman problem

Cites work

• scientific article; zbMATH DE number 3898611 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• On some techniques useful for solution of transportation network problems
• Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem

Cited in

(26)

• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• On the generalized 2-peripatetic salesman problem
• New lower bounds for the symmetric travelling salesman problem
• The undirected \(m\)-capacitated peripatetic salesman problem
• Sensitivity analysis for symmetric 2-peripatetic salesman problems
• Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP
• Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services
• Heuristiques pour le Problème du Vendeurm-Péripatétique
• Bounds for the symmetric 2-peripatetic salesman problem
• Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
• A polynomial algorithm with asymptotic ratio 2/3 for the asymmetric maximization version of the m-PSP
• A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
• An asymptotically optimal algorithm for the m-peripatetic salesman problem on random inputs with discrete distribution
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem
• Lower and upper bounds for the m-peripatetic vehicle routing problem
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• Dissimilar arc routing problems
• Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
• Branch-and-cut algorithms for the undirected m-Peripatetic Salesman Problem
• Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations

This page was built for publication: Lower bounds for symmetricK-peripatetic salesman problems

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