Hostname: page-component-7bb8b95d7b-l4ctd Total loading time: 0 Render date: 2024-09-10T21:45:58.222Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  15 August 2002

Philippe Meurdesoif  and
Benoît Rottembourg
Philippe Meurdesoif
Affiliation:
Projet NUMOPT, INRIA Rhône-Alpes, 655 avenue de l'Europe, 38330 Montbonnot-Saint-Martin, France; [email protected].
Benoît Rottembourg
Affiliation:
Direction des Technologies Nouvelles, Bouygues, 1 avenue Eugène Freyssinet, 78061 Saint-Quentin-en-Yvelines, France; [email protected].
Get access

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.

Keywords

Discrete optimizationsemidefinite programming frequency assignmentgraph coloringhypergraph coloring.
Type
Research Article
Information
RAIRO - Operations Research , Volume 35 , Issue 2: ROADEF'99 , April 2001 , pp. 211 - 228
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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
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.
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.
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.
Goemans, M.X. and Williamson, D.P., Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42 (1995) 1115-1145. CrossRef
Karger, D., Motwani, R. and Sudan, M., Approximate graph coloring by semidefinite programming. J. ACM 45 (1998) 246-265. CrossRef
M. Krivelevich and B. Sudakov, Approximate coloring of uniform hypergraphs. DIMACS Technical Report 98-31 (1998) 15 p.
L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inform. Theory IT-25 (1979) 1-7.
Lund, C. and Yannakakis, M., On the hardness of approximating minimization problems. J. ACM 41 (1994) 960-981. CrossRef
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.