### Interdisciplinary Seminar Series

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.

DIMACS/CCICADA Interdisciplinary Series, Spring 2011