Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Max-coloring and online coloring
Speaker:Rajiv Raman
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D3, D5, RG2, D2, D4, RG1, SWS
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Friday, 7 December 2007
Duration:30 Minutes
Building:E1 4
The input to the max-coloring problem is a graph G=(V,E), with

non-negative weights on the vertices. We define the weight of any proper
vertex coloring of G as follows: The cost of a color class is the
maximum weight of any vertex in this color class, and the cost of a
coloring is the sum of the weights of the color classes. The objective
is to compute a minimum weight coloring of G. The problem arises in
batch scheduling of conflicting jobs and buffer minimization.
In the online coloring problem, the graph is not known to the algorithm
at the start, and vertices are presented one at a time to the algorithm.
When a vertex is presented, the edges to previously presented vertices
is also revealed. The algorithm irrecoverably assigns a color to the
vertex before the next vertex is revealed. The objective is to assign
colors to minimize the number of colors used.
In this talk I will focus on approximation algorithms for the
max-coloring problem on various classes of graphs, and on the analysis
of the first-fit algorithm for interval graphs.

Name(s):Khaled Elbassioni
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Khaled Elbassioni, 12/05/2007 04:50 PM -- Created document.