Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary Seminar Series-Thursday, March 24, 2011

Linda Casals lindac at
Thu Mar 24 09:41:02 EDT 2011


DIMACS/CCICADA Interdisciplinary Seminar Series Presents
         a Special Seminar - Thursday, March 24, 2011

***Thursday, March 24, 2011 ** Please note special day and time***

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


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 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. 

More information about the Dimacs-ccicada-announce mailing list