Article ID: | iaor20053274 |
Country: | France |
Volume: | 35 |
Issue: | 2 |
Start Page Number: | 211 |
End Page Number: | 228 |
Publication Date: | Apr 2001 |
Journal: | RAIRO Operations Research |
Authors: | Meurdesoif Philippe, Rottembourg Benot |
Keywords: | programming (semidefinite) |
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