Online algorithms for the maximum k-colorable subgraph problem. (March 2018)

• Record Type: Journal Article
• Authors: Hertz, Alain; Montagné, Romain; Gagnon, François
• Is Part Of: Computers & operations research. Volume 91(2018)
• Page Start: 209
• Page End: 224
• Publication Date: 2018-03
• Subjects: Online algorithms -- Maximum k-colorable subgraph -- Sequential vertex coloring -- Competitive analysis; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.10.003
• Languages: English
• ISSNs: 0305-0548

Abstract

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.