BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260407T234425Z
UID:Seminar-networks-632@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Giorgos Christodoulou:MAILTO:G.Christodoulou@liverpool.ac.uk
DTSTART:20171102T140000
DTEND:20171102T150000
SUMMARY:Networks and Distributed Computing Series
DESCRIPTION:Prof Prudence Wong: Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals\n\nGraph coloring has been studied extensively in the literature. The classical problem concerns the number of colors used. In this talk we focus on coloring intervals\nwhere the input is a set of intervals and two overlapping intervals cannot be assigned the same color. In particular, we are interested in the setting where there is an increasing cost associated with using a higher color index. Given a set of intervals (on a line) and a coloring, the cost of the coloring at any point is the cost of the maximum color index used at that point and the cost of the overall coloring is the integral of the cost over all points on the line. The objective is to assign a valid color to each interval and minimize the total cost of the coloring. Intuitively, the maximum color index used at each point forms a skyline and so the objective is to obtain a minimum skyline coloring. The problem arises in various applications including optical networks and job scheduling.\n\nThis is a joint work with: Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, and Shmuel Zaks.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=632
LOCATION:
END:VEVENT
END:VCALENDAR