### Page Content

### to Navigation

## List of all publications

## 2010

**Harks, T., Matuschke, J. and König, F. G.**.

**Approximation Algorithms for Capacitated Location Routing**.

Preprint 010-2010, Technische Universität Berlin, 2010.

**Günther, E., Lübbecke, M. E. and Möhring, R. H.**.

**Ship Traﬃc Optimization for the Kiel Canal**.

In *Proceedings of the Seventh Triennial Symposium on Transportation Analysis (TRISTAN 2010)*, 2010.

**Jansen, T. and Theile, M.**.

**Stability in the Self-Organized Evolution of Networks**.

*Algorithmica*, Vol. 57, pp. 147-169, 2010.

**Kanj, I., Wiese, A. and Zhang, F.**.

**Local Algorithms for Edge Colorings in UDGs**.

In **Paul, Christophe and Habib, Michel (ed.)**, *Graph-Theoretic Concepts in Computer Science (WG 2010)*, pp. 202-213, Springer, 2010.

**Neumann, F. and Theile, M.**.

**How Crossover Speeds Up Evolutionary Algorithms for the Multi-criteria All-Pairs-Shortest-Path Problem**.

In *Proceedings of the Parallel Problem Solving from Nature (PPSN XI)*, pp. 667-676, 2010.

**Peis, B., Skutella, M. and Wiese, A.**.

**Packet Routing: Complexity and Algorithms**.

In **Bampis, Evripidis and Jansen, Klaus (ed.)**, *Approximation and Online Algorithms, 7th International Workshop, WAOA 2009, Copenhagen, Denmark, September 2009. Revised Papers*, pp. 217–228, Springer, 2010.

**Skutella, M., Peis, B. and Wiese, A.**.

**Packet Routing on the Grid**.

In **Lopez-Ortiz, Alejandro (ed.)**, *Theoretical Informatics, 9th Latin American Symposium, LATIn 2010, Oaxaca, Mexico*, Lecture Notes in Computer Science, Springer, Vol. 6034, pp. 120-130, 2010.

**Peis, B., Stiller, S. and Wiese, A.**.

**Policies for Periodic Packet Routing**.

In **Cheong, Otfried and Chwa Kyung-Yong and Park, Kunsoo (ed.)**, *Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea*, Lecture Notes in Computer Science, Springer, Vol. 6507, pp. 266–278, 2010.

**Reichel, J. and Skutella, M.**.

**Evolutionary Algorithms and Matroid Optimization Problems**.

*Algorithmica*, Vol. 57, pp. 187–206, 2010.

**Schmidt, M. and Skutella, M.**.

**Earliest Arrival Flows in Networks with Multiple Sinks**.

*Electronic Notes in Discrete Mathematics*, Vol. 36, pp. 607–614, 2010. ISCO 2010 – International Symposium on Combinatorial Optimization.

**Skutella, M. and Verschae, J.**.

**A Robust PTAS for Machine Covering and Packing**.

In **de Berg, Mark and Meyer, Ulrich (ed.)**, *Algorithms – ESA '10*, pp. 36–47, Springer, 2010.

**Skutella, M. and Weber, A.**.

**On the dominant of the s-t-cut polytope**.

*Mathematical Programming*, Vol. 124, pp. 441–454, 2010.

**Bley, A., Fortz, B., Gourdin, E., Holmberg, K., Klopfenstein, O., Pióro, M., Tomaszewski, A. and Ümit, H.**.

**Optimization of OSPF Routing in IP Networks**.

In **A.M.C.A. Koster and X. Muñoz (ed.)**, *Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless and Ad Hoc Networks*, chapter 8, pp. 199–240, Springer, 2010.

**Bley, A., Boland, N., Fricke, C. and Froyland, G.**.

**A strengthened formulation and cutting planes for the open pit mine production scheduling problem**.

*Computers and Operations Research*, Vol. 37, pp. 1641–1647, 2010.

**Stiller, S. and Wiese, A.**.

**Increasing speed scheduling and Flow scheduling**.

In *Algorithms and Computation (ISAAC 2010)*, pp. 279–290, Springer, 2010.

**Menne, U., Wessäly, R., Martens, M. and Bley, A.**.

**Integrated optimization of aggregation and core for varying NGN architectures**.

