Title: Some heuristics for the binary paint shop problem and their expected number of colour changes
Speaker: Winfried Hochstaettler, University of Hagen, Germany
Date: Thursday, March 24, 2011 1:00 - 2:00 pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In the binary paint shop problem we are given a word on $n$ characters of length $2n$ where every character occurs exactly twice. The objective is to colour the letters of the word in two colours, such that each character receives both colours and the number of colour changes of consecutive letters is minimized. Amini et.\ al proved that the expected number of colour changes of the heuristic greedy colouring is at most $2n/3$. They also conjectured that the true value is $n/2$. We verify their conjecture and, furthermore, compute an expected number of $2n/3$ colour changes for a heuristic, named {\em red first}, which behaves well on some worst case examples for the greedy algorithm.
From our proof method, finally, we derive a new recursive greedy heuristichich achieves an average number of $2n/5$ colour changes.