This is an old revision of the document!
Upper and Lower Bounds for the Minimum Sum Coloring Problem
In this work, we study upper and lower bounds of the Minimum Sum Coloring Problem (MSCP) from a uniform point of view. MSCP is a graph coloring problem whose goal is to minimize the sum of colors, where colors are represented by natural numbers. We propose calculating upper and lower bounds for MSCP using a single coloring algorithm: a Memetic Algorithm (MA) hybridizing a simple genetic algorithm with local search. Our lower bound is based on partitioning the original graph into cliques. In this context we define a new problem for obtaining this kind of general lower bound, namely Partition into Cliques for MSCP (PCMSCP), and prove its NPcompleteness. We test our algorithm and compare it with other algorithms in the literature, and we also present the new results for some instances from the commonly used benchmark instances in order to provide a basis for future work. Experimental results show that our approach strictly improves or attains the lower bounds in the literature, and for the upper bounds the result of our algorithm is comparable. This work allows to optimally solve 27 instances for MSCP and 36 instances for PCMSCP among 81 tested ones.
People involved Yu Li Corinne Lucet Aziz Moukrim Kaoutar Sghiouer
References  Y. Li, C. Lucet, A. Moukrim, and K. Sghiouer. Greedy algorithms for the minimum sum coloring problem. In International Workshop: Logistics and transport, 2009.  A. Moukrim, K. Sghiouer, C. Lucet, and Y. Li. Lower bounds for the minimum sum coloring problem. Electronic Notes in Discrete Mathematics, 36:663–670, 2010. A. Moukrim, K. Sghiouer, C. Lucet, and Y. Li. Upper and Lower Bounds for the Minimum Sum Coloring Problem. Submitted, january 2013.