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

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2013},
     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
PB  - mathdoc
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
%I mathdoc
%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/