Semi-definite positive programming relaxations for graph k-coloring in frequency assignment

Semi-definite positive programming relaxations for graph k-coloring in frequency assignment

0.00 Avg rating0 Votes
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: ,
Keywords: programming (semidefinite)
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.

Reviews

Required fields are marked *. Your email address will not be published.