Uni-Logo
Algorithms and Complexity
 

Graduate Course
"Combinatorial Optimization"
Winter Term 2011/12
Alexander Souza


News

  • 14.2.: Chapter 9 is published.
  • 8.2.: Sheet 7 is published. Chapter 8 is published. Remember the deadline of 11.2. for registration for the exam.
  • 25.1.: See below for the forms for evaluating this course.
  • 24.1.: Sheet 6 is published. Chapters 6 and 7 are published.
  • 17.1.: See below for even more updated exam details. PLEASE REGISTER VIA THE WEB-PAGE OF THE "Vorlesungsverzeichnis"!
  • 10.1.: See below for updated exam details. Sheet 5 is published.
  • 14.12.: .mod files of Sheets 2 and 3 are published. Chapter 5 is published.
  • 13.12.: Sheet 4 is published. Chapter 4 is published.
  • 28.11.: Sheet 3 is published. Chapter 3 is published.
  • 8.11.: Sheet 2 is published.
  • 7.11.: We have a new room for Tuesdays: 101-01-016
  • 28.10.: ILOG CPLEX for Linux is available.
  • 26.10.: Chapters 1 and 2 are published. Sheet 1 is published.

Details

  • Instructor: Dr. Alexander Souza
  • Lecture
    • Tuesday: 12-14, 101-01-016 (biweekly)
    • Wednesday: 10-12, 051-00-034
  • Tutorial
    • Tuesday: 12-14, 101-01-016 (biweekly)
  • Type: Elective, 3+1 SWS
  • ECTS-Credits: 6
  • Prerequisites: none, but "Algorithms and Datastructures" and "Algorithm Theory" might be helpful.
  • Language: English
  • Lecture Notes: Yes, made available as the course goes on.
  • Evaluation Forms: German, English. Please eMail your filled form to the Studienberatung
  • Exam
    • Type: Oral Exam
    • Date: 23./24.2.2012
    • Admission: Registration via web-page of the "Vorlesungsverzeichnis". Somewhere here.
    • Expiry date for admission: 11.2.2012.
    • Duration: 30 minutes
    • Room: 051-02-022
    • Contents: Everything except the proofs in Chapter 3 on Linear Programming
    • Style: Proofs and analysis will be asked

Objectives

Learn linear programming techniques, design polynomial time exact and approximation algorithms, study applications from logistics and operations research: Network Flows, Scheduling, Bin Packing, and more.
In the tutorials, we will also work with state-of-the-art optimization software, e.g., ILOG CPLEX.

Contents

  1. Introduction: Examples, Combinatorial Optimization Problems, Approximation Algorithms
  2. Network Flows: Maximum Flows and Minimum Cuts, Edmonds-Karp Algorithm, Minimum Cost Flows
  3. Linear Programming: Polyhedra, Duality
  4. Knapsack: Greedy, Dynamic Programming, Fully Polynomial-Time Approximation Scheme
  5. Set Cover: Greedy, Primal-Dual, LP-Rounding
  6. Satisfiability: Randomized algorithms, Derandomization
  7. Makespan Scheduling: List Scheduling, Polynomial-Time Approximation Scheme, Unrelated Machines
  8. Bin Packing: Hardness, Heuristics, Asymptotic Polynomial-Time Approximation Scheme
  9. Traveling Salesman: Hardness, Metric Traveling Salesman

Lecture Notes

Contents
  1. Introduction
  2. Network Flows
  3. Linear Programming
  4. Knapsack
  5. Set Cover
  6. Satisfiability
  7. Makespan Scheduling
  8. Bin Packing
  9. Traveling Salesman

Exercise Sheets

Schedule

Date Contents
25.10.L Introduction
26.10.L Network Flows
1.11.- Allerheiligen
2.11.L Network Flows
8.11.T Sheet 1
9.11.L Network Flows
15.11.LNetwork Flows
16.11.LNetwork Flows
22.11.TSheet 2
23.11.LLinear Programming
29.11.LLinear Programming
30.11.LLinear Programming
6.12.TSheet 3
7.12.LLinear Programming
13.12.LKnapsack
14.12.LKnapsack
20.12.TSheet 4
21.12.LSet Cover
27.12.-Christmas Break
28.12.-Christmas Break
3.1.-Christmas Break
4.1.-Christmas Break
10.1.LSet Cover
11.1.LSet Cover
17.1.TSheet 5
18.1.LSatisfiability
24.1.LSatisfiability
25.1.LMakespan Scheduling
31.1.TSheet 6
1.2.LMakespan Scheduling
7.2.LMakespan Scheduling
8.2.LBin Packing
14.2.TSheet 7
15.2.LBin Packing, Traveling Salesman
L: Lecture, T: Tutorial, -: Nothing

Software

Further Reading

  • Korte, Vygen: Combinatorial Optimization, Springer Verlag
  • Vazirani: Approximation Algorithms, Springer Verlag