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

Author： Meurdesoif Philippe   Rottembourg Benoît  

Publisher： Edp Sciences

E-ISSN： 1290-3868|35|2|211-228

ISSN： 0399-0559

Source： RAIRO - Operations Research, Vol.35, Iss.2, 2010-03, pp. : 211-228

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want tominimize the number of distinct n-uples of colors used to color a givenset of n-complete-subgraphs of a graph. We will propose two relaxations based onSemi-Definite Programming models for graph and hypergraphcoloring, to approximate those (generally) NP-hard problems, as well asa generalization of the works of Karger et al. for hypergraph coloring,to find good feasible solutions with a probabilisticapproach.

Related content

A logarithm barrier method for semi-definite programming

By Crouzeix Jean-Pierre   Merikhi Bachir  

RAIRO - Operations Research, Vol. 42, Iss. 2, 2008-05 ,pp. : 123-139 (17)

Edp Sciences

Access to resources Recommend Favorite

On the central path for nonlinear semidefinite programming

By Grana Drummond L. M.   Iusem Alfredo Noel   Svaiter B. F.  

RAIRO - Operations Research, Vol. 34, Iss. 3, 2010-03 ,pp. : 331-345 (15)

Edp Sciences

Access to resources Recommend Favorite

Semidefinite Programming Based Algorithms for the Sparsest Cut Problem

By Meira Luis A.A.   Miyazawa Flávio K.  

RAIRO - Operations Research, Vol. 45, Iss. 2, 2011-06 ,pp. : 75-100 (26)

Edp Sciences

Access to resources Recommend Favorite

A relaxed logarithmic barrier method for semidefinite programming

By Samia Kettab   Djamel Benterki  

RAIRO - Operations Research, Vol. 49, Iss. 3, 2015-02 ,pp. : 555-568 (14)

Edp Sciences

Access to resources Recommend Favorite

The Reduction of Directed Cyclic Graph for Task Assignment Problem

By  

MATEC Web of conference, Vol. 150, Iss. issue, 2018-02 ,pp. : 06031-06031 (1)

Edp Sciences

Access to resources Recommend Favorite