Datalogisk Institut
Københavns Universitet

Recent Research Results, blok 2, 2006-07

[Meddelelser] [Opgaver] [Seminar] [SIS]

Forudsætninger

Videregående Algoritmik (VA)
Introduktion til Optimering

The course will give an in-depth covering of a variety of topics in combinatorial optimiztion and the corresponding solution methods.

Forelæsninger: Tirsdag 10-12 og fredag 10-12, N037, DIKU

Foreløbig plan for kurset. Forbehold for ændringer.

Dato	Lærer	Indhold/Emne	Litteratur	Plancher	Opgaver
ti 14/11	DP	Interior point methods -- an introduction	artikel,noter	pdf	pdf, pdip.m
fr 17/11	DP	Semidefinite programming	pdf page 1-7, 13-15, 27-29, 34-35, 38-39, 41-42	pdf	pdf
ti 21/11	BP	Label-setting algorithms for shortest path problems	pdf	pdf	pdf
fr 24/11	SS	Optimal Routing with Single Backup Path Protection	Udleveres hos Simon i N325	pdf	pdf
ti 28/11	SS	General Improvement Techniques for Solving MIPs	Se referencer på slides	pdf pdf	pdf
fr 1/12	JK	A football pool problem: beat the computer!	abstract	plancher	opgaver
ti 5/12	JE	Sofa Packing	litteratur	plancher	opgaver
fr 8/12	MZ	Matrix Scaling and Applications in Election Systems	pdf,pdf	pdf	opgaver findes i plancherne
ti 12/12	MP	Algoritmer til proteinfoldning og proteinstrukturforudsigelse	litteratur	pdf	pdf
fr 15/12	PW	Evolutionary trees using distance based methods	litteratur: udleveret	pdf	opgaver
ti 2/1	BP	Vehicle Routing Problem with Time Windows solved by Branch-Cut-and-Price Seminaremner udleveres	Ingen litteratur	pdf	Ingen opgaver
fr 5/1		Fordeling af seminaremner	--	--	--
ti 9/1		--	--	--	--
fr 12/1		Seminar	--	--	--

Ved seminaret skal en af nedenstående artikler præsenteres i ca. 30 minutter. Præsentationerne sker i hold på 2 personer.

(DP) M. Laurent, F. Rendl "Semidefinite Programming and Integer Programming" ps (artiklen er lang, så der kan focuseres på et bestemt emne, f.eks.: lift-and-project, stable set problem, max-cut problem, approximation algorithms)
(MZ) Matrix Scaling pdf pdf
(PW) M. Farach, S. Kannan, T. Warnow "A Robust model for finding optimal evolutionary trees" pdf
(SS) Balas, Saxena "Optimizing over the Split Closure" pdf
(BP) G. Desaulniers, F. Lessard, A. Hadjar "Tabu Search, Generalized k-Path Inequalities, and Partial Elementarity for the Vehicle Routing Problem with Time Windows" pdf
(MP) D. Russel and L. Guibas, "Exploring Protein Folding Conformations Using Spanners", pdf
(JE)

Name

ex1

ex2

ex3

ex4

ex5

ex6

ex7

ex8

ex9

ex10

ex11

passed

Kim Vejlin

Rasmus Halland

Rikke Hamilton

Anja Westh-Liljenbøl

Ole Borup

Lasse Nisted

Thomas Gerken

Thomas Alexander Jacobsen

x = corrected
/ = corrected but less than 1/2 credit
o = handed in (not yet corrected)