Seminars: M. Yu. Khachai, Neznakhina E.D., Polynomial-time approximation scheme for problem of splitting complete Euclidean graph on two minimum weight gamiltonian cycles

SEMINARS


Seminar for Optimization Laboratory April 18, 2014 11:00, Ekaterinburg, Sophya Kovalevskaya, 16, Big Hall, Krasovsky Institute of Mathematics and Mechanics, Ural Branch of RAS, Ekaterniburg

Polynomial-time approximation scheme for problem of splitting complete Euclidean graph on two minimum weight gamiltonian cycles M. Yu. Khachai^ab, Neznakhina E.D.^b ^a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg ^b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg
Abstract: In this work we propose more general form of Arora's PTAS for Euclidean multiple (two) traveling salesman problem on the plane. It differs from classical traveling salesman problem by the requirement to find two closed vertex-disjoint circuits of minimum overall weight.