Geodesic
$2$-approximate algorithm for finding a clique with minimum weight of vertices and edges
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 2, pp. 134-143 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The problem on a minimal 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 special cases. Approximability questions are analyzed. The weak approximability of the problem is established for the general case. A $2$-approximate effective algorithm with time complexity $O(n^2)$ is proposed for cases where vertex weights are nonnegative and edge weights either satisfy the triangle inequality or are squared pairwise distances for some system of points of a Euclidean space.
Keywords: complete undirected graph, clique of fixed size, minimum weight of vertices and edges, subset search, approximability, performance guarantee, time complexity.
Mots-clés : polynomial approximation algorithm 
@article{TIMM_2013_19_2_a12,
     author = {I. I. Eremin and E. Kh. Gimadi and A. V. Kel'manov and A. V. Pyatkin and M. Yu. Khachai},
     title = {$2$-approximate algorithm for finding a~clique with minimum weight of vertices and edges},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {134--143},
     year = {2013},
     volume = {19},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a12/}
}
TY  - JOUR
AU  - I. I. Eremin
AU  - E. Kh. Gimadi
AU  - A. V. Kel'manov
AU  - A. V. Pyatkin
AU  - M. Yu. Khachai
TI  - $2$-approximate algorithm for finding a clique with minimum weight of vertices and edges
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2013
SP  - 134
EP  - 143
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a12/
LA  - ru
ID  - TIMM_2013_19_2_a12
ER  - 
%0 Journal Article
%A I. I. Eremin
%A E. Kh. Gimadi
%A A. V. Kel'manov
%A A. V. Pyatkin
%A M. Yu. Khachai
%T $2$-approximate algorithm for finding a clique with minimum weight of vertices and edges
%J Trudy Instituta matematiki i mehaniki
%D 2013
%P 134-143
%V 19
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a12/
%G ru
%F TIMM_2013_19_2_a12
I. I. Eremin; E. Kh. Gimadi; A. V. Kel'manov; A. V. Pyatkin; M. Yu. Khachai. $2$-approximate algorithm for finding a clique with minimum weight of vertices and edges. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 2, pp. 134-143. http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a12/

[1] Garey M. R., Johnson D., Computers and intractability: A guide to the theory of $NP$-completeness, Freeman, San Francisco, 1979, 314 pp. | MR | Zbl

[2] Håstad J., “Clique is hard to approximate within $n^{1-\varepsilon}$”, Acta Math., 182:1 (1999), 105–142 | DOI | MR

[3] Park K., Lee K., Park S., “An extended formulation approach to the edge-weighted maximal clique problem”, European J. of Operational Research, 95:3 (1996), 671–682 | DOI | Zbl

[4] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979, 536 pp. | MR

[5] Kelmanov A. V., Pyatkin A. V., “$NP$-polnota nekotorykh zadach vybora podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 17:5 (2010), 37–45 | MR

[6] Kelmanov A. V., Romanchenko S. M., “Priblizhennyi algoritm dlya resheniya odnoi zadachi poiska podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 18:1 (2011), 61–69 | MR