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 51 Technische Universität Berlin Straße des 17. Juni 136 Germany 

Phone: +49 30  314 25728 (Secretary)
Email: {moehringschaefer} 'at' math.tuberlin.de 

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.
Results.
A partial list of the problems that have been studied within the project, classified according to their respective application areas, is as follows:
 Telecommunication: frequency assignment and data transfer in wireless networks, frequency code assignment, network design (virtual networks, infrastructure networks).
 Traffic: delay management, traffic signal optimization, Stackelberg routing.
 Logistics: stacking problems, routing of automated guided vehicles, shutdown and turnaround scheduling.
The results that have been achieved within this project can be summarized as follows.
 Several algorithms for the above mentioned fundmental combinatorial optimization problems were developed and analyzed within the project. Some of these algorithms were also implemented and evaluated experimentally.
 The simulation platform TOPSURDM to simulate delays in railway systems was implemented.
 The results that we achieved within the project were published in international conference proceedings and journals; please see Publications for a list of references.
The outcomes of the project were presented to interested industry partners in February 2008; the program is available as [pdf] (in German).
Publications.
[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: TOPSURDM. 
[3] 
A. Berger, R. Hoffmann, U. Lorenz, and S. Stiller.
TOPSURDM: 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 0202007, Technische Universität Berlin, 2007. 
[5] 
V. Bonifaci, P. Korteweg, A. MarchettiSpaccamela, 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 constantcompetitive algorithm for online OVSF code assignment. In Proceedings of the 18th Annual International Symposium on Algorithms and Computation, pages 452463, 2007. Invited to special issue of Algorithmica. 
[7] 
F. Y. L. Chin and Y. Zhang.
Constantcompetitive tree node assignment, 2008, submitted. 
[8] 
F. Y. L. Chin, Y. Zhang, and H. Zhu.
A 1local 4/3competitive algorithm for multicoloring trianglefree hexagonal graphs. In Proceedings of the 13th Annual International Computing and Combinatorics Conference, pages 526536, 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 apexminorfree 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 555567, 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 ACMSIAM Symposium on Discrete Algorithms, pages 11741183, 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 PSPACEcomplete stacking. In Proceedings of the 15th Annual European Symposium on Algorithms, volume 4698 of Lecture Notes in Computer Science, pages 729740, 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 365378, 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 0292007, Technische Universität Berlin, 2007. 