Improved Bounds for the Binary Paint Shop Problem
摘要
We improve bounds for the binary paint shop problem posed by Meunier and Neveu [Computing solutions of the paintshop-necklace problem. Comput. Oper. Res. 39, 11 (2012), 2666-2678]. In particular, we disprove their conjectured upper bound for the number of color changes by giving a linear lower bound. We show that the recursive greedy heuristics is not optimal by providing a tiny improvement. We also introduce a new heuristics, recursive star greedy, that a preliminary analysis shows to be 10% better.