### Page Content

### to Navigation

## List of all publications

## 2011

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

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

*Theory of Computing Systems*, Vol. 49, pp. 46 – 70, 2011.

**Heinz, S. and Schulz, J.**.

**Explanations for the Cumulative Constraint: An Experimental Study**.

In **Panos M.\ Pardalos and Steffen Rebennack (ed.)**, *Experimental Algorithms (SEA 2011)*, Lecture Notes in Computer Science, Vol. 6630, pp. 400–409, Springer, 2011.

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

**Challenges in Scheduling when Planning the Ship Traffic on the Kiel Canal**.

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

**Kötzing, T., Sudholt, D. and Theile, M.**.

**How Crossover Helps in Pseudo-Boolean Optimization**.

In *Genetic and Evolutionary Computation Conference (GECCO 2011)*, 2011.
(best paper award).

**von Falkenhausen, P. and Harks, T.**.

**Optimal Cost Sharing Protocols for Scheduling Games**.

In *Proceedings of the 12th ACM conference on Electronic commerce*, EC '11, pp. 285–294, New York, USA, ACM, 2011.

**Harks, T. and Klimm, M.**.

**Demand Allocation Games: Integrating Discrete and Continuous Strategy Spaces**.

In **Chen, Ning and Elkind, Edith and Koutsoupias, Elias (ed.)**, *Proceedings of the 7th International Workshop on Internet and Network Economics (WINE)*, pp. 194 – 205, 2011.

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

**Continuous and discrete flows over time**.

*Mathematical Methods of Operations Research*, 2011. To appear.

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

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

*Theory of Computing Systems*, Vol. 49, pp. 71–97, 2011.

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

**Computing Minimum Cuts by Randomized Search Heuristics**.

*Algorithmica*, Vol. 59, pp. 323–342, 2011.

**Niemeier, M., Wiese, A. and Baruah, S.**.

**Partitioned Real-Time Scheduling on Heterogeneous Shared-Memory Multiprocessors**.

In *Proceedings of the 23rd Euromicro Conference on Real-Time Systems (ECRTS 2011)*, 2011.
to appear.

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

**Universal packet routing with arbitrary bandwidths and transit times**.

In *Integer Programming and Combinatorial Optimization (IPCO 2011)*, pp. 362-375, Springer, 2011.

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

**Throughput Maximization for Periodic Packet Routing on Trees and Grids**.

In *Approximation and Online Algorithms (WAOA 2010)*, pp. 213–224, Springer, 2011.

**Skutella, K. and Skutella, M.**.

**Minimum Spanning Trees – Sometimes Greed Pays Off**.

In **Vöcking, Berthold and Alt, Helmut and Dietzfelbinger, Martin and Reischuk, Rüdiger and Scheideler, Christian and Vollmer, Heribert and Wagner, Dorothea (ed.)**, *Algorithms Unplugged*, chapter 33, pp. 325–331, Springer, 2011.

**Skutella, M. and Welz, W.**.

**Route Planning for Robot Systems**.

In **Hu, Bo and Morasch, Karl and Pickl, Stefan and Siegle, Markus (ed.)**, *Operations Research Proceedings 2010*, pp. 307–312, Springer, 2011.

**Bley, A.**.

**An Integer Programming Algorithm for Routing Optimization in IP Networks**.

*Algorithmica*, Vol. 60, pp. 21–45, 2011. Short version appeared in Proceedings of ESA 2008..

**Verschae, J. and Wiese, A.**.

**On the Configuration-LP for Scheduling on Unrelated Machines**.

In *Algorithms - ESA '11*, Springer, 2011.
to appear.

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

**Clique-based facets for the precedence constrained knapsack problem**.

*Mathematical Programming*, 2011. To appear.

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

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

*Telecommunication Systems*, 2011. To appear.

**Martens, M. and Bley, A.**.

**Securely Connected Facility Location in Metric Graphs**.

In *Operations Research Proceedings 2010: Selected Papers of the Annual International Conference of the German Operations Research Society, Munich, Germany*, pp. 288–294, Springer, 2011.

**Bley, A., D'Andreagiovanni, F. and Hanemann, A.**.

