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, inapproximability and the PCP theorem, and the unique games conjecture. 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 is a pre-requisite for this class. The course textbook is:

Williamson/Shmoys: The Design of Approximation Algorithms 

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:

• Vijay Vazirani: Approximation Algorithms

• Hochbaum: Approximation Algorithms for NP-Hard Problems

• Motwani/Raghavan: Randomized Algorithms

• Kleinberg/Tardos: Algorithm Design

• Garey/Johnson: Computers and Intractability

Homework, Exams, and Grading

Although most of the lectures will be drawn from the textbook, 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 every 1-2 weeks. Homework should be submitted on Gradescope as a printable pdf file. As with all assignments submitted online, it is the student's responsibility to verify that the correct files successfully uploaded, and that the files can be read by the instructor. 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 submissions, which allow the student to turn in the homework 2 days after the due date (e.g., on a Saturday instead of a Thursday). You cannot use more than one late submission for the same homework, or use a late submission after already turning something in. 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 on Gradescope. 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 may not consult any sources except the ones specifically mentioned on the class webpage (this means no Internet, no papers that are not specifically mentioned on the webpage, no people outside of this class, no exams from previous semesters, etc). No collaboration is allowed during exams.

Use of AI tools in homeworks: you are allowed to use AI tools to help with your homework in this class. However, this would still be considered a breach of academic integrity unless you do the following: (1) Make it very clear how exactly you used the AI, and which parts are your own work. What this effectively means is: you must include the name and version of the software you used, and exactly how you used it. Include all the prompts you used (not just the final one), and all the AI responses, as well as the final version which you actually want me to grade. (2) Note that all the other requirements about academic integrity still stand: you may not search the Internet for solutions, consult any resources like other textbooks or papers or people who are not in the class, etc. If you have any questions, or are not sure what is allowed, please do not hesitate to ask the instructor after class or in office hours.

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. If you don't know how to solve a homework problem, even after thinking about it for a significant amount of time, working together with your classmates, and coming to office hours, then please submit a homework with that problem being left blank. You will still receive 50 percent of the credit for this problem. This is much better than not submitting a homework at all, or submitting a very incorrect solution, as the score in those cases would be much lower than 50 percent.

There will be a midterm exam, as well as a 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.

Additional Requirements for CSCI 6040: Some of the homeworks will include additional problems specifically for 6040. Moreover, all students registered for CS 6040 must in addition complete a report on a published research paper of their choice related to approximation algorithms. The student must read this paper, and write a report (1) summarizing the topic of this paper and its major contributions, and (2) the algorithms involved and how these algorithms address the problems in the paper. This report is due on the last day of class; any student registered for CS 6040 who does not submit such a report will automatically receive a failing grade for the semester.