2-Approximation algorithm for finding a clique with minimum weight of vertices and edges / Eremin I.I., Gimadi E.K., Kel'manov A.V., Pyatkin A.V., Khachai M.Y. // Proceedings of the Steklov Institute of Mathematics. - 2014. - V. 284, l. SUPPL.1. - P. 87-95.

ISSN:

00815438

Type:

Article

Abstract:

The problem of finding a minimum clique (with respect to the total weight of its vertices and edges) of fixed size in a complete undirected weighted graph is considered along with some of its important subclasses. Approximability issues are analyzed. The inapproximability of the problem is proved for the general case. A 2-approximation efficient algorithm with time complexity O(n 2) is suggested for the cases when vertex weights are nonnegative and edge weights either satisfy the triangle inequality or are squared pairwise distances for some point configuration of Euclidean space. © 2014 Pleiades Publishing, Ltd.

Author keywords:

approximability; approximation guarantee; clique of fixed size; complete undirected graph; minimum weight of vertices and edges; polynomial time approximation algorithm; subset search; time complexity

Index keywords:

нет данных

DOI:

10.1134/S0081543814020084

Смотреть в Scopus:

https://www.scopus.com/inward/record.uri?eid=2-s2.0-84898742572&doi=10.1134%2fS0081543814020084&partnerID=40&md5=53bd3dde229557bc9493cd9ba1614344

Соавторы в МНС:

—

Другие поля

Поле	Значение
Link	https://www.scopus.com/inward/record.uri?eid=2-s2.0-84898742572&doi=10.1134%2fS0081543814020084&partnerID=40&md5=53bd3dde229557bc9493cd9ba1614344
Affiliations	Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russian Federation; Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg, 620990, Russian Federation; Institute of Mathematics and Computer Science, Ural Federal University, pr. Lenina 51, Yekaterinburg, 620000, Russian Federation
Author Keywords	approximability; approximation guarantee; clique of fixed size; complete undirected graph; minimum weight of vertices and edges; polynomial time approximation algorithm; subset search; time complexity
Funding Details	12-01-00090, RFBR, Russian Foundation for Basic Research; 12-01-00093, RFBR, Russian Foundation for Basic Research; 12-01-33028-mol-a-ved, RFBR, Russian Foundation for Basic Research; 13-01-00210, RFBR, Russian Foundation for Basic Research; 13-07-00070, RFBR, Russian Foundation for Basic Research; 13-07-00181, RFBR, Russian Foundation for Basic Research; 12-P1-1016, RAS, Russian Academy of Sciences; 12-S1-1017/1, RAS, Russian Academy of Sciences; 7B, RAS, Russian Academy of Sciences
References	Garey, M.R., Johnson, D.S., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , San Fransisco: Freeman; Håstad, J., Clique is hard to approximate within n1-e{open} (1999) Acta Math., 182 (1), pp. 105-142; Park, K., Lee, K., Park, S., An extended formulation approach to the edge-weighted maximal clique problem (1996) Europ. J. Oper. Res., 95 (3), pp. 671-682; Aho, A., Hopcroft, J., Ullman, J., (1974) The Design and Analysis of Computer Algorithms, , Reading, MA: Addison-Wesley; Kel'manov, A.V., Pyatkin, A.V., NP-completeness of some problems of choosing a vector subset (2011) J. Appl. Ind. Math., 5 (3), pp. 352-357; Kel'manov, A.V., Romanchenko, S.M., An approximation algorithm for solving a problem of search for a vector subset (2012) J. Appl. Ind. Math., 6 (4), pp. 90-96
Correspondence Address	Gimadi, E. K.; Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russian Federation; email: gimadi@math.nsc.ru
Language of Original Document	English
Abbreviated Source Title	Proc. Steklov Inst. Math.
Source	Scopus