Some heuristics for the binary paint shop problem and their expected number of colour changes

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/32n/3. They also conjectured that the true value is asymptotically n/2n/2. We verify their conjecture and, furthermore, compute an expected number of (2n+1)/3(2n+1)/3 colour changes for a heuristic, named 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 heuristic which achieves an average number of 2n/5+O(1)2n/5+O(1) colour changes.