The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


                            Computer Science Seminar

                              Magnus  Halldorsson
                             University of Iceland


                                 will speak on


                         Average coloring planar graphs

Abstract:
When coloring graphs, some colors may be more preferable to others.  We can
then rank them and try to minimize the average color assigned to a vertex. This
is also known as the Chromatic Sum or Sum Coloring problem. Some of the
motivation for this problem comes from resource allocation, and other
scheduling problems, under the sum-of-completion-times or mean flow time
measures.

In this talk, we focus on planar graphs, the original object of graph coloring
research. The average coloring problem is NP-hard on planar graphs, but we
present a polynomial time approximation scheme (PTAS). We then discuss an
extension of the problem, where the vertices have color requirements,
corresponding to job lengths in the scheduling scenario. En route to deriving a
PTAS for this generalization, we run into a variation on Markov's inequality
which may be interesting in its own right.

This is joint work with Guy Kortsarz.




                      The lecture will take place in the 
                     Lecture Hall, Room 1, Ziskind Building
                          on Monday, December 4, 2000
                                 14:30 - 15:30