ARC Colloquium: Debmalya Panigrahi, Microsoft Research

Event Details
  • Date/Time:
    • Monday February 18, 2013 - Tuesday February 19, 2013
      12:00 pm - 11:59 am
  • Location: KACB 1116W
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:


Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

Title: Energy-efficient Scheduling in the Non-clairvoyant model


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

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

(Based on joint work with Yossi Azar, Nikhil Devanur, and Zhiyi Huang.)

Additional Information

In Campus Calendar

College of Computing, School of Computer Science, ARC

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Jan 28, 2013 - 4:50am
  • Last Updated: Oct 7, 2016 - 10:02pm