### Page Content

### to Navigation

## List of all publications

**Megow, N. and Verschae, J.**.

**Dual techniques for scheduling on a machine with varying speed**.

In *Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013)*, Lecture Notes in Computer Science, Vol. 7965, pp. 745–756, Springer-Verlag Berlin Heidelberg, 2013.

**Correa, J., Marchetti-Spaccamela, A., Matuschke, J., Stougie, L., Svensson, O., Verdugo, V. and Verschae, J.**.

**Strong LP formulations for scheduling splittable jobs on unrelated machines**.

In *Integer Programming and Combinatorial Optimization (IPCO 2014)*, pp. 249-260, Springer, 2014.

**Bjelde, A., Fischer, F. and Klimm, M.**.

**Impartial Selection and the Power of Up to Two Choices**.

In *Proceedings of the 11th Conference on Web and Internet Economics (WINE)*, 2015.

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

**Bottleneck Routing with Elastic Demands**.

In *Proceedings of the 11th Conference on Web and Internet Economics (WINE)*, 2015.

**Schewior, K.**.

**Handling Critical Tasks Online**.

Doctoral thesis, TU Berlin, 2016.

**Gellert, T. J.**.

**Scheduling Rail-mounted Cranes**.

Doctoral thesis, TU Berlin, 2015.

**Cseh, Á.**.

**Complexity and algorithms in matching problems under preferences**.

Doctoral thesis, TU Berlin, 2016.

**Rezapour, M.**.

**Network Design with Facility Location**.

Doctoral thesis, TU Berlin, 2015.

**Bärtschi, A., Chalopin, J., Das, S., Disser, Y., Geissmann, B., Graf, D., Labourel, A. and Mihalák, M.**.

**Collaborative Delivery with Energy-Constrained Mobile Robots**.

In *Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO)*, 2017.

**Klimm, M.**.

**Competition for Resources: The Equilibrium Existence Problem in Congestion Games**.

Doctoral thesis, TU Berlin, 2012.

**Chen, L., Megow, N., Rischke, R., Stougie, L. and Verschae, J.**.

**Optimal Algorithms and a PTAS for Cost-Aware Scheduling**.

In *Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS'15)*, pp. 211–222, 2015.

**Goetzmann, K.-S.**.

**The Power of Compromise. Reference Point Methods and Approximation in Multicriteria Optimization**.

Doctoral thesis, TU Berlin, 2013.

**Chen, L., Megow, N., Rischke, R. and Stougie, L.**.

**Stochastic and Robust Scheduling in the Cloud**.

In *Proceedings of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'15)*, pp. 175–186, 2015.

**Groß, M.**.

**Approximation Algorithms for Complex Network Flow Over Time Problems**.

Doctoral thesis, TU Berlin, 2014.

**Rischke, R.**.

**Two-Stage Robust Combinatorial Optimization with Priced Scenarios**.

In *Operations Research Proceedings 2013 - Selected Papers of the International Conference on Operations Research (OR'13)*, pp. 377–382, 2014.

**Matuschke, J.**.

**Network flows and network design in theory and practice**.

Doctoral thesis, TU Berlin, 2013.

**Höhn, W.**.

**Complex Single Machine Scheduling: Theoretical and Practical Aspects of Sequencing**.

Doctoral thesis, TU Berlin, 2013.

**Marchetti-Spaccamela, A., Megow, N., Schlöter, J., Skutella, M. and Stougie, L.**.

**On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems**.

In *Proceedings of the 34th IEEE International Parallel and Distributed Processing Symposium*, 2020.

**Neumann, F., Polyakovskiy, S., Skutella, M., Stougie, L. and Wu, J.**.

**A Fully Polynomial Time Approximation Scheme for Packing While Traveling**.

In **Disser, Yann and Verykios, Vassilios S. (ed.)**, *Algorithmic Aspects of Cloud Computing – Fourth International Workshop, ALGOCLOUD 2018*, pp. 59–72, Springer, 2018.

**Klimm, M. and Weibull, J. W.**.

**Finding all minimal CURB sets**.

.
SSE/EFI Working Paper Series in Economics and Finance No 722, 20 pages, July 1, 2009, \texttturlhttp://swopec.hhs.se/hastef/abs/hastef0722.htm.

**Hansknecht, C., Klimm, M. and Skopalik, A.**.

**Approximate pure Nash equilibria in weighted congestion games**.

In **Klaus Jansen and Jos'e Rolim and Nikhil Devanur and Cristopher Moore (ed.)**, *Proceedings of the 17th Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)*, pp. 242 – 257, 2014.

**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.

**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.

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

**A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks**.

In *Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA 2010)*, Lecture Notes in Computer Science, Vol. 6534, pp. 166-177, Springer, 2011.

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

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

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

