Geodesic
Semi-definite positive programming relaxations for graph K 𝐧 -coloring in frequency assignment
RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 2, pp. 211-228 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct n-uples of colors used to color a given set of n-complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find good feasible solutions with a probabilistic approach.

Dans cet article, nous décrivons une nouvelle classe de problèmes de coloration rencontrés en Allocation de Fréquences militaire : nous voulons minimiser le nombre de n-uplets distincts utilisés pour colorier un ensemble doné de n-cliques d’un graphe. Pour approcher ces problèmes généralement NP-difficiles, nous proposons deux relaxations basées sur les modélisations semi-définies de la coloration de graphes et d’hypergraphes, ainsi qu’une généralisation des travaux de Karger et al. à la coloration d’hypergraphes, pour trouver de bonnes solutions faisables par une approche probabiliste.

Keywords: discrete optimization, semidefinite programming, frequency assignment, graph coloring, hypergraph coloring 
@article{RO_2001__35_2_211_0,
     author = {Meurdesoif, Philippe and Rottembourg, Beno{\^\i}t},
     title = {Semi-definite positive programming relaxations for graph $K_{\bf n}$-coloring in frequency assignment},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {211--228},
     year = {2001},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {2},
     mrnumber = {1868870},
     zbl = {1049.90111},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RO_2001__35_2_211_0/}
}
TY  - JOUR
AU  - Meurdesoif, Philippe
AU  - Rottembourg, Benoît
TI  - Semi-definite positive programming relaxations for graph $K_{\bf n}$-coloring in frequency assignment
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2001
SP  - 211
EP  - 228
VL  - 35
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/item/RO_2001__35_2_211_0/
LA  - en
ID  - RO_2001__35_2_211_0
ER  - 
%0 Journal Article
%A Meurdesoif, Philippe
%A Rottembourg, Benoît
%T Semi-definite positive programming relaxations for graph $K_{\bf n}$-coloring in frequency assignment
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2001
%P 211-228
%V 35
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/RO_2001__35_2_211_0/
%G en
%F RO_2001__35_2_211_0
Meurdesoif, Philippe; Rottembourg, Benoît. Semi-definite positive programming relaxations for graph $K_{\bf n}$-coloring in frequency assignment. RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 2, pp. 211-228. http://geodesic.mathdoc.fr/item/RO_2001__35_2_211_0/