In **M. Pióro and K. Szczypiorski and J. Rak and O. Gonzalez-Soto (ed.)**, *Proceedings of the 14th International Telecommunications Network Strategy and Planning Symposium (NETWORKS 2010), Warsaw, Poland*, IEEE Xplore, pp. 228–233, IEEE, 2010.
Extended version submitted to Telecommunication Systems.

**Bley, A. and Neto, J.**.

**Approximability of 3- and 4-hop bounded disjoint paths problems**.

In *Integer Programming and Combinatorial Optimization: Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization (IPCO 2010), Lausanne, Switzerland*, LNCS, pp. 205–218, Springer, 2010.

**Welz, W.**.

**Route Planning for Robot Systems**.

Diploma thesis, TU Berlin, 2010.

## 2009

**Theile, M.**.

**An article about my work (in German) which appeared in Technology Review**.

, 2009.

**Davis, R., Rothvoß, T., Baruah, S. and Burns, A.**.

**Exact quantification of the sub-optimality of uniprocessor fixed-priority preemptive scheduling**.

*Kluwer Academic Publishers*, Vol. 43, pp. 211–258, 2009.

**Eisenbrand, F. and Rothvoß, T.**.

**New Hardness Results for Diophantine Approximation**.

In *Proceedings of the 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009)*, Lecture Notes in Computer Science, Vol. 5687, pp. 98–110, Springer, 2009.

**Karrenbauer, A. and Rothvoß, T.**.

**An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling**.

In *Proceedings of the 17th Annual European Symposium on Algorithms (ESA 2009)*, Lecture Notes in Computer Science, Vol. 5757, pp. 432–443, Springer, 2009.

**Baumann, N. and Skutella, M.**.

**Solving Evacuation Problems Efficiently: Earliest Arrival Flows with Multiple Sources**.

*Mathematics of Operations Research*, Vol. 34, pp. 499–512, 2009.

**Becchetti, L., Korteweg, P., Marchetti-Spaccamela, A., Skutella, M., Stougie, L. and Vitaletti, A.**.

**Latency Constrained Aggregation in Sensor Networks**.

*ACM Transactions on Algorithms*, Vol. 6, pp. 13:1–13:20, 2009.

**Nasrabadi, E.**.

**Dynamic Flows in Time-varying Networks**.

Doctoral thesis, Amirkabir University of Technology / TU Berlin, 2009.

**Correa, J. R., Skutella, M. and Verschae, J.**.

**The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders**.

In **Dinur, Irit and Jansen, Klaus and Naor, Joseph and Rolim, José D. P. (ed.)**, *Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009*, Lecture Notes in Computer Science, Vol. 5687, pp. 84–97, Springer, 2009.

**Doerr, B., Eremeev, A. V., Horoba, C., Neumann, F. and Theile, M.**.

**Evolutionary algorithms and dynamic programming**.

In *Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)*, pp. 771-778, 2009.

**Doerr, B. and Theile, M.**.

**Improved analysis methods for crossover-based algorithms**.

In *Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)*, pp. 247-254, 2009.

**Eisenbrand, F., Karrenbauer, A., Skutella, M. and Xu, C.**.

**Multiline Addressing by Network Flow**.

*Algorithmica*, Vol. 53, pp. 583–596, 2009.

**Günther, E., König, F. G. and Megow, N.**.

**The Bin Scheduling Problem**.

In *Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2009)*, 2009.

**Bilò, D., Disser, Y., Mihalák, M., Suri, S., Vicari, E. and Widmayer, P.**.

**Reconstructing Visibility Graphs with Simple Robots**.

In *Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO)*, pp. 87–99, 2009.

**Disser, Y., Bilò, D., Mihalák, M., Suri, S., Vicari, E. and Widmayer, P.**.

**On the Limitations of Combinatorial Visibilities**.

In *Proceedings of the 25th European Workshop on Computational Geometry (EuroCG)*, pp. 207–210, 2009.

**Groß, M.**.

**Flows over Time with Commodity-Dependent Transit Times**.

Diploma thesis, TU Dortmund, 2009.

**Groß, M., Kappmeier, J.-P., Plümpe, D. and Schmidt, M.**.

**Kreuzzahlrätsel**.

*Mitteilungen der DMV*, Vol. 17, pp. 96, 2009.

**Stiller, S.**.

