Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph

DOI10.1016/J.DAM.2015.03.007MaRDI QIDQ499338zbMATH OpenOpenAlexFDO

Authors A. A. Skretneva, O. Yu. Tsidulko, D. Zh. Zambalaeva, Eh. Kh. Gimadi, A. N. Glebov

Publication date 30 September 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.03.007

zbMATH Keywords

polynomial algorithmasymptotic optimalityperformance guaranteesasymmetric \(m\)-peripatetic salesman problemdisjoint Hamiltonian circuitsrandom inputs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Eulerian and Hamiltonian graphs (05C45) Signed and weighted graphs (05C22)

Recommendations

• Approximation algorithms for the maximum 2-peripatetic salesman problem
• Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2
• A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
• 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

Cites work

• scientific article; zbMATH DE number 6007907 (Why is no real title available?)
• scientific article; zbMATH DE number 3485514 (Why is no real title available?)
• scientific article; zbMATH DE number 741240 (Why is no real title available?)
• scientific article; zbMATH DE number 2102640 (Why is no real title available?)
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• A heuristic approach to the overnight security service problem
• An approximation algorithm for the minimum 2-peripatetic salesman problem with different weight functions
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• Better approximations for max TSP
• Bounds for the symmetric 2-peripatetic salesman problem
• Lower bounds for symmetricK-peripatetic salesman problems
• On some probability inequalities for some discrete optimization problems
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• The traveling salesman problem and its variations
• Well-solved cases of the 2-peripatetic salesman problem
• \(7/5\)-approximation algorithm for 2-PSP on minimum with different weight functions

Cited in

(5)

• The Undirected m-Peripatetic Salesman Problem: Polyhedral Results and New Algorithms
• An asymptotically optimal algorithm for the \(m\)-peripatetic salesman problem on random inputs with discrete distribution
• Branch-and-cut algorithms for the undirected m-Peripatetic Salesman Problem
• A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
• Safe and secure vehicle routing: a survey on minimization of risk exposure

This page was built for publication: Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph

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