**Robustness in Communication Networks: Scenarios and Mathematical Approaches**.

In *Proceedings of the 12th ITG-Fachtagung Photonische Netze, Leipzig, Germany*, pp. 105–112, VDE Verlag, 2011.

**Arulselvan, A., Bley, A., Gollowitzer, S., Ljubic, I. and Maurer, O.**.

**MIP modeling of Incremental Connected Facility Location**.

In *Proceedings of the 5th International Network Optimization Conference (INOC 2011), Hamburg, Germany*, LNCS, pp. 490–502, Springer, 2011.

**Welz, W.**.

**Automatisches Multi-GPU Scheduling in OpenCL**.

Diploma thesis, TU Berlin, 2011. In German.

## 2010

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

**EDF-schedulability of synchronous periodic task systems is coNP-hard**.

In *Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)*, pp. 1029–1034, 2010.

**Bansal, N., Khandekar, R., Könemann, J., Nagarajan, V. and Peis, B.**.

**On Generalizations of Network Design Problems with Degree Bounds**.

In **Eisenbrand, Friedrich and Shepherd, F. Bruce (ed.)**, *Integer Programming and Combinatorial Optimization, 14th International Conference, IPCO 2010, Lausanne, Switzerland*, Lecture Notes in Computer Science, Springer, Vol. 6080, pp. 110-123, 2010.

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

**Throughput Maximization for Periodic Packet Routing on Trees and Grids**.

In **Jansen, Klaus and Solis-Oba, Roberto (ed.)**, *Approximation and Online Algorithms, 8th International Workshop, WAOA 2009*, Lecture Notes in Computer Science, Springer, Vol. 6534, pp. 213-224, 2010.

**Matuschke, J. and Peis, B.**.

**Lattices and Maximum Flow Algorithms in Planar Graphs**.

In **Thilikos, Dimitrios (ed.)**, *Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece*, Lecture Notes in Computer Science, Springer, Vol. 6410, pp. 324-335, 2010.

**Faigle, U. and Peis, B.**.

**Two-phase Greedy Algorithms for Some Classes of Combinatorial Linear Programs**.

*ACM Transactions on Algorithms*, Vol. 6(4), 2010. An extended abstract appeared in SODA 2008-proceedings.

**Faigle, U., Kern, W. and Peis, B.**.

**A Ranking Model for Cooperative Games, Convexity and the Greedy Algorithm**.

*Math. Programming, (doi:10.1007/s10107-010-0406-2)*, Vol. A, 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*, Lecture Notes in Computer Science, Springer, Vol. 5893, pp. 217–228, 2010.

**Baier, G., Erlebach, T., Hall, A., Köhler, E., Kolman, P., Pangr\?ac, O., Schilling, H. and Skutella, M.**.

**Length-Bounded Cuts and Flows**.

*ACM Transactions on Algorithms*, Vol. 7, pp. 4, 2010.

**Berthold, T., Heinz, S., Lübbecke, M. E., Möhring, R. H. and Schulz, J.**.

**A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling**.

In **Andrea Lodi and Michela Milano and Paolo Toth (ed.)**, *Proceedings of the 7th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems*, Lecture Notes in Computer Science, Vol. 6140, pp. 313-317, Springer, 2010.

**Coughlan, E. T., Lübbecke, M. E. and Schulz, J.**.

**A Branch-and-Price Algorithm for Multi-mode Resource Leveling**.

In **Paola Festa (ed.)**, *Proceedings of the 9th International Symposium on Experimental Algorithms (SEA2010)*, Lecture Notes in Computer Science, Vol. 6049, pp. 226-238, Springer, 2010.

**Doerr, B., Johannsen, D., Kötzing, T., Neumann, F. and Theile, M.**.

**More Effective Crossover Operators for the All-Pairs Shortest Path Problem**.

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

**Dressler, D., Groß, M., Kappmeier, J.-P., Kelter, T., Kulbatzki, J., Plümpe, D., Schlechter, G., Schmidt, M., Skutella, M. and Temme, S.**.

**On the use of network flow techniques for assigning evacuees to exits**.

