BEGIN:VCALENDAR
PRODID:-//Mercury//HGEvent//EN
VERSION:2.0
METHOD:PUBLISH
BEGIN:VEVENT
STATUS:CONFIRMED
LAST-MODIFIED:20130525T201506
PRIORITY:0
CLASS:PUBLIC
UID:ATEvent-eed436ece7e23bbcfe0d4623c4969225
SUMMARY:ARC Colloquium: Debmalya Panigrahi\, Microsoft Research
DESCRIPTION:Title: Energy-efficient Scheduling in the Non-clairvoyant model\nAbstract:\nA fundamental problem in energy-efficient computing is to schedule multiple jobs released over time on a single machine with adjustable speed so as to minimize the sum of flowtime and energy. Note that the two objectives are in conflict: higher speeds reduce flowtime at the cost of increased energy consumption. In the clairvoyant version of the problem\, the parameters of a job (volume and density) are revealed when the job is released. For this problem\, a series of results culminated in a (2+epsilon)-competitive algorithm due to Bansal\, Chan\, and Pruhs. In this talk\, I will consider the non-clairvoyant version of the problem where the density of a job is revealed on release but the volume is unknown. This version is often more practical and has been widely considered in other scheduling problems. We give a constant-competitive algorithm\, which to the best of our knowledge\, is the first non-trivial result for this problem.\nOur algorithm is defined by simulating the clairvoyant algorithm in a novel inductive way\, which then leads to an inductive analytical tool that may be of independent interest for other non-clairvoyant scheduling problems.\n(Based on joint work with Yossi Azar\, Nikhil Devanur\, and Zhiyi Huang.)\n
DTSTART:20130218T130000
DTEND:20130218T130000
CREATED:20130201T101504
DTSTAMP:20130201T101504
SEQUENCE:0
LOCATION:
END:VEVENT
END:VCALENDAR