Recent Research Results (course 459, spring 2002)

Course plan

Date	Topic	Speaker	Literature
8. Febr.	The greedy algorithm (matching, 4-block-free bipartite graphs) (classic result)	JK	[1], [2], [3]
15. Febr.	Variants of the Steiner problem in graphs (recent research)	DGJ	slides, exercises
22. Febr.	The p/q-active facility location problem (recent research)	JK
1. March	Sorting and searching on a word-RAM (classic result)	DP	[6] slides, exercises
8. March	Dynamic programming on a word-RAM (recent research)	DP	[7] slides, exercises
15. March	Steiner trees in uniform orientation metrics (classic result)	MZ	[8] slides, exercises
22. March	Rectilinear Steiner trees with secondary objectives (recent research)	MZ	[9] slides, exercises
29. March	No teaching
5. April	Lower bounds for the n-dimensional bin packing problem (classic research)	MS
12. April	Improved algorithms for the Steiner problem in networks (classic result)	DGJ	[12]
19. April	Decomposition techniques and constraint programming for 2D bin packing problems (recent research)	MS
26. April	No teaching
3. May	Voronoi Diagrams with Applications (classic result)	PW	slides
10. May	Geometric Network Design (recent research)	PW
17. May	Seminar	Group 1, 2, 3
24. May	Seminar	Group 4, 5, 6

GROUP 1: Jacob Blom Andersen, Martin Paluszewski
2D Bin Packing Problems, heuristic approaches
GROUP 2: Rune Sandvik, Anders Bo Rasmussen
2D Bin Packing Problems, lower bounds and exact algorithms
GROUP 3: Rasmus Erik Voel, Mikkel Larsen
An approximation algorithm (own results!)
GROUP 4: Ulf Worsøe, Christian Jul Jensen
Multiconnected Steiner Problems
GROUP 5: Philip Bille, Lorenzo Venerucci
Dictionaries in linear space on word-RAM
GROUP 6: Allan Ebdrup: Stifinder algoritme (paper)

Friday 10.15-12.00 in N037

Teachers

JK: Jakob Krarup, krarup@diku.dk

DGJ: David Grove Jørgensen, david@diku.dk

DP: David Pisinger, pisinger@diku.dk

MS: Mikkel Sigurd, sigurd@diku.dk

PW: Pawel Winter, pawel@diku.dk

MZ: Martin Zachariasen, martinz@diku.dk

References

The papers will be handed out one week before the lecture:

[1] J. Clausen, J. Krarup, "Arranging apples in an array", BIT 28 (1988) 552-568.

[2] J. Clausen, J. Krarup, "A family of bipartite cardinality matching problems solvable in O(n2) time", Nordic Journal of Computing 2 (1995) 496-501.

[3] T. Illes, J. Krarup, "Maximum 4-block-free matrices and knapsack-type relaxations", Pure Mathematics and Applications 10 (1999) 115-131.

[6] Torben Hagerup. Sorting and searching on the Word RAM. In Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science, pages 366--398. SpringerVerlag, 1998.

[7] David Pisinger. Dynamic Programming on the Word RAM.

[8] M. Brazil, D. A. Thomas, J. F. Weng, "Minimum Networks in Uniform Orientation Metrics", SIAM Journal on Computing 30, 1579--1593, 2000.

[9] S. Peyer, M. Zachariasen, D.G. Jørgensen, "Delay-related Secondary Objectives for Rectilinear Steiner Minimum Trees", Tech. Rep. 01913, Forschungsinstitut für Diskrete Mathematik, University of Bonn, 2001.

[12] Tobias Polzin and Siavash Vahdati Daneshmand "Improved algorithms for the Steiner problem in networks" Discrete Applied Mathematics 112 (2001) 263-300 (online)

Seminar topics

(PW) Applications of Voronoi diagrams, according to your own (well-considered) choice. An overview of several applications is found at http://www.voronoi.com/application.htm
(PW) A sweepline algorithm for Voronoi diagrams, S. Fortune, Algorithmica 2 (1987) 153-174. A good description is also found in M. de Berg et al., Computational Geometry, Springer 2000
(PW/MZ) Multiconnected Steiner Networks (both in graphs and in the plane)
(MZ) Uniformly-Oriented Steiner Trees for a given Topology (paper)
(DP) Longest-Common-Subsequence on the word RAM. See the paper Allision og Dix ``A Bit-String Longest-Common-Subsequence Algorithm'' Information Processing Letters 23 305-310 (1986), which is also found here.
(DP) Neighbor Dictionaries Using Linear Space (Section 6 in Hagerup "Sorting and Searching on the word RAM" [6])

Credit

To obtain full credit the participants should

Attend the lectures
Make 2/3 of the home exercises
give a seminar at the end of the course

Home Exercsies

The following exercises have been handed in for correction

Name

8/2

15/2

22/2

1/3

8/3

15/3

22/3

5/4

12/4

19/4

3/5

DGJ

bestået

Anders Bo Rasmussen

Rasmus Erik Voel Jensen

Ulf Worsøe

Anders Bruun Krusell

ok (- pres)

Christian Jul Jensen

Allan Ebdrup

Egil Hauge Larsen

Adam Rosenberg

Rune Sandvik

Jacob Blom Andersen

Martin Paluszewski

Michael Lodberg Samuel

Mikkel Larsen

Philip Bille

Lorenzo Venerucci

Steffen Nissen

Thomas Bindzus

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

[ Upwards | DIKU Home ]

Last updated May 24, 2002, pisinger@diku.dk