RUS  ENG
Full version
JOURNALS // University proceedings. Volga region. Physical and mathematical sciences // Archive

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.

UDC: 004.021:519.8:519.724.6



© Steklov Math. Inst. of RAS, 2024