Lower bounds for symmetricK-peripatetic salesman problems
From MaRDI portal
Publication:5749147
DOI10.1080/02331939108843650zbMath0717.90048OpenAlexW1963919276MaRDI QIDQ5749147
Publication date: 1991
Published in: Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/02331939108843650
Programming involving graphs or networks (90C35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Paths and cycles (05C38) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items (21)
On the generalized 2-peripatetic salesman problem ⋮ 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 ⋮ A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP ⋮ Bounds for the symmetric 2-peripatetic salesman problem ⋮ Lower and upper bounds for the \(m\)-peripatetic vehicle routing problem ⋮ Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP ⋮ An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution ⋮ On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space ⋮ 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 ⋮ Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph ⋮ The undirected \(m\)-capacitated peripatetic salesman problem ⋮ Branch-and-cut algorithms for the undirected \(m\)-Peripatetic Salesman Problem ⋮ A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem ⋮ Heuristiques pour le Problème du Vendeurm-Péripatétique ⋮ A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP ⋮ 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 ⋮ A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
Cites Work
This page was built for publication: Lower bounds for symmetricK-peripatetic salesman problems