### Page Content

## List of all publications

## 2009

**Sanders, P., Sivadasan, N. and Skutella, M.**.

**Online Scheduling with Bounded Migration**.

*Mathematics of Operations Research*, Vol. 34, pp. 481–498, 2009.

**Skutella, M.**.

**An Introduction to Network Flows Over Time**.

In **Cook, William and Lovász, László and Vygen, Jens (ed.)**, *Research Trends in Combinatorial Optimization*, pp. 451–482, Springer, 2009.

**Bley, A.**.

**Approximability of Unsplittable Shortest Path Routing Problems**.

*Networks*, Vol. 54, pp. 23–46, 2009. Short version appeared in Proceedings of IPCO 2005..

**Bley, A.**.

**On the Hardness of Finding Small Shortest Path Routing Conflicts**.

In *Proceedings of the 4th International Network Optimization Conference (INOC 2009), Pisa, Italy*, 2009.

**Bley, A.**.

**Logarithmic inapproximability results for the minimum shortest path routing conflict problem**.

Preprint 025-2009, Institute of Mathematics, TU Berlin, 2009. Submitted to Networks.

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

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

In **C. Stein and M. Uetz and T. Vredeveld (ed.)**, *Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2009), Rolduc, The Netherlands*, pp. 259–261, 2009.

**Bley, A., Gleixner, A., Koch, T. and Vigerske, S.**.

**Comparing MIQCP solvers on open pit mine production scheduling problems with stockpiling constraints**.

Preprint 09-32, ZIB, 2009. Short version submitted to Modeling, Simulation and Optimization of Complex Processes: Proceedings of the 4th International Conference on High Performance Scientific Computing (HPSC 2009), Hanoi, Vietnam..

**Theile, M.**.

**Exact Solutions to the Traveling Salesperson Problem by a Population-Based Evolutionary Algorithm**.

In *Proceedings of the Proceedings of Evolutionary Computation in Combinatorial Optimisation (EvoCOP)*, pp. 145-155, 2009.

**Bampis, Evripidis and Skutella, Martin (ed.)**,

**Approximation and Online Algorithms, 6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers**.

Proceedings, Lecture Notes in Computer Science, Vol. 5426, Springer, 2009.

## 2008

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

**Static-priority Real-time Scheduling: Response Time Computation is NP-hard**.

In *IEEE Real-Time Systems Symposium (RTSS)*, 2008.

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

**A Hierarchical Model for Cooperative Games**.

In **Monien, Burkhard and Schroeder, Ulf-Peter (ed.)**, *Algorithmic Game Theory, First International Symposium, SAGT 2008, Paderborn, Germany*, Lecture Notes in Computer Science, Springer, Vol. 4997, pp. 230-241, 2008.

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

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

In **Teng, Shang-Hua (ed.)**, *Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA*, SIAM, pp. 161-166, 2008.
A full version appeared in TALG 2010.

**Lätsch, M. and Peis, B.**.

**On a Relation Between the Domination Number and a Strongly Connected Bidirection of an Undirected Graph**.

*Discrete Applied Mathematics*, Vol. 156, pp. 3194-3202, 2008.

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

**Note on Pseudolattices, Lattices and Submodular Linear Programs**.

*Discrete Optimization*, Vol. 5, pp. 489-500, 2008.

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

**Note on maximal split-stable subgraphs**.

*Discrete Applied Mathematics*, Vol. 156, pp. 3194-3202, 2008.

**Oellrich, M.**.

**Minimum Cost Disjoint Paths under Arc Dependences - Algorithms for Practice**.

Doctoral thesis, TU Berlin, 2008.

**Bhattacharya, B., Burmester, B., Hu, Y., Kranakis, E., Shi, Q. and Wiese, A.**.

**Optimal Movement of Mobile Sensors for Barrier Coverage of a Planar Region**.

In **Yang, Boting and Du, Ding-Zhu and Wang, Cao (ed.)**, *Combinatorial Optimization and Applications (COCOA 2008)*, pp. 103-115, Springer, 2008.

**Biermann, D., Surmann, T., Sacharow, A., Skutella, M. and Theile, M.**.

