|
University proceedings. Volga region. Physical and mathematical sciences, 2009, Issue 3, Pages 96–100
(Mi ivpnz701)
|
|
|
|
Mathematics
Approximation algorithms and a pseudometric version of the traveling salesman problem
E. S. Borisova, B. Melnikov Togliatti State University, Togliatti
Abstract:
An Article contains classical approach to approximation algorithms, there are given examples illustrating the basic definition of these algorithms. There are contained polynomial-time approximation scheme and fully polynomial-time approximation scheme. There is cited an example psevdometric traveling salesperson problem. Efficient algorithms giving optimal solution this problem haven't yet developed.
Keywords:
approximation algorithms, relative error, approximation ratio, approximation scheme, psevdometric traveling salesperson problem.
Citation:
E. S. Borisova, B. Melnikov, “Approximation algorithms and a pseudometric version of the traveling salesman problem”, University proceedings. Volga region. Physical and mathematical sciences, 2009, no. 3, 96–100
Linking options:
https://www.mathnet.ru/eng/ivpnz701 https://www.mathnet.ru/eng/ivpnz/y2009/i3/p96
|
Statistics & downloads: |
Abstract page: | 28 | Full-text PDF : | 20 | References: | 12 |
|