Next year: Thursdays, February 5, 2015 — May 7, 2015; 9:15-11:00; Room TBA, Snellius.
Subject: TBA. Perhaps: Knuth, Volume 4, Fascicle 6A: Section 7.2.2.2.
Contents | Schedule | Participants | Deliverables | References
The Seminar (Combinatorial) Algorithms
is intended for Master students in Computer Science.
Lectures are in English.
The seminar is organised by
dr. H.J. (Hendrik Jan) Hoogeboom
and
dr. W.A. (Walter) Kosters.
Dates: Thursday mornings, 9:15-11:00 hours; February 6, 2014 — May 8, 2014. Room 405, Snellius.
This year's book is D.P. Williamson and D.B. Shmoys, The design of approximation algorithms, Cambridge University Press, 2011, link:
"Interesting discrete optimization problems are everywhere, from traditional operations research planning problems, such as scheduling, facility location, and network design, to computer science problems in databases, to advertising issues in viral marketing. Yet most interesting discrete optimization problems are NP-hard. Thus unless P = NP, there are no efficient algorithms to find optimal solutions to such problems. This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions."
In the first half of the semester every student presents a part
from the book above. After that
students should study recent literature (or later chapters of the book)
and present their results. And maybe do some programming ...
Meetings are on a weekly basis.
Students can also suggest neighbouring subjects. For a somewhat
more detailed list, see below.
Credit points: 6 ECTS.
There is no written exam.
Prerequisites: Algorithms, Complexity, Datastructures (all at bachelor's level, see for instance the Dutch course pages Datastructures and Complexity).
Students should register in advance, in December 2013, by personal visit to the organizers. The number of participants is at most 10 (approximately :).
Students are supposed to present and discuss chapters of the book,
and papers, during class. The setup depends on the number
of participants.
Subjects are presented by the students in two one hour lectures
(i.e., twice 40 minutes); more precisely, every student takes care of
one (academic) hour lecture twice.
Next to the oral presentations
(using PDF or PowerPoint slides, with the additional help of the
blackboard) ± ten
page self-contained essays on the subject must be written (in
LaTeX; in English).
See here for a template.
Deadline: one month after the presentation.
Essays should be improved until students and organizers
agree on the contents. Students must be present
during all sessions, and are supposed to actively
take part in the presentations, e.g., ask questions.
Immediately after each lecture there is a short
discussion between students and organizers,
where the presentation is evaluated.
The first and second meetings are used to make a proper schedule.
Every student is supposed to choose and present two subjects,
one in the first half and one in the second half of the seminar.
Students should use their own laptop for the presentations.
It is wise to also have the slides for the presentation on a memory-stick.
A beamer is always available.
Grading The final grade is composed of the four Ps: presentation (2x), paper (2x), participation (including presence) and peer review OR programming.
========== 1st half: ==============
========== 2nd half: ==============
name | remarks | |
---|---|---|
Bart Hijmans | barthijmans at G | ... |
Joost Leuven | joostleuven at ziggo | ... |
Jordi Ozir | jordi.ozir at G | ... |
Lai-yee Liu | lyliu92 at G | ... |
Mark Hoekveen | mhoekveen at G | ... |
Mathé Zeegers | mathe_zeegers at live | ... |
Michiel Vos | msvos at liacs | ... |
Pepijn van Heiningen | pepijnvanheiningen at hetnet | ... |
Ruud Heesterbeek | ruudheesterbeek at G | ... |
subject | who | remarks |
---|---|---|
Introduction (1.2,1.3) | Joost | ✓ first version handed in (30.5) and checked by W (2.6); second version handed in (24.11) and checked by HJ (22.12); final version (25.12) |
Primal/dual and rounding (1.4 & 1.5) | Jordi | ✓ first version handed in (23.3) and checked by W (26.3); second version handed in (2.5) and checked by HJ (7.7); final version (25.8) |
Greedy set cover (1.6) | Mark | ✓ first version handed in (24.3) and checked by W (25.3); second version handed in (28.3) and checked by HJ (16.5); final version (28.5) |
Randomized rounding (1.7) | Bart | ✓ first version handed in (1.4) and checked by W (4.4); second version handed in (25.4) and checked by HJ (19.5); final version (20.5) |
Greedy algorithms (2.1 & 2.2) | Michiel | ✓ first version handed in (23.3) and checked by W (24.3); second version handed in (2.4) and checked by HJ (16.5); final version (3.6) |
Scheduling jobs (2.3) | Pepijn | ✓ first version handed in (21.3) and checked by W (24.3); second version handed in (26.3) and checked by HJ (25.4); final version (29.4) |
Metric TSP (2.4) | Lai-yee | ✓ first version handed in (20.4) and checked by W (25.4); second version handed in (2.7) and checked by HJ (15.8); final version (8.9) |
Max float (2.5) | Mathé | ✓ first version handed in (30.3) and checked by W (3.4); second version handed in (27.4) and checked by HJ (20.5); final version (23.5) |
Edge coloring (2.7) | Ruud | ✓ first version handed in (25.4) and checked by W (25.4); second version handed in (17.10) and checked by HJ (11.12); final version (26.12) |
======================= | ===== | ===== |
Knapsack problem (3.1) | Joost | ✓ first version handed in (25.8) and checked by W (26.8); second version handed in (9.12) and checked by HJ (23.12); final version (25.12) |
Minimum-degree spanning trees (2.6) | Jordi | ✓ first version handed in (20.4) and checked by W (25.4); second version handed in (15.5) and checked by HJ (5.9); final version (6.10) |
Scheduling jobs 2 (4.1 & 4.2) | Michiel | ✓ first version handed in (8.5) and checked by W (12.5); second version handed in (6.6) and checked by HJ (18.7); final version (22.7) |
Randomized algorithms (5.1) | Mark | ✓ first version handed in (3.7) and checked by W (7.7); second version handed in (13.7) and checked by HJ (21.7); final version (22.7) |
Chernoff bounds (5.10, 5.11/12) | Mathé | ✓ first version handed in (6.6) and checked by W (10.6); second version handed in (15.6) and checked by HJ (18.7); final version (21.7) |
Uncapacitated facility location (9.1) | Pepijn | ✓ first version handed in (23.5) and checked by W (2.6); second version handed in (5.6) and checked by HJ (16.7); final version (18.7) |
Two graph problems (7.2) | Lai-yee | ✓ first version handed in (11.7) and checked by W (15.7); second version handed in (8.9) and checked by HJ (24.10); final version (22.12) |
The k-median problem (9.2) | Ruud | ✓ first version handed in (17.10) and checked by W (20.10); second version handed in (28.10) and checked by HJ (30.10); final version (26.12) |
Reductions from NP-complete problems (16.1) | Bart | ✓ first version handed in (16.9) and checked by W (16.9); second version handed in (19.9) and checked by HJ (20.10); final version (28.10) |
December 26, 2014 — http://www.liacs.leidenuniv.nl/~kosterswa/semalg/index.html