Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Greedy colorings for the binary paintshop problem

Abstract : Cars have to be painted in two colors in a sequence where each car occurs twice; assign the two colors to the two occurrences of each car so as to minimize the number of color changes. This problem is denoted by PPW (2, 1). This version and a more general version-with an arbitrary multiset of colors for each car-were proposed and studied for the first time in 2004 by Epping, Hochstättler and Oertel. Since then, other results have been obtained: for instance, Meunier and Sebo{combining double acute accent} have found a class of PPW (2, 1) instances for which the greedy algorithm is optimal. In the present paper, we focus on PPW (2, 1) and find a larger class of instances for which the greedy algorithm is still optimal. Moreover, we show that when one draws uniformly at random an instance w of PPW (2, 1), the greedy algorithm needs at most 1/3 of the length of w color changes. We conjecture that asymptotically the true factor is not 1/3 but 1/4. Other open questions are emphasized. © 2008 Elsevier B.V. All rights reserved.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-enpc.archives-ouvertes.fr/hal-00835222
Contributeur : Frédérique Bordignon <>
Soumis le : mardi 18 juin 2013 - 13:38:27
Dernière modification le : vendredi 17 juillet 2020 - 17:08:53

Lien texte intégral

Identifiants

Collections

Citation

H. Amini, Frédéric Meunier, H. Michel, A. Mohajeri. Greedy colorings for the binary paintshop problem. Journal of Discrete Algorithms, Elsevier, 2010, 8 (1), pp.8--14. ⟨10.1016/j.jda.2008.05.002⟩. ⟨hal-00835222⟩

Partager

Métriques