Fundamental Algorithms for Combinatorial Optimization Problems


Duration: Jan. 2007 - Nov. 2007
Project heads: Prof. Dr. Rolf H. Möhring and Dr. Guido Schäfer
Fakultät II - Mathematik und Naturwissenschaften
Institut für Mathematik, Sekr. MA 5-1
Technische Universität Berlin
Straße des 17. Juni 136
Phone: +49 30 - 314 25728 (Secretary)
Email: {moehring|schaefer} 'at'
Members: Andre Berger
Vincenzo Bonifaci
Feodor Dragan
Fabrizio Grandoni
Tobias Harks
Ralf Hoffmann
Ulf Lorenz
Martin Oellrich
Rajiv Raman
Alexander Souza
Björn Stenzel
Tjark Vredeveld
Gregor Wünsch
Yong Zhang
Associated members:
Ewgenij Gawrilow
Ekkehard Köhler
Felix König
Marco Lübbecke
Nicole Megow
Sebastian Stiller
Support: Programm zur Förderung von Forschung, Innovationen und Technologien (ProFIT),
partially supported by the European Regional Development Fund (ERDF/EFRE).
Quick Links: Publications

Project description.

The aim of this project is to design, analyze and experimentally evaluate algorithms for fundamental combinatorial optimization problems. A particular focus will be given to optimization problems that arise in the application areas telecommunication, traffic and logistics.


A partial list of the problems that have been studied within the project, classified according to their respective application areas, is as follows:

The results that have been achieved within this project can be summarized as follows.

The outcomes of the project were presented to interested industry partners in February 2008; the program is available as [pdf] (in German).


[1] A. Berger, V. Bonifaci, F. Grandoni, and G. Schäfer.
Budgeted matching and budgeted matroid intersection via the gasoline puzzle.
In Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization, 2008, to appear.
[2] A. Berger, R. Hoffmann, U. Lorenz, and S. Stiller.
Railway Delay Management: A Simulation Tool.
Website: TOPSU-RDM.
[3] A. Berger, R. Hoffmann, U. Lorenz, and S. Stiller.
TOPSU-RDM: A simulation platform for railway delay management.
In Proceedings of the 1st International Conference on Simulation Tools and Techniques for Communications, Networks and Systems, 2008, to appear.
[4] V. Bonifaci, T. Harks, and G. Schäfer.
The impact of Stackelberg routing in general networks.
Preprint 020-2007, Technische Universität Berlin, 2007.
[5] V. Bonifaci, P. Korteweg, A. Marchetti-Spaccamela, and L. Stougie.
Minimizing flow time in the wireless gathering problem.
In Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science, 2008.
[6] F. Y. L. Chin, H. Ting, and Y. Zhang.
A constant-competitive algorithm for online OVSF code assignment.
In Proceedings of the 18th Annual International Symposium on Algorithms and Computation, pages 452-463, 2007. Invited to special issue of Algorithmica.
[7] F. Y. L. Chin and Y. Zhang.
Constant-competitive tree node assignment, 2008, submitted.
[8] F. Y. L. Chin, Y. Zhang, and H. Zhu.
A 1-local 4/3-competitive algorithm for multicoloring triangle-free hexagonal graphs.
In Proceedings of the 13th Annual International Computing and Combinatorics Conference, pages 526-536, 2007. Invited to special issue of Algorithmica.
[9] D. G. Corneil, F. F. Dragan, E. Köhler, and Y. Xiang.
Additive spanners for circle graphs and polygonal graphs, 2008, submitted.
[10] F. F. Dragan and F. V. Fomin and P. Golovach.
A PTAS for the sparsest spanners problem on apex-minor-free graphs, 2008, submitted.
[11] F. F. Dragan, C. Yan, and Y. Xiang.
Collective additive tree spanners of homogeneously orderable graphs.
In Proceedings of the 8th Symposium Latin American Theoretical Informatics, volume 4957 of Lecture Notes in Computer Science, pages 555-567, 2008.
[12] F. Eisenbrand, F. Grandoni, T. Rothvoß, and G. Schäfer.
Approximating connected facility location problems via random facility sampling and core detouring.
In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1174-1183, 2008.
[13] E. Köhler, C. Liebchen, R. Rizzi, and G. Wünsch.
Lower bounds for strictly fundamental cycle bases in grid graphs.
Networks, 2008, to appear.
[14] F. G. König, M. E. Lübbecke, R. H. Möhring, G. Schäfer, and I. Spenke.
Practical solutions to PSPACE-complete stacking.
In Proceedings of the 15th Annual European Symposium on Algorithms, volume 4698 of Lecture Notes in Computer Science, pages 729-740, 2007.
[15] C. Liebchen, G. Wünsch, E. Köhler, A. Reich, and R. Rizzi.
Benchmarks for strictly fundamental cycle bases.
In Proceedings of the 6th Workshop on Experimental Algorithms, volume 4525 of Lecture Notes in Computer Science, pages 365-378, 2007.
[16] N. Megow, R. H. Möhring, and J. Schulz.
Turnaround scheduling in chemical manufacturing.
In Proceedings of the 8th Workshop on Models and Algorithms for Planning and Scheduling Problems, 2007.
[17] N. Megow and T. Vredeveld.
Stochastic online scheduling with precedence constraints.
Preprint 029-2007, Technische Universität Berlin, 2007.

ProFIT Project