**McCormick, S. T. and Peis, B.**.

**A Primal-Dual Algorithm for Weighted Abstract Cut Packing**.

In **Günlück, Oktay and Woeginger, Gerhard (ed.)**, *Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, New York, USA*, Lecture Notes in Computer Science, Springer, Vol. 6655, pp. 324-335, 2011.

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

**Scheduling with an Orthogonal Resource Constraint**.

In *10th Workshop on Approximation and Online Algorithms (WAOA2012)*, 2012.

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

**Universal Packet Routing with Arbitrary Bandwidths and Transit Times**.

In **Günlück, Oktay and Woeginger, Gerhard (ed.)**, *Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, New York, USA*, Lecture Notes in Computer Science, Springer, Vol. 6655, pp. 362–375, 2011.

**Sagnol, G., Schmidt genannt Waldschmidt, D. and Tesch, A.**.

**The Price of Fixed Assignments in Stochastic Extensible Bin Packing**.

In *Approximation and Online Algorithms (WAOA '18)*, Lecture Notes in Computer Science, Vol. 11312, pp. 327–347, Springer, 2018.

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

**On Greedy and Submodular Matrices**.

In **Marchetti-Spaccamela and Segal, Michael (ed.)**, *Theory and Practice of Algorithms in (Computer) Systems - First International ICST Conference, TAPAS 2011, Rome, Italy*, Lecture Notes in Computer Science, Springer, Vol. 6595, pp. 116-126, 2011.

**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.

**Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C. and Sviridenko, M.**.

**Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates**.

In *Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science*, pp. 32–43, New York City, NY, 1999.

**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.

**Arkin, E. M., Bender, M. A., Fekete, S. P., Mitchell, J. S. B. and Skutella, M.**.

**The freeze-tag problem: How to wake up a swarm of robots**.

In *Proceedings of the 13th Annual ACM–SIAM Symposium on Discrete Algorithms*, pp. 568–577, San Francisco, CA, 2002.

**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.

**Mittal, S., Schulz, A. and Stiller, S.**.

**Robust appointment scheduling**.

In *Proceedings of APPROX 2014*, 2014.
to appear.

**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.

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

**Feasibility Analysis in the Sporadic DAG Task Model**.

In *ECRTS*, pp. 225-233, 2013.

**Baier, G., Erlebach, T., Hall, A., Köhler, E., Schilling, H. and Skutella, M.**.

**Length-Bounded Cuts and Flows**.

In **Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo (ed.)**, *Automata, Languages and Programming*, pp. 679–690, Springer, 2006.

**25th Euromicro Conference on Real-Time Systems, ECRTS 2013, Paris, France, July 9-12, 2013**.

Proceedings, IEEE, 2013.

**Baier, G., Köhler, E. and Skutella, M.**.

**On the k-splittable flow problem**.

In

**Möhring, Rolf H. and Raman, Rajeev (ed.)**,

*Algorithms – ESA '02*, pp. 101–113, Springer, 2002.

**Korach, E., Peis, B. and Thánh, N.**.

**Subgraph Characterization of Red/Blue-Split Graphs and König-Egerváry Graphs**.

In *Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA*, ACM Press, pp. 842-850, 2006.

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

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

In *Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science*, pp. 399–408, Berkeley, CA, 2006.

**Hochstättler, W., Nickel, R. and Peis, B.**.

**Two disjoint negative cycles in a signed graph**.

In **Faigle, Ulrich and Hurink, Johann and Schrader, Rainer and Schultz, Rüdiger (ed.)**, *Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Lambrecht, Germany*, pp. 107-111, 2006.

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

**Latency Constrained Aggregation in Sensor Networks**.

In **Azar, Yossi and Erlebach, Thomas (ed.)**, *Algorithms – ESA '06*, pp. 88–99, Springer, 2006.

**Peis, B.**.

**Structure Analysis of Some Generalizations of Matchings and Matroids Under Algorithmic Aspects**.

Doctoral thesis, Universiät zu Köln, 2006.

**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.