Semi-definite positive programming relaxations for graph K-coloring in frequency assignment
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 -uples of colors used to color a given set of -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...