PTAS ДЛЯ ЗАДАЧИ MIN-K-SCCP В ЕВКЛИДОВОМ ПРОСТРАНСТВЕ ПРОИЗВОЛЬНОЙ ФИКСИРОВАННОЙ РАЗМЕРНОСТИ

Resultado de pesquisa: Articlerevisão de pares

Resumo

We study the Min--SCCP on a partition of a complete weighted digraph into vertex-disjoint cycles of minimum total weight. This problem is a generalization of the known traveling salesman problem (TSP) and a special case of the classical vehicle routing problem (VRP). It is known that the problem Min--SCCP is strongly -hard and preserves its intractability even in the geometric statement. For the Euclidean Min--SCCP in with , we construct a polynomial-time approximation scheme, which generalizes the approach proposed earlier for the planar Min-2-SCCP. For any fixed the scheme finds a -approximate solution in time.
Título traduzido da contribuiçãoA PTAS for the Min--SCCP in a Euclidean space of arbitrary fixed dimension
Idioma originalRussian
Páginas (de-até)268-278
Número de páginas11
RevistaТруды института математики и механики УрО РАН
Volume21
Número de emissão3
Estado da publicaçãoPublished - 2015

GRNTI

  • 27.45.00

Level of Research Output

  • VAK List

Impressão digital

Mergulhe nos tópicos de investigação de “PTAS ДЛЯ ЗАДАЧИ MIN-K-SCCP В ЕВКЛИДОВОМ ПРОСТРАНСТВЕ ПРОИЗВОЛЬНОЙ ФИКСИРОВАННОЙ РАЗМЕРНОСТИ“. Em conjunto formam uma impressão digital única.

Citar isto