Online algorithms for the maximum k-colorable subgraph problem. (March 2018) - Hertz, Alain; Montagné, Romain; Gagnon, François
Highlights: The maximum k-colorable subgraph problem ( k -MCSP), which is to color as many vertices as possible with at most k colors can model a resource allocation problem in a wireless network: the vertices of the graph are mobile users of the network to which a channel (or color) must be assigned, the edges correspond to interferences, and the aim is to maximize the number of simultaneously communicating mobiles. We consider online algorithms for this NP-hard problem. We give bounds on the competitive ratio of online algorithms for the k -MCSP. We compare the performance of several online sequential coloring algorithms, using DIMACS benchmark instances. Abstract: The maximum k -colorable subgraph problem ( k -MCSP) is to color as many vertices as possible with at most k colors, such that no two adjacent vertices share the same color. We consider online algorithms for this NP -hard problem, and give bounds on their competitive ratio. We then consider a large family A of online sequential coloring algorithms and determine the smallest graphs for which no algorithm in A can produce an optimal solution to the k -MCSP. We then compare the performance of several online sequential coloring algorithms, using DIMACS benchmark instances. We finally consider the case where vertices colored at an early stage can receive a new color later on, as long as they remain colored.