|
|
Seminar for Optimization Laboratory
April 18, 2014 11:00–12: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. Khachaiab, 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
|
| Number of views: |
| This page: | 279 |
|
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.
|
|
Contact us: