2WO07: Approximation algorithms
3rd quarter, 2014/15



This page: https://www.win.tue.nl/~gwoegi/2WO07/
OWinfo page: https://venus.tue.nl/owinfo-cgi/owi_0695.opl?vakcode=2WO07
Contact: Gerhard Woeginger (gwoegi@win.tue.nl)


Exam information (added June 2):

The oral exams will cover the following chapters: 2 (except 2.3), 3, 4, 5, 8, 9, 16, 17

The oral exams will take place on June 16 (from 13:00 onwards) and June 30 (from 14:00 onwards), in my office MF 4.098.


General information:

Course format: We will work through some of the 30 chapters in the book by Vazirani.

Everybody presents some of the chapters on the blackboard, discusses the contents of the chapters, and explains the main ideas to the entire group. It is strictly forbidden to use slides, hand-outs, or electronic presentation tools. The entire presentation has to be done on the blackboard (or whiteboard).

The main criteria for passing the course are clarity and independence of the presentation. The presentation must summarize the contents and the ideas of the chapter in your own words. If you mainly copy theorems from the chapter to the blackboard and/or keep reading paragraphs from the chapter to the audience, then the best possible resulting grade will be 4.

A good presentation (1) states and illustrates the considered problem, (2) states the derived main results, and finally (3) explains how these main results are derived. Concentrate on the ideas, and not on the technical details!

At the end of the course, there is a 30min oral (individual) exam where you must know and understand the contents of all chapters that have been presented.


Assignment of topics (permanent):

  1. Irene ---- Steiner tree: introduction of Chapter 3; Section 3.1
  2. Ylona ---- Cuts (1): introduction of Chapter 4; Section 4.1
  3. Emma ---- Cuts (2): Section 4.2, up to Algorithm 4.7
  4. Tristan ---- Cuts (3): Section 4.2, starting with Theorem 4.8
  5. Mark ---- k-center (1): introduction of Chapter 5; Section 5.1
  6. Remco ---- k-center (2): Section 5.2
  7. Yifan ---- Set cover (1): introduction of Chapter 2; Section 2.1
  8. Ellen ---- Set cover (2): Section 2.2
  9. Emma ---- Knapsack (1): introduction of Chapter 8; Section 8.1
  10. Tristan ---- Knapsack (2): Section 8.2
  11. Mark ---- Knapsack (3): Section 8.3
  12. Remco ---- Satisfiability (1): Chapter 16, up to Section 16.2
  13. Yifan ---- Satisfiability (2): Section 16.3
  14. Ellen ---- Satisfiability (3): Section 16.4
  15. Irene ---- Scheduling (1): Chapter 17, up to Section 17.2
  16. Ylona ---- Scheduling (2): Sections 17.3 and 17.4

Schedule of lectures (Updated: May-18):

Date Speaker Topic
fr 8 mayIrene Steiner tree
fr 8 mayYlona Cuts (1)
fr 8 mayEmma Cuts (2)
tu 19 mayTristanCuts (3)
tu 19 mayMark k-center (1)
tu 19 mayRemco k-center (2)
fr 22 mayYifan Set cover (1)
fr 22 mayEllen Set cover (2)
tu 26 mayEmma Knapsack (1)
tu 26 mayTristanKnapsack (2)
tu 26 mayMark Knapsack (3)
fr 29 mayRemco Satisfiability (1)
fr 29 mayYifan Satisfiability (2)
fr 29 mayEllen Satisfiability (3)
tu 2 juneIrene Scheduling (1)
tu 2 juneYlona Scheduling (2)


Modified on 2-June-2015