An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution (Q5374000): Difference between revisions

Latest revision as of 09:36, 30 July 2024

scientific article; zbMATH DE number 6857054

Language	Label	Description	Also known as
English	An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution	scientific article; zbMATH DE number 6857054

Statements

instance of

scholarly article

0 references

title

An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution (English)

0 references

0 references

0 references

Journal of Applied and Industrial Mathematics

0 references

publication date

6 April 2018

0 references

zbMATH Keywords

\(m\)-peripatetic salesman problem

0 references

asymptotically optimal algorithm

0 references

random input

0 references

discrete distribution

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Q3115591

0 references

Q3115183

0 references

On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space

0 references

Q4817463

0 references

Q3115668

0 references

Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations

0 references

Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above

0 references

Approximation algorithms for the maximum 2-peripatetic salesman problem

0 references

0 references

0 references

0 references

0 references

Fast probabilistic algorithms for Hamiltonian circuits and matchings

0 references

An algorithm for finding Hamilton paths and cycles in random graphs

0 references

Well-solved cases of the 2-peripatetic salesman problem

0 references

Lower bounds for symmetric<i>K</i>-peripatetic salesman problems

0 references

Bounds for the symmetric 2-peripatetic salesman problem

0 references

A branch and bound algorithm for symmetric 2-peripatetic salesman problems

0 references

Q3267900

0 references

An algorithm for finding hamilton cycles in random directed graphs

0 references

An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three

0 references

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

0 references

An Algorithm with Approximation Ratio 5/6 for the Metric Maximum m-PSP

0 references

Limit distribution for the existence of Hamiltonian cycles in a random graph

0 references

Q4068472

0 references

Hamiltonian circuits in random graphs

0 references

full work available at URL

https://doi.org/10.1134/s1990478917030061

0 references

Identifiers

zbMATH Open document ID

1399.05210

0 references

DOI

10.1134/S1990478917030061

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5374000

@@ Property / cites work @@
+Q3115591
@@ Property / cites work: Q3115591 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3115183
@@ Property / cites work: Q3115183 / rank @@
+Normal rank
@@ Property / cites work @@
+On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
+Normal rank
@@ Property / cites work @@
+Q4817463
@@ Property / cites work: Q4817463 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3115668
@@ Property / cites work: Q3115668 / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations
+Normal rank
@@ Property / cites work @@
+Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for the maximum 2-peripatetic salesman problem
+Normal rank
@@ Property / cites work @@
+Q3215242
@@ Property / cites work: Q3215242 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3115273
@@ Property / cites work: Q3115273 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3115278
@@ Property / cites work: Q3115278 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5613125
@@ Property / cites work: Q5613125 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast probabilistic algorithms for Hamiltonian circuits and matchings
+Normal rank
@@ Property / cites work @@
+An algorithm for finding Hamilton paths and cycles in random graphs
+Normal rank
@@ Property / cites work @@
+Well-solved cases of the 2-peripatetic salesman problem
+Normal rank
@@ Property / cites work @@
+Lower bounds for symmetric<i>K</i>-peripatetic salesman problems
+Normal rank
@@ Property / cites work @@
+Bounds for the symmetric 2-peripatetic salesman problem
+Normal rank
@@ Property / cites work @@
+A branch and bound algorithm for symmetric 2-peripatetic salesman problems
+Normal rank
@@ Property / cites work @@
+Q3267900
@@ Property / cites work: Q3267900 / rank @@
+Normal rank
@@ Property / cites work @@
+An algorithm for finding hamilton cycles in random directed graphs
+Normal rank
@@ Property / cites work @@
+An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
+Normal rank
@@ Property / cites work @@
+Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
+Normal rank
@@ Property / cites work @@
+An Algorithm with Approximation Ratio 5/6 for the Metric Maximum m-PSP
+Normal rank
@@ Property / cites work @@
+Limit distribution for the existence of Hamiltonian cycles in a random graph
+Normal rank
@@ Property / cites work @@
+Q4068472
@@ Property / cites work: Q4068472 / rank @@
+Normal rank
@@ Property / cites work @@
+Hamiltonian circuits in random graphs
@@ Property / cites work: Hamiltonian circuits in random graphs / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1134/s1990478917030061
+Normal rank
@@ Property / OpenAlex ID @@
+W2753301622
@@ Property / OpenAlex ID: W2753301622 / rank @@
+Normal rank