**Automated analysis of the form error caused by springback in metal sheet forming**.

In **Bouzakis, Konstantinos-Dionysios (ed.)**, *Proceedings of the 3rd International Conference on Manufacturing Engineering, 1.-3. October 2008, Kallithea of Chalkidiki, Greece*, pp. 737–746, 2008.

**Caragiannis, I., Kaklamanis, C., Kranakis, E., Krizanc, D. and Wiese, A.**.

**Communication in wireless networks with directional antennas**.

In *Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures (SPAA 2008)*, pp. 344–351, ACM, 2008.

**Stenzel, B.**.

**Online Disjoint Vehicle Routing with Application to AGV Routing**.

Doctoral thesis, TU Berlin, 2008.

**Wünsch, G.**.

**Coordination of Traffic Signals in Networks and Related Graph Theoretical Problems on Spanning Trees**.

Doctoral thesis, TU Berlin, 2008.

**Wilms, J., Disser, Y., Alber, G. and Percival, I. C.**.

**Local Realism, Detection Efficiencies, and Probability Polytopes**.

*Physical Review A*, Vol. 73, pp. 032116(8), 2008.

**Disser, Y., Müller-Hannemann, M. and Schnee, M.**.

**Multi-criteria Shortest Paths in Time-Dependent Train Networks**.

In *Proceedings of the 7th International Workshop on Experimental Algorithms (WEA)*, pp. 347 – 361, 2008.

**Froyland, G., Koch, T., Megow, N., Duane, E. and Wren, H.**.

**Optimizing the Landside Operation of a Container Terminal**.

*OR Spectrum*, Vol. 30, pp. 53-75, 2008.

**Grandoni, F., Kaibel, V., Oriolo, G. and Skutella, M.**.

**A short proof of the VPN tree routing conjecture on ring networks**.

*Operations Research Letters*, Vol. 36, pp. 361–365, 2008.

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

**A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling**.

In **Dan Halperin and Kurt Mehlhorn (ed.)**, *Algorithms - ESA 2008, 16th Annual European Symposium on Algortihms*, Lecture Notes in Computer Science, Vol. 5193, pp. 210-221, Springer, 2008.

**Berger, A., Hoffmann, R., Lorenz, U. and Stiller, S.**.

**TOPSU–RDM: a simulation platform for online railway delay management**.

In **Sándor Molnár and John R. Heath and Olivier Dalle and Gabriel A. Wainer (ed.)**, *Proceedings of the 1st International Conference on Simulation Tools and Techniques for Communications, Networks and Systems & Workshops, SimuTools 2008*, pp. 20, ICST, 2008.

**Baumann, N. and Stiller, S.**.

**The Price of Anarchy of a Network Creation Game with Exponential Payoff**.

In **Burkhard Monien and Ulf-Peter Schroeder (ed.)**, *Algorithmic Game Theory, First International Symposium, SAGT 2008, Paderborn, Germany, April 30-May 2, 2008. Proceedings*, Lecture Notes in Computer Science, Vol. 4997, pp. 218-229, Springer, 2008.

**König, F. G. and Lübbecke, M. E.**.

**Sorting with Complete Networks of Stacks**.

In *Algorithms and Computation: 19th International Symposium, ISAAC 2008*, Lecture Notes in Computer Science, Vol. 5369, pp. 896-907, Springer, 2008.

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

**Maximum k-Splittable s,t-Flows**.

*Theory of Computing Systems*, Vol. 43, pp. 56–66, 2008.

**Kranakis, E. and Wiese, A.**.

**Impact of Locality on Location Aware Unit Disk Graphs**.

*Proceedings of the 2nd International Workshop on Localized Algorithms and Protocols for Wireless Sensor Networks (LOCALGOS 2008)*, Vol. 1, pp. 2–29, 2008.

**Kranakis, E. and Wiese, A.**.

**Local PTAS for Independent Set and Vertex Cover in Location Aware UDGs**.

In *Distributed Computing in Sensor Systems (DCOSS 2008)*, pp. 415–431, Springer, 2008.

