en:mscp

This shows you the differences between two versions of the page.

Next revision | Previous revision | ||

en:mscp [2013/05/14 08:33] moukrim created |
en:mscp [2013/09/21 23:28] (current) moukrim |
||
---|---|---|---|

Line 1: | Line 1: | ||

- | Upper and Lower Bounds for the Minimum Sum Coloring Problem | + | ====== Upper and Lower Bounds for the Minimum Sum Coloring Problem ====== |

- | | + | === Description === |

- | Description | + | |

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 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 | ||

Line 7: | Line 6: | ||

- | People involved | + | === People involved === |

- | Yu Li | + | Yu Li\\ |

- | Corinne Lucet | + | Corinne Lucet\\ |

- | Aziz Moukrim | + | Aziz Moukrim\\ |

- | Kaoutar Sghiouer | + | Kaoutar Sghiouer\\ |

- | References | + | === References === |

- | [1] Y. Li, C. Lucet, A. Moukrim, and K. Sghiouer. Greedy algorithms for the minimum sum coloring problem. In International Workshop: Logistics and transport, 2009. | + | [1] Y. Li, C. Lucet, A. Moukrim, and K. Sghiouer. Greedy algorithms for the minimum sum coloring problem. In International Workshop: Logistics and transport, 2009.\\ |

- | [2] A. Moukrim, K. Sghiouer, C. Lucet, and Y. Li. Lower bounds for the minimum sum coloring problem. Electronic Notes in Discrete Mathematics, | + | [2] A. Moukrim, K. Sghiouer, C. Lucet, and Y. Li. Lower bounds for the minimum sum coloring problem. Electronic Notes in Discrete Mathematics,\\ |

- | [3]A. Moukrim, K. Sghiouer, C. Lucet, and Y. Li. {{en:mscp_23_janvier_2013.pdf|Upper and Lower Bounds for the Minimum Sum Coloring Problem}}. Submitted, january 2013. | + | [3] A. Moukrim, K. Sghiouer, C. Lucet, and Y. Li. {{en:mscp_cor13septembre2013.pdf|Upper and Lower Bounds for the Minimum Sum Coloring Problem}}. Submitted January 2013 and revised September 2013. |