Proceedings of the Steklov Institute of Mathematics · 2016 · 21 citations · 12 references
ComputingComputer ScienceAlgorithmsOptimizationApproximation AlgorithmsCombinatorial OptimizationComputational ComplexityShortest Path AlgorithmsTransportation ProblemsComplexityExact AlgorithmsLinear ComplexityTraveling Salesperson ProblemTraveling Salesperson Problem Approximation
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.
12