**Kranakis, E. and Wiese, A.**.

**Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs**.

In *Graph-Theoretic Concepts in Computer Science (WG 2008)*, pp. 372-383, Springer, 2008.
10.1007/978-3-540-92248-3_33.

**Kranakis, E. and Wiese, A.**.

**Local PTAS for Dominating and Connected Dominating Set in Location Aware UDGs**.

In *Approximation and Online Algorithms (WAOA 2008)*, pp. 227-240, Springer, 2008.

**Kranakis, E. and Wiese, A.**.

**Local Maximal Matching and Local 2-Approximation for Vertex Cover in UDGs**.

In *Ad-hoc, Mobile and Wireless Networks (ADHOC-NOW 2008)*, pp. 1–14, Springer, 2008.

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

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

In **Yang, Boting and Du, Ding-Zhu and Wang, Cao An (ed.)**, *Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications*, Lecture Notes in Computer Science, Vol. 5165, pp. 180–189, Springer, 2008.

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

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

In *Proceedings of the 10th Genetic and Evolutionary Computation Conference*, pp. 779–787, 2008.

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

**Minimal aufspannende Bäume – Wenn das Naheliegende das Beste ist...**.

In **Vöcking, Berthold and Alt, Helmut and Dietzfelbinger, Martin and Reischuk, Karl Rüdiger and Scheideler, Christian and Vollmer, Heribert and Wagner, Dorothea (ed.)**, *Taschenbuch der Algorithmen*, pp. 353–360, Springer, 2008.
In German.

**Bley, A.**.

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

In *Algorithms – ESA 2008: Proceedings of the 16th Annual European Symposium on Algorithms, Karlsruhe, Germany*, LNCS, pp. 198–209, Springer, 2008.

**Bley, A., Koch, T. and Niu, L.**.

**Experiments with nonlinear extensions to SCIP**.

Preprint 08-28, ZIB, 2008.

**Bley, A., Menne, U., Klähne, R., Raack, C. and Wessäly, R.**.

**Multi-layer network design – A model-based optimization approach**.

In *Proceedings of the 5th Polish-German Teletraffic Symposium 2008*, pp. 107–116, Berlin, Germany, 2008.

**Kaklamanis, Christos and Skutella, Martin (ed.)**,

**Approximation and Online Algorithms, 5th International Workshop, WAOA 2007, Eilat, Israel, October 11-12, 2007. Revised Papers**.

Proceedings, Lecture Notes in Computer Science, Vol. 4927, Springer, 2008.

## 2007

**Eisenbrand, F., Grandoni, F., Oriolo, G. and Skutella, M.**.

**New Approaches for Virtual Private Network Design**.

*SIAM Journal on Computing*, Vol. 37, pp. 706–721, 2007.

**Fleischer, L. and Skutella, M.**.

**Quickest Flows Over Time**.

*SIAM Journal on Computing*, Vol. 36, pp. 1600–1630, 2007.

**Hall, A., Hippler, S. and Skutella, M.**.

**Multicommodity Flows Over Time: Efficient Algorithms and Complexity**.

*Theoretical Computer Science*, Vol. 379, pp. 387–404, 2007.

**Hall, A., Langkau, K. and Skutella, M.**.

**An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times**.

*Algorithmica*, Vol. 47, pp. 299–321, 2007.

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

**Stability in the self-organized evolution of networks**.

In *Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)*, pp. 931-938, 2007.

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

**Traffic Optimization under Route Constraints with Lagrangian Relaxation and Cutting Plane Methods**.

In *Operations Research Proceedings 2006*, pp. 53-59, Springer, 2007.

**König, F. G., Lübbecke, M. E., Möhring, R. H., Schäfer, G. and Spenke, I.**.

**Solutions to Real-World Instances of PSPACE-Complete Stacking**.

In *Algorithms - ESA 2007: 15th Annual European Symposium*, Lecture Notes in Computer Science, Vol. 4698, pp. 729-740, Springer, 2007.

**Megow, N., Möhring, R. H. and Schulz, J.**.

**Turnaround Scheduling in Chemical Manufacturing**.

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