ПОЛИНОМИАЛЬНАЯ ПРИБЛИЖЕННАЯ СХЕМА ДЛЯ ЕВКЛИДОВОЙ ЗАДАЧИ О ЦИКЛОВОМ ПОКРЫТИИ ГРАФА

科研成果: Article同行评审

摘要

We study the Min--SCCP problem on a partition of a complete weighted digraph into vertex-disjoint cycles of minimum total weight. This problem is a natural generalization of the known Traveling salesman problem (TSP) and has a number of applications in operations research and data analysis. We show that the problem is strongly -hard and preserves intractability even in the geometric statement. For a metric special case of the problem, a new polynomial 2-approximation algorithm is proposed. For the Euclidean Min--SCCP, a polynomial-time approximation scheme based on Arora's approach is built.
投稿的翻译标题Polynomial-time approximation scheme for a Euclidean problem on a cycle covering of a graph
源语言Russian
页(从-至)297-311
页数15
期刊Труды института математики и механики УрО РАН
20
4
Published - 2014

GRNTI

  • 27.45.00

Level of Research Output

  • VAK List

指纹 探究 'ПОЛИНОМИАЛЬНАЯ ПРИБЛИЖЕННАЯ СХЕМА ДЛЯ ЕВКЛИДОВОЙ ЗАДАЧИ О ЦИКЛОВОМ ПОКРЫТИИ ГРАФА' 的科研主题。它们共同构成独一无二的指纹。

引用此