# Semi-definite positive programming relaxations for graph K${}_{\mathbf{n}}$-coloring in frequency assignment

Philippe Meurdesoif; Benoît Rottembourg

RAIRO - Operations Research - Recherche Opérationnelle (2001)

- Volume: 35, Issue: 2, page 211-228
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topMeurdesoif, Philippe, and Rottembourg, Benoît. "Semi-definite positive programming relaxations for graph K$_{\bf n}$-coloring in frequency assignment." RAIRO - Operations Research - Recherche Opérationnelle 35.2 (2001): 211-228. <http://eudml.org/doc/105243>.

@article{Meurdesoif2001,

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.},

author = {Meurdesoif, Philippe, Rottembourg, Benoît},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {discrete optimization; semidefinite programming; frequency assignment; graph coloring; hypergraph coloring},

language = {eng},

number = {2},

pages = {211-228},

publisher = {EDP-Sciences},

title = {Semi-definite positive programming relaxations for graph K$_\{\bf n\}$-coloring in frequency assignment},

url = {http://eudml.org/doc/105243},

volume = {35},

year = {2001},

}

TY - JOUR

AU - Meurdesoif, Philippe

AU - Rottembourg, Benoît

TI - Semi-definite positive programming relaxations for graph K$_{\bf n}$-coloring in frequency assignment

JO - RAIRO - Operations Research - Recherche Opérationnelle

PY - 2001

PB - EDP-Sciences

VL - 35

IS - 2

SP - 211

EP - 228

AB - 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.

LA - eng

KW - discrete optimization; semidefinite programming; frequency assignment; graph coloring; hypergraph coloring

UR - http://eudml.org/doc/105243

ER -

## References

top- [1] F. Alizadeh, J.-P. Haeberly, M.V. Nayakkankuppam and M.L. Overton, SDPPack User’s Guide, version 0.8 beta. Technical report, NYU Computer Science Dept. (1997) 30 p. URL: http://www.cs.nyu.edu/phd_students/madhu/sdppack/sdppack.html
- [2] T. Defaix, Optimisation stochastique et allocation de plans de fréquences pour des réseaux à évasion de fréquences. Thèse de doctorat, Université de Rennes 1 (1996) 175 p.
- [3] U. Feige and J. Kilian, Zero Knowledge and the Chromatic Number, in Proc. of the 11th Annual IEEE Conference in Computing Complexity, Preliminary Version (1996) 278-287. Zbl0921.68089
- [4] A. Frieze and M. Jerrum, Improved approximation algorithms for MAX $k$-cut and MAX BISECTION, in Proc. of the Fourth MPS Conference on Integer Programming and Combinatorial Optimization. Springer-Verlag (1995) Paper Version: 21 p. Zbl1135.90420MR1367967
- [5] M.X. Goemans and D.P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42 (1995) 1115-1145. Zbl0885.68088MR1412228
- [6] D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming. J. ACM 45 (1998) 246-265. Zbl0904.68116MR1623197
- [7] M. Krivelevich and B. Sudakov, Approximate coloring of uniform hypergraphs. DIMACS Technical Report 98–31 (1998) 15 p. Zbl0928.05027
- [8] L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inform. Theory IT-25 (1979) 1-7. Zbl0395.94021MR514926
- [9] C. Lund and M. Yannakakis, On the hardness of approximating minimization problems. J. ACM 41 (1994) 960-981. Zbl0814.68064MR1371491
- [10] S. Mahajan and H. Ramesh, Derandomizing semidefinite programming based approximation algorithms, in Proc. of the 36th Annual IEEE Symposium on Foundations of Computer Science (1995) Paper Version: 19 p. Zbl0938.68915MR1619086

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.