Approximation algorithms for graph approximation problems
Victor P. Il’ev, Svetlana Il’eva, A. A. Navrotskaya · Journal of Applied and Industrial Mathematics · 2011
Several versions of the graph approximation problem are under study. 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.