Semi-definite positive programming relaxations for graph K 𝐧 -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

Abstract

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

How to cite

top

Meurdesoif, 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. [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. [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. [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. [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. [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. [6] D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming. J. ACM 45 (1998) 246-265. Zbl0904.68116MR1623197
  7. [7] M. Krivelevich and B. Sudakov, Approximate coloring of uniform hypergraphs. DIMACS Technical Report 98–31 (1998) 15 p. Zbl0928.05027
  8. [8] L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inform. Theory IT-25 (1979) 1-7. Zbl0395.94021MR514926
  9. [9] C. Lund and M. Yannakakis, On the hardness of approximating minimization problems. J. ACM 41 (1994) 960-981. Zbl0814.68064MR1371491
  10. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.