Facets of the minimum-adjacency vertex coloring polytope
Diego Delle Donne(ddelledoungs.edu.ar)
Abstract: In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation of the minimum-adjacency vertex coloring problem which, given an interference graph G representing the potential interference between the antennas and a set of prespecified colors/channels, asks for a vertex coloring of G minimizing the number of edges receiving adjacent colors. We propose an integer programming model for this problem and present two families of facet-inducing valid inequalities.
Keywords: frequency assignment, adjacent colors, integer programming
Category 1: Combinatorial Optimization (Polyhedra )
Category 2: Integer Programming (0-1 Programming )
Citation: Technical Report, Universidad Nacional de General Sarmiento, October 2010.
Entry Submitted: 10/01/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|