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

DOI10.1016/J.DAM.2015.03.007zbMATH Open1321.05101OpenAlexW2037601619MaRDI QIDQ499338FDOQ499338

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

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

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)

Cites Work

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