An exact algorithm with linear complexity for a problem of visiting megalopolises

A. G. Chent︠s︡ov, M. Yu. Khachai, Daniil Khachai

Proceedings of the Steklov Institute of Mathematics · 2016 · 21 citations · 12 references

Concepts

Abstract

A problem of visiting megalopolises with a fixed number of “entrances” and precedence relations defined in a special way is studied. The problem is a natural generalization of the classical traveling salesman problem. For finding an optimal solution, we give a dynamic programming scheme, which is equivalent to a method of finding a shortest path in an appropriate acyclic oriented weighted graph. We justify conditions under which the complexity of the algorithm depends on the number of megalopolises polynomially, in particular, linearly.

References

12