Research Interests

As brief as possible, this ordered list of (overlapping) areas characterize my interests:
Online Algorithms, Data Structures, Database Systems, Algorithmics.
A slightly more detailed description is given below, and some impression can be obtained by checking my publication list, list of students, and list of courses.

Online Algorithms

My primary interest has been performance measures; in particular the accommodating function and relative worst order analysis. Along the way, I have worked with many concrete online problems, including bin packing (fair and unfair variants), call control, inventory management, k-server, list accessing, packet bundling (dynamic TCP acknowledgment), paging, scheduling, seat reservation, and unit clustering.

Data Structures

Most of my work in this area has dealt with search trees with relaxed balance, involving variants of B-trees, AVL-trees, red-black trees, and other structures. I have also looked at chronological transcript operations in persistent search trees as well as various amortized analysis issues

Database Systems

My work on search trees with relaxed balance came out of a database index motivation. I have also worked on smooth incorporation of grouping and domain value computation in relational algebra and on various query optimization issues, limiting the need for sorting of temporary results.

Algorithmics

In addition to the problems areas above (most of which fall under the headline of algorithmics), I have touched upon the following:


Last modified: Fri Jul 30 15:36:29 CEST 2010
Kim Skak Larsen (kslarsen@imada.sdu.dk)