In **Hoogendoorn, S.P. and Pel, A.J. and Taylor, M.A.P. and Mahmassani, H. (ed.)**, *Proceedings of the International Conference on Evacuation Modeling and Management*, Procedia Engineering, Vol. 3, pp. 205–215, Elsevier Ltd, 2010.

**Eisenbrand, F., Hähnle, N., Niemeier, M., Skutella, M., Verschae, J. and Wiese, A.**.

**Scheduling periodic tasks in a hard real-time environment**.

In **Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G. (ed.)**, *Automata, Languages and Programming (ICALP 2010)*, pp. 299–311, Springer, 2010.

**Eisenbrand, F., Kesavan, K., Mattikalli, R. S., Niemeier, M., Nordsieck, A. W., Skutella, M., Verschae, J. and Wiese, A.**.

**Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods**.

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

**Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M. and Stougie, L.**.

**Universal sequencing on a single machine**.

In **Eisenbrand, Friedrich and Shepherd, Bruce (ed.)**, *Integer Programming and Combinatorial Optimization*, pp. 230–243, Springer, 2010.

**Büsing, C.**.

**Recoverable Robustness in Combinatorial Optimization**.

Doctoral thesis, TU Berlin, 2010.

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

**Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width**.

In *Approximation and Online Algorithms: 7th International Workshop, WAOA 2009*, Lecture Notes in Computer Science, Vol. 5893, pp. 170-181, Springer, 2010.

**Disser, Y., Mihalák, M. and Widmayer, P.**.

**Reconstructing a simple polygon from its angles**.

In *Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)*, pp. 13–24, 2010.

**Chalopin, J., Das, S., Disser, Y., Mihalák, M. and Widmayer, P.**.

**How Simple Robots Benefit from Looking Back**.

In *Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC)*, pp. 229–239, 2010.

**Baruah, S., Bonifaci, V., D'Angelo, G., Li, H., Marchetti-Spaccamela, A., Megow, N. and Stougie, L.**.

**Scheduling real-time mixed-criticality jobs**.

In *Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010)*, Lecture Notes in Computer Science, Vol. 6281, pp. 90–101, Springer, 2010.

**Bonifaci, V., Chan, H.-L., Marchetti-Spaccamela, A. and Megow, N.**.

**Algorithms and Complexity for Periodic Real-Time Scheduling**.

In *Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)*, pp. 1350–1359, 2010.

**Brenner, J.**.

**Truthful Mechanism Design for Cooperative Cost Sharing and Congestion Games**.

Doctoral thesis, TU Berlin, 2010.

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

**Kreuzzahlrätsel**.

*Mitteilungen der DMV*, Vol. 18, pp. 118, 2010.

**Galli, L. and Stiller, S.**.

**Strong Formulations for the Multi-module PESP and a Quadratic Algorithm for Graphical Diophantine Equation Systems**.

In **Mark de Berg and Ulrich Meyer (ed.)**, *Algorithms - ESA 2010 (1), 18th Annual European Symposium on Algorithms*, Lecture Notes in Computer Science, Vol. 6346, pp. 338-349, Springer, 2010.

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

**Improved multiprocessor global schedulability analysis**.

*Real-Time Systems*, Vol. 46, pp. 3-24, 2010.

**Liebchen, C., Schachtebeck, M., Schöbel, A., Stiller, S. and Prigge, A.**.

**Computing delay resistant railway timetables**.

*Computers & OR*, Vol. 37, pp. 857-868, 2010.

**Harks, T., Hoefer, M., Klimm, M. and Skopalik, A.**.

**Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games**.

In **M. de Berg and U. Meyer (ed.)**, *Proceedings of the 18th European Symposium on Algorithms (ESA)*, Lecture Notes in Computer Science, Vol. 6347, pp. 29 – 38, 2010.

**Harks, T. and Klimm, M.**.

**On the Existence of Pure Nash Equilibria in Weighted Congestion Games**.

In **S. Abramsky and C. Gavoille and C. Kirchner and F. Meyer auf der Heide and P. Spirakis (ed.)**, *Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP)*, Lecture Notes in Computer Science, Vol. 6198, pp. 79 – 89, Springer, 2010.