Geodesic
On the Approximability of the Minimum Weight $t$-partite Clique Problem
Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 171-190.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The ${\rm M{\small INIMUM}~W\small{EIGHT}}$ $t$-${\rm {\small PARTITE}~C{\small LIQUE}~P{\small ROBLEM}~MW} t {\rm CP}$ is the problem of finding a $t$-clique with minimum weight in a complete edge-weighted $t$-partite graph. The motivation for studying this problem is its potential in modelling the problem of identifying sets of commonly existing putative co-regulated, co-expressed genes, called gene clusters. In this paper, we show that ${\rm MW} t {\rm CP}$ is NP-hard, APX-hard in the general case. We also present a 2-approximation algorithm that runs in $O(n^2)$ for the metric case and has 1+$ \frac{1}{t}$-approximation performance guarantee for the ultrametric subclass of instances. We further show how relaxing or tightening the application of the metricity property affects the approximation ratio. Finally insights on the application ${\rm MW} t {\rm CP}$ to gene cluster discovery are presented. 
@article{JGAA_2020_24_3_a2,
     author = {Geoffrey Solano and Guillaume Blin and Mathieu Raffinot and Jhoirene Clemente and Jaime Caro},
     title = {On the {Approximability} of the {Minimum} {Weight} $t$-partite {Clique} {Problem}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {171--190},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2020},
     doi = {10.7155/jgaa.00525},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00525/}
}
TY  - JOUR
AU  - Geoffrey Solano
AU  - Guillaume Blin
AU  - Mathieu Raffinot
AU  - Jhoirene Clemente
AU  - Jaime Caro
TI  - On the Approximability of the Minimum Weight $t$-partite Clique Problem
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 171
EP  - 190
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00525/
DO  - 10.7155/jgaa.00525
LA  - en
ID  - JGAA_2020_24_3_a2
ER  - 
%0 Journal Article
%A Geoffrey Solano
%A Guillaume Blin
%A Mathieu Raffinot
%A Jhoirene Clemente
%A Jaime Caro
%T On the Approximability of the Minimum Weight $t$-partite Clique Problem
%J Journal of Graph Algorithms and Applications
%D 2020
%P 171-190
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00525/
%R 10.7155/jgaa.00525
%G en
%F JGAA_2020_24_3_a2
Geoffrey Solano; Guillaume Blin; Mathieu Raffinot; Jhoirene Clemente; Jaime Caro. On the Approximability of the Minimum Weight $t$-partite Clique Problem. Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 171-190. doi : 10.7155/jgaa.00525. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00525/

Cité par Sources :