Сибирский федеральный университет

Тип публикации: статья из журнала

Год издания: 2015

Идентификатор DOI: 10.1134/S0081543815050089

Ключевые слова: approximation algorithm, attainable bounds, metric problem, minimum total weight of vertices and edges, performance guarantee, quadratic Euclidean problem, search for vertex-disjoint cliques

Аннотация: We consider the problem of finding a fixed number of vertex-disjoint cliques of given sizes in a complete undirected weighted graph so that the total weight of vertices and edges in the cliques would be minimal. We show that the problem is strongly NP-hard both in the general case and in two subclasses, which have important applications. An approximation algorithm for this problem is presented. We show that the algorithm finds a solution with a bounded approximation ratio for the considered subclasses of the problem, and the bound is attainable. In the case when the number of cliques to be found is fixed in advance (i.e., is a parameter), the time complexity of the algorithm is polynomial. © 2015, Pleiades Publishing, Ltd.

Журнал: Proceedings of the Steklov Institute of Mathematics

Выпуск журнала: Vol. 289

Номера страниц: 88-101

• Gimadi E.K. (Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, pr. Akad. Koptyuga 4, Novosibirsk, Russian Federation, Novosibirsk State University, ul. Pirogova 2, Novosibirsk, Russian Federation)
• Kel’manov A.V. (Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, pr. Akad. Koptyuga 4, Novosibirsk, Russian Federation, Novosibirsk State University, ul. Pirogova 2, Novosibirsk, Russian Federation)
• Pyatkin A.V. (Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, pr. Akad. Koptyuga 4, Novosibirsk, Russian Federation, Novosibirsk State University, ul. Pirogova 2, Novosibirsk, Russian Federation)
• Khachai M.Y. (Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg, Russian Federation, Institute of Mathematics and Computer Science, Ural Federal University, pr. Lenina 51, Yekater)

• Scopus