Algorithmic Modelling and Complexity (AMC)
Modifications made to this document
Jan 21: Final version of lecturenotes 16 have been added.
Nov 5: The .tex files of the lecture notes of Oct. 28 have been removed
from this site.
Nov 5: Notes lecture of Nov 4 have been replaced by 2nd prelim. version.
Nov 5: Notes lecture of Nov 4 have been replaced by 2nd prelim. version.
Nov 2: Notes lecture of Nov 4 have been added.
Nov 2: Deadline for final lecture notes added.
Nov 2: Notes lecture of Nov 3 have been added.
Nov 1: Notes lecture of Nov 2 have been added.
Some older modifications.
Lecture hours AMC 2004
- Tuesday 9.00-10.45, in: BBL 505.
- Thursday 13.15-15.00, in: BBL 505.
- From week 38 onward also: Tuesday 11.00-12.45 (in: BBL 505),
see the schedule below.
- Office hours: by appointment.
- Back to main.
LaTex template: scribe.tex.
Example source file of last year:
lecture03-1.tex.
Notes posted on this site are for educational use only. They may not be
used for any other purposes without the permission of the Instructor.
Weekly schedule
Listed topics are tentative.
Week 36
- Thursday 2 september
Topics: administrivia,
research in algorithmic systems,
vehicle routing, multiple TSP.
Notes: in pdf,
in ps.
Exercises: in pdf,
in ps.
Week 37
- Tuesday 7 september
Topics: Euclidean traveling salesman problem,
Clarke-Wright savings heuristic.
Notes: in pdf,
in ps.
Exercises: in pdf,
in ps.
- Thursday 9 september
Topics: Connectivity in graphs,
Augmentation,
Steiner tree
Exercises: in pdf,
in ps.
Week 38
- Tuesday 14 september, 9.00
Topics: dominating sets,
k-centers and the lazy tourist problem.
Notes: in pdf,
in ps.
Exercises: in pdf,
in ps.
- Tuesday 14 september, 11.00
Topics: presentation of homework
- Thursday 16 september
Topics: vertex cover,
fixed parameter tractability,
(connected) vertex covers.
Notes: in pdf,
in ps.
Exercises: in pdf,
in ps.
Week 39
- Tuesday 21 september 9.00
Topics: integer linear programs and reductions,
weighted dominating set,
weighted set cover,
approximation by linear programming
Notes: in pdf,
in ps.
Exercises: in pdf,
in ps.
- Tuesday 21 september 11.00
Topics: presentation of homework
- Thursday 23 september
Topics: the set cover problem,
duality,
complemetary slackness,
approximating set cover.
Notes: in pdf,
in ps.
Week 40
- Tuesday 28 september 9.00
Topics: primal-dual methods,
the facility location problem.
Notes: in pdf,
in ps.
- Thursday 30 september
Topics: personnel assignments,
matching,
perfect and stable matchings.
Notes: in pdf,
in ps.
Week 41
- Tuesday 5 october 9.00
Topics: assignments and transportation problem,
equivalence to min cost flow and shortest path.
Notes: in pdf,
in ps.
- Tuesday 5 october 11.00
Topics: presentation of homework
- Thursday 7 october
Topics: scheduling on identical and on unrelated machines.
Notes: in pdf,
in ps.
Week 42
- Tuesday 12 october 9.00
Topics: 2SAT, 3SAT, the Davis-Putnam procedure.
Notes: in pdf,
in ps.
- Thursday 14 october Canceled.
Week 43
- Tuesday 19 october 9.00
Topics: NP-completeness,
tripartite matching, set cover again, TSP.
Notes: in pdf,
in ps.
- Thursday 21 october
Topics: pseudo-polynomial algorithms,
1-dimensional packing.
Notes: in pdf,
in ps.
Week 44
- Tuesday 26 october 9.00
Topics: The distortion problem.
Lecture by Lianne Bodenstaff and Roel van Tiel
Notes: in pdf,
in ps.
- Wednesday 27 october 15.00, BBL 505
Topics: The edge-disjoint escape problem in 2D-grids.
Lecture by Sjoerd van Hagen and Johan van Rooij
Notes: in pdf,
in ps.
- Thursday 28 october
Topics: Labeling points on a map.
Lecture by Jan Willem van den Broek and Jules van Kempen
Notes: in pdf,
in ps.
Week 45
- Tuesday 2 november
Topics: APX, in-approximability,
maximum independent set problem.
Notes: in pdf,
in ps.
- Wednesday 3 november 15.00 BBL 505
Topics: Lecture by Maarten Löffler
Notes: in pdf,
in ps.
- Thursday 4 november
Topics: Lecture by Bernard Maassen and Gerben Oostra
Notes: in pdf.
Evaluation.
- 9 november 2004 : Tentamen
- Time: 9-12 in: BBL 471
- The tentamen covers the topics (excluding the lectures by students)
treated and is `open notes'. That is, Lecture notes are allowed, even
when you have made annotations on the lecture notes. Other material
(books, journal papers, exercises, etc.) is not allowed.
- Friday, November 12, 17.00 o'clock, final version of lecture notes must
have been received by Marinus (as a tex-file, with accompanying files
if necessary).