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

Philippe Meurdesoif; Benoît Rottembourg

RAIRO - Operations Research (2010)

  • 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 Kn-Coloring in Frequency Assignment." RAIRO - Operations Research 35.2 (2010): 211-228. <http://eudml.org/doc/197841>.

@article{Meurdesoif2010,
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},
keywords = {Discrete optimization; semidefinite programming frequency assignment; graph coloring; hypergraph coloring.; discrete optimization; semidefinite programming; frequency assignment; hypergraph coloring},
language = {eng},
month = {3},
number = {2},
pages = {211-228},
publisher = {EDP Sciences},
title = {Semi-Definite positive Programming Relaxations for Graph Kn-Coloring in Frequency Assignment},
url = {http://eudml.org/doc/197841},
volume = {35},
year = {2010},
}

TY - JOUR
AU - Meurdesoif, Philippe
AU - Rottembourg, Benoît
TI - Semi-Definite positive Programming Relaxations for Graph Kn-Coloring in Frequency Assignment
JO - RAIRO - Operations Research
DA - 2010/3//
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.; discrete optimization; semidefinite programming; frequency assignment; hypergraph coloring
UR - http://eudml.org/doc/197841
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:  URIhttp://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.  
  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.  
  5. M.X. Goemans and D.P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM42 (1995) 1115-1145.  
  6. D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming. J. ACM45 (1998) 246-265.  
  7. M. Krivelevich and B. Sudakov, Approximate coloring of uniform hypergraphs. DIMACS Technical Report 98-31 (1998) 15 p.  
  8. L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inform. TheoryIT-25 (1979) 1-7.  
  9. C. Lund and M. Yannakakis, On the hardness of approximating minimization problems. J. ACM41 (1994) 960-981.  
  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.  

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.