Semi-Definite positive Programming Relaxations for Graph K_n-Coloring in Frequency Assignment

¹ Projet NUMOPT, INRIA Rhône-Alpes, 655 avenue de l'Europe, 38330 Montbonnot-Saint-Martin, France; Philippe.Meurdesoif@inrialpes.fr.
² Direction des Technologies Nouvelles, Bouygues, 1 avenue Eugène Freyssinet, 78061 Saint-Quentin-en-Yvelines, France; brottemb@challenger.bouygues.fr.

Received: May 1999

Abstract

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.

Résumé

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.