**Instructor:**
Samir Khuller Office: AVW 3369. Office phone: (301) 405--6765.
E-mail: samir@cs.umd.edu.

**Office Hours:** Mon, Wed 11-12.

*
I will update this page every week during the
semester. I will place all homeworks as well
as solutions to homeworks here. If you have any trouble
accessing them, please let me know.
*

**Class Time:** Currently Scheduled for Wed 4:00--6:30pm. CSIC 2120.
My plan is to find an hour when everyone is free; and break this up into
two meetings per week.

**Course Overview:**
The main paradigm in the course will be the design and analysis of
algorithms for scheduling problems.
Scheduling problems arise in a wide variety of domains - whether it is
to schedule jobs on computers, or to distribute tasks to a collection
of people, or to schedule every day activities.

The first half of the course will cover classical works in scheduling. We will cover problems that can be solved optimally, as well as study some basic methods for establishing NP-completeness of various scheduling problems. Small changes in problem definition often change the complexity of a problem from being solvable optimally in lynomial time to being NP-hard. The second half of the course will focus on the emerging needs of "green computing". With the advent of large scale data centers, the ability to schedule tasks needs to be done in tandem with reducing the power consumption in large scale storage/compute platforms.

The focus will be to try and understand the inherent complexity of problems and we will cover several scheduling problems with the goal of emphasizing the following four topics.

- Polynomial time solvability
- NP-completeness
- Approximation Algorithms
- Online scheduling

- Learning about efficient algorithms for basic problems that are used as building blocks elsewhere. These include matching, flow, min cost flows, primal-dual methods, LP-rounding etc.
- An understanding of the inherent complexity of problems: Polynomial time, NP-completeness, Approximation Algorithms etc. We will spend a large fraction of the semester studying techniques for designing online/approximation algorithms. Many of these involve fairly mathematical proofs.

**Course Work:**
Course work will consist of a few homeworks
(answers will be discussed in class), a class presentation,
a research paper and scribing lecture notes.

**THIS IS NOT A Ph.D. CORE COURSE**

Do not forget to do the course evaluation!!!

**Grading:**

40% Research paper

30% Homeworks

20% Class presentation

10% Lecture Notes Preparation

**Homeworks:**

- Homework 1: Complete by Feb 22.
**POSTED**Solution 1 - Homework 2: Complete by Mar 7.
**POSTED**Solution 2 - Homework 3: Complete by Apr 11.
**POSTED**Solution 3

- Week 1 (Jan 25)
**Khuller**: Course Overview. Easy Scheduling Problems from books. - Week 2 (Feb 1)
**Chang & Khuller**: Unit Jobs and Unrelated Machine Scheduling - Week 3 (Feb 8)
**Chan & Khuller**: Unrelated Machines (continued) - Week 4 (Feb 15)
**Khuller**: - Week 5 (Feb 22)
**Khuller**: Weighted Completion Time - Week 6 (Feb 29):
**Mukherjee & Khuller**:Online Scheduling - Week 7 (Mar 7):
**Harris & Sarpatwar**: General Topics - Week 8 (Mar 14):
**Khuller & Purohit**: Broadcast Scheduling - SPRING BREAK
- Week 9 (Mar 28)
**Young**: Survey of results. - Week 10 (Apr 4):
**Khuller & Wang**: - Week 11 (Apr 11):
**Khuller & Tanner**: - Week 12 (Apr 18):
**Khuller & Szymczak** - Week 13 (Apr 25)
**Khuller & Chang**: - Week 14 (May 2): Work on class projects.
- Week 15 (May 9):
**Khuller**