Algorithms Research

The Algorithms Group at Computing Science, Chalmers

This group reflects a general interest in algorithms, with particular focus on discrete optimisation, macine learning and bioinformatics. Within optimisation we form a joint group together with the optimisation group at mathematics. We also participate in the joint Chalmers effort in bioinformatics in cooperation with the other departments of the School of Mathematics and Computing Sciences, and several departments of biology and medicine.

One of our specialisations is efficent algorithms for discrete optimisation. An implementation of one of our optimisation algorithms is used in the Carmen System for airline crew scheduling, which is used by all major European airlines. Another of our projects within the field of machine learning and data mining, have made us and IVEE Development AB to winners in the European IT-prize competition. Here is a short summary of the project.

Research areas and ongoing projects

Large scale 0-1 integer programming The group has developed a new type 0-1 integer optimiser that can solve very large problems with high quality.

Algorithmic and machine learning issues in bioinformatics

On-line algorithms. This research involves making decisions in real time and in spite of ignorance of the future and competitive analysis of the performance.

Combinatorial algorithms: We study different reconstruction, recognition, and optimization problems in discrete structures, such as special graphs. Some are extensions of classical problems in the field - easy to formulate but hard to solve.

Distributed algorithms.

Probabilistic Analysis. One of our group members is currently working on a research monograph which will be part of the series on Algorithms and Combinatorics (Springer-Verlag).

Machine learning and data mining. This project concerns the development of efficient algorithms for discovering the interaction structure in a data set, in terms of a Markov graph. Recently, we have investigated how our algorithms can be integrated with the visual data mining product Spotfire.

Probabilistic inference. This project concerns effient inference of under uncertainty, typically in a probabilistic expert system.

Cost Propagation. In this project, we analyse and extend the algorithm developed in the project Large scale 0-1 integer programming

Routing algorithms: In this project we cooperate with different companies in the development of routing algorithms for specific applications.

Previous projects

is at present the largest project of the group. PAROS is an ESPRIT-project which is devoted to increase the performance of automatic scheduling methods with particular emphasis on airline crew scheduling.

Group members

The group consists of the following active members:

Previous members:

Rene van Dal
Tomas Gustafsson (applied mathematics)
Roland Olsson
Magnus Oskarsson (applied mathematics)

Related seminars

Related courses

The following courses are either given by members of the Algorithms group or are strongly connected to our ongoing research.

Some publications

Wedelin D. (1995). An algorithm for large scale 0-1 integer optimization. Annals of Operations Research 57.
Wedelin D. (1995).The design of an 0-1 optimizer and its application in the Carmen System. European Journal of Operational Research 87. This is an easy to read short introduction to the algorithm presented in the previous paper.
Olsson J. R. (1995), Inductive functional programming using incremental program transformation, Artificial Intelligence, volume 74, number 1.
Wedelin D. (1996). Efficient estimation and model selection in large graphical models. Statistics and Computing 6.
Dubhashi D.P. (1997), "Simple Proof of Occupancy Tail Bounds", Random Structures and Algorithms, 11 pp. 119-123.
Breslauer D., Czumaj A., Dubhashi D.P. and Meyer auf der Heide F. (1997): "Transforming Comparison Model Lower Bounds to the Parallel Random Access Machine", Information Proc. Letters 62(2) pp. 103--110.
Andersson E., Housos E., Kohl N., Wedelin D. (1997). Crew Pairing Optimization . Yu G. (Ed.) (1998). Operations Research in the Airline Industry. Kluwer Scientific Publishers.
Dubhashi D.P. and Ranjan D. (1998), "Balls and Bins: A Study in Negative Dependence", Random Structures and Algorithms, 13(2), pp. 99--124.
Dubhashi D., Grable D. and Panconesi A. (1995/98), "Near Optimal Distributed Edge Colouring via the Nibble Method", European Symposium on Algorithms, September 1995. Invited for the special issue of Theoretical Computer Science devoted to ESA'95, 203, pp. 225--251, 1998.
Chaudhuri S. and Dubhashi D. (1998): "(Probabilistic) Recurrence Relations Revisited", Invited for the special issue of Theoretical Computer Science for LATIN 95, 181(1) pp. 45--56.
Dubhashi D.P. (1998): "Talagrand's Inequality and Locality in Distributed Computing", RANDOM 98, the Second Workshop on Randomization and Approximation Methods in Computer Science, Barcelona, Spain, LNCS 1444 pp. 60--70, Springer Verlag.
Dubhashi D.P. (1998): "Martingales and Locality in Distributed Computing", FSTTCS 98, the Foundations of Software Technology and Theoretical Computer Science, Chennai India, December 1998, Springer LNCS 1530, pp. 174 -- 185, Springer--Verlag 1998.
Oskarsson M. (1999). A Decision Support System for Scheduling a Shop Floor Work Center. Licentiate thesis, Dept. of Mathematics, Chalmers Univ. of Tech.
Gustafsson T. (1999). A heuristic approach to column generation for airline crew scheduling. Licentiate thesis, Dept. of Mathematics, Chalmers Univ. of Tech.
Takkula, T. (2001). The dual of integer programs. Licentiate thesis, Dept. of Computing Science, Chalmers Univ. of Techn.
Swain, M.T. and Kemp, G.J.L. (2001). A CLP approach to the protein side-chain placement problem. In Walsh, T. (ed.) Principles and Practice of Constraint Programming - CP2001, Lecture Notes in Computer Science (vol. 2239), Springer-Verlag, Berlin, pp 479-493.
Dubhashi D. and Sen S. (2001): "Concentration of Measure for the Analysis of Algorithms", in P.Pardalos, S. Rajasekhar and J. Rolim (eds) Handbook of Randomized Computing, Elsevier 2001.
Dubhashi D., Mei A., Panconesi A., Radhakrishnan J., A. Srinivasan (2003): "Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear Size Skeletons, to appear, ACM Symposium on Discrete Algorithms.
More publications can be found on the group member's homepages.

dag@cs.chalmers.se

Last modified: Fri Nov 15 10:14:05 MET 2002 by Birgit