# Home Page for CMSC 858T (Topics in Algorithms: Scheduling)

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
I expect that the students are already familiar with the material from CMSC 451 (minimum spanning trees, shortest paths, dynamic programming, NP-completeness etc.).

### Goals:

• 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.
Approximation Compendium .

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: