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

Resultado de pesquisa: Articlerevisão de pares

Resumo

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.
Título traduzido da contribuiçãoPolynomial-time approximation scheme for a Euclidean problem on a cycle covering of a graph
Idioma originalRussian
Páginas (de-até)297-311
Número de páginas15
RevistaТруды института математики и механики УрО РАН
Volume20
Número de emissão4
Estado da publicaçãoPublished - 2014

GRNTI

  • 27.45.00

Level of Research Output

  • VAK List

Impressão digital

Mergulhe nos tópicos de investigação de “ПОЛИНОМИАЛЬНАЯ ПРИБЛИЖЕННАЯ СХЕМА ДЛЯ ЕВКЛИДОВОЙ ЗАДАЧИ О ЦИКЛОВОМ ПОКРЫТИИ ГРАФА“. Em conjunto formam uma impressão digital única.

Citar isto