**Extending Concepts of Reliability: Network Creation Games, Real-time Scheduling, and Robust Optimization**.

Doctoral thesis, TU Berlin, 2009.

**Groß, M., Plümpe, D. and Schmidt, M.**.

**Kreuzzahlrätsel – Sudokus waren gestern**.

*Informatik-Spektrum*, Vol. 32, pp. 538-545, 2009.

**Megow, N.**.

**Keller oder Dach zuerst**.

In **K. Biermann and M. Götschel and B. Lutz-Westphal (ed.)**, *Besser als Mathe: Moderne angewandte Mathematik aus dem Matheon zum Mitmachen*, pp. 111–115, Vieweg+Teubner, 2009.

**Correa, J. R., Megow, N., Raman, R. and Suchan, K.**.

**Cardinality Constrained Graph Partitioning into Cliques with Submodular Costs**.

In *8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009)*, 2009.

**Liebchen, C., Lübbecke, M. E., Möhring, R. H. and Stiller, S.**.

**The Concept of Recoverable Robustness, Linear Programming Recovery, and Railway Applications**.

In **Ravindra K. Ahuja and Rolf H. Möhring and Christos D. Zaroliagis (ed.)**, *Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems} publisher = {Springer*, pp. 1-27, 2009.

**Baruah, S. K., Bonifaci, V., Marchetti-Spaccamela, A. and Stiller, S.**.

**Implementation of a Speedup-Optimal Global EDF Schedulability Test**.

In *ECRTS*, pp. 259-268, IEEE Computer Society, 2009.

**Harks, T., Klimm, M. and Möhring, R. H.**.

**Strong Nash Equilibria in Games with the Lexicographical Improvement Property**.

In **S. Leonardi (ed.)**, *Proceedings of the 5th International Workshop on Internet and Network Economics (WINE)*, Lecture Notes in Computer Science, Vol. 5929, pp. 463 – 470, Springer, 2009.

**Harks, T., Klimm, M. and Möhring, R. H.**.

**Characterizing the Existence of Potential Functions in Weighted Congestion Games**.

In **M. Mavronicolas and V. G. Papadopoulou (ed.)**, *Proceedings of the 2nd International Symposium on Algorithmic Game Theory (SAGT)*, Lecture Notes in Computer Science, Vol. 5814, pp. 97 – 108, Springer, 2009.

**Köhler, E., Möhring, R. H. and Skutella, M.**.

**Traffic networks and flows over time**.

In **Lerner, Jürgen and Wagner, Dorothea and Zweig, Katharina A. (ed.)**, *Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation*, pp. 166–196, Springer, 2009.

**König, F. G.**.

**Sorting with Objectives - Graph Theoretic Concepts in Industrial Optimization**.

Doctoral thesis, Technische Universität Berlin, 2009. Supervisors: Rolf H. Möhring and Peter Widmayer.

**Kappmeier, J.-P.**.

**Berechnung maximaler Flüsse unter Vermeidung von Residualnetzwerken**.

Diploma thesis, TU Dortmund, 2009. In German.

**Koch, R., Peis, B., Skutella, M. and Wiese, A.**.

**Real-Time Message Routing and Scheduling**.

In **Jansen, Klaus and Naor, Joseph and Rolim, Jose (ed.)**, *Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX-RANDOM 2009, Berkeley, USA*, Lecture Notes in Computer Science, Springer, Vol. 5687, pp. 217–230, 2009.

**Koch, R. and Skutella, M.**.

**Nash Equilibria and the Price of Anarchy for Flows Over Time**.

In **Mavronicolas, Marios and Papadopoulou, Vicky G. (ed.)**, *Proceedings of the 2nd International Symposium on Algorithmic Game Theory*, pp. 323–334, Springer, 2009.

**Martens, M. and Skutella, M.**.

**A Network Flow Problem with Unit Path Capacities and Related Packing and Covering Problems**.

*Journal of Combinatorial Optimization*, Vol. 18, pp. 272–293, 2009.

**Reichel, J. and Skutella, M.**.

**On the size of weights in randomized search heuristics**.

In *Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms*, pp. 21–28, New York, ACM, 2009.

**Salazar, F. and Skutella, M.**.

**Single-source k-splittable min-cost flows**.

*Operations Research Letters*, Vol. 37, pp. 71–74, 2009.