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.

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.

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.

Mots-clés : 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},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {2},
     year = {2001},
     mrnumber = {1868870},
     zbl = {1049.90111},
     language = {en},
     url = {http://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/item/RO_2001__35_2_211_0/

[1] F. Alizadeh, J.-P. Haeberly, M.V. Nayakkankuppam and M.L. Overton, SDPPack User's Guide, version 0.8 beta. Technical report, NYU Computer Science Dept. (1997) 30 p. URL: http://www.cs.nyu.edu/phd_students/madhu/sdppack/sdppack.html

[2] T. Defaix, Optimisation stochastique et allocation de plans de fréquences pour des réseaux à évasion de fréquences. Thèse de doctorat, Université de Rennes 1 (1996) 175 p.

[3] U. Feige and J. Kilian, Zero Knowledge and the Chromatic Number, in Proc. of the 11th Annual IEEE Conference in Computing Complexity, Preliminary Version (1996) 278-287.

[4] A. Frieze and M. Jerrum, Improved approximation algorithms for MAX k-cut and MAX BISECTION, in Proc. of the Fourth MPS Conference on Integer Programming and Combinatorial Optimization. Springer-Verlag (1995) Paper Version: 21 p. | MR | Zbl

[5] M.X. Goemans and D.P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42 (1995) 1115-1145. | MR | Zbl

[6] D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming. J. ACM 45 (1998) 246-265. | MR | Zbl

[7] M. Krivelevich and B. Sudakov, Approximate coloring of uniform hypergraphs. DIMACS Technical Report 98-31 (1998) 15 p. | Zbl

[8] L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inform. Theory IT-25 (1979) 1-7. | MR | Zbl

[9] C. Lund and M. Yannakakis, On the hardness of approximating minimization problems. J. ACM 41 (1994) 960-981. | MR | Zbl

[10] S. Mahajan and H. Ramesh, Derandomizing semidefinite programming based approximation algorithms, in Proc. of the 36th Annual IEEE Symposium on Foundations of Computer Science (1995) Paper Version: 19 p. | MR | Zbl