Volume 18, No 1, 2011, P. 41-60
UDC 519.8
V. P. Il'ev, S. D. Il'eva, A. A. Navrotskaya
Approximation algorithms for graph approximation problems
Abstract:
Some versions of the graph approximation problem are studied. Approximation algorithms for these problems are proposed and performance guarantees of the algorithms are obtained. In particular, it is shown that the problem of approximation by graphs with a bounded number of connected components belongs to the class APX.
Ill. 1, bibliogr. 12.
Keywords: graph approximation problem, approximation algorithm, performance guarantee.
Il’ev Victor Petrovich 1
Il’eva Svetlana Diadorovna 2
Navrotskaya Anna Aleksandrovna 1
1. Omsk State University,
55a Mira ave., 644077 Omsk, Russia
2.
Omsktelecom,
23 First Zavodskaya, 644040 Omsk, Russia
e-mail: iljev@mail.ru, iljeva@mail.ru, nawrocki@yandex.ru
