Approximation Algorithms

Computer Science 6040/4040
Fall 2017

Instructor: Elliot Anshelevich
311 Lally Hall, 518-276-6491
first letter of first name + first 6 letters of last name AT cs dot rpi dot edu

Time and Place: Mondays and Thursdays, 2:00pm-3:50pm, Amos Eaton 215
Office Hours: Monday and Thursday 4:00pm-5:00pm (or by appointment)


Announcements:

10/16/17 - Problem Set 5 is out. It is due Thursday, October 26.
10/05/17 - Problem Set 4 is out. It is due Thursday, October 19.
09/28/17 - Midterm Exam is out. It is due Tuesday, October 10. This exam is individual work.
09/25/17 - Problem Set 3 is out. It is due Monday, October 2.
09/14/17 - Problem Set 2 is out. It is due Monday, September 25.
08/31/17 - Problem Set 1 is out. It is due Thursday, September 14.


Class Schedule


Course Overview

Algorithms with provable guarantees on the quality of their solutions are a powerful way of dealing with intractable problems. This course is an advanced course in approximation algorithms; it will cover fundamental techniques for designing approximation algorithms as well as more specialized topics. Possible topics include: semi-definite and linear programming, iterated rounding, metrics and cuts, primal-dual methods, online algorithms, and approximations in game theory, markets, and auctions. We will look at algorithms in a variety of settings; some of these may include social networks, graph partitioning, network design and routing, traveling salesman problems, and many applications in communication networks. Course Learning Objectives: Students who successfully complete this course will be able to analyze and design efficient approximation algorithms for a variety of computational problems. They will also be able to communicate their ideas in the form of precise algorithm descriptions and rigorous proofs.

Pre-requisites and Books

CSCI 4020/6210 is a pre-requisite for this class. The course textbook is:

It should be available at the campus store, and can also be downloaded for free from the publisher. Other books which should be very useful for reference and for different perspectives are: During the second portion of the course, we will focus especially on approximation in game theory and related topics. The required textbook for this portion is:
It should be available at the campus store, and can also be downloaded for free from the publisher. (See here for Errata.) You may also find the following books useful for reference and for different perspectives:

Homework, Exams, and Grading

Although most of the lectures will be drawn from the textbooks, we will cover many topics that do not appear in the text, and the textbooks include material that we will not cover in class. You are responsible for the content of the lectures. If you miss a lecture make sure to get notes from another student, or ask the instructor about the topics covered. Students are encouraged to attend all classes. Your active in-class participation will be a substantial part of your learning process, and will be taken into consideration when final grades are determined.

Homeworks will be assigned approximately every 2 weeks. There will not be any programming assignments. Homeworks should be handed in at the beginning of lecture on the day they are due. Late homeworks will not be accepted, except in case of a genuine emergency. An exception to this is that every student is allocated two late days, which allow the student to turn in the homework during the class following the due date (e.g., on a Monday instead of a Thursday). Any request to re-evaluate a grade must be made within one week of the return date of the homework or exam in question. You must explain why you think your grade should be changed in writing, and submit your request together with the original problem solution. The second grade will remain.

You are allowed (and encouraged) to discuss homework problems with other members of the class, and to formulate ideas together. However, everyone must write up their assignments separately, and include the names of everyone you discussed the assignment with. You may not copy (or near-copy) a solution from another student or another source; everything you turn in must be your own work. Failure to write the solution to a homework completely on your own will be considered a breach of academic integrity, and may result in the final grade being reduced by a letter and a 0-grade for the homework for both parties. You can use the class textbooks when thinking about problems, but no other sources. No collaboration is allowed during exams.

You are required to prove your statements, unless otherwise specified. If a homework or exam question asks you to design an algorithm for a certain task, then the answer must consist of a description of the algorithm (an English description is fine), as well as an analysis of its running time and a proof of its correctness.

There will be a take-home midterm exam due on October 10, as well as a non-take-home final exam during finals week. Unlike the homeworks, you must complete them entirely on your own. The final exam will be worth 30% of your grade, the midterm 20%, and the homework will be worth 50%. Final scores will correspond to the following letter grades: A/A-: 85-100; B+/B/B-: 70-85; final scores of less than 70 percent will result in a failing grade.