Paper Info
Title
A comparison of integer programming models for the partial directed weighted improper coloring problem
Abstract
Given a complete directed graph G with weights on the vertices and on the arcs, a θ-improper k-coloring of G is an assignment of at most k different colors to the vertices of G such that the weight of every vertex v is greater, by a given factor 1θ, than the sum of the weights on the arcs (u,v) entering v, with the tail u of the same color as v. For a given real number θ and an integer k, the Partial Directed Weighted Improper Coloring Problem ((θ,k)-PDWICP) is to determine the order of the largest induced subgraph G′ of G such that G′ admits a θ-improper k-coloring. The (θ,k)-PDWICP appears as a natural model when solving channel assignment problems that aim to maximize the number of simultaneously communicating mobiles in a wireless network. In this paper, we compare integer programming approaches to solve this NP-hard problem to optimality. A polynomial-time computable upper bound inspired by the Lovász ϑ(G) function, and valid inequalities based on the knapsack and set-packing problems are embedded in a branch-and-bound procedure. Comparisons with a branch-and-price scheme clearly show that the latter is much more effective than branch-and-cut-based methods.
Year
DOI
Venue
2019
10.1016/j.dam.2018.08.026
Discrete Applied Mathematics
Keywords
Field
DocType
Weighted improper vertex coloring,Integer programming,Valid inequalities,Branch-and-cut,Branch-and-price
Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Upper and lower bounds,Directed graph,Induced subgraph,Integer programming,Knapsack problem,Real number,Mathematics
Journal
Volume
ISSN
Citations 
261
0166-218X
0
PageRank 
References 
Authors
0.34
5
3
Name
Order
Citations
PageRank
alain hertz11347107.41
Romain Montagné211.70
Francois Gagnon313133.07