### Page Content

### to Navigation

## List of all publications

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

## 1992

**Gustedt, J.**.

**Algorithmic Aspects of Ordered Structures**.

Doctoral thesis, TU Berlin, 1992.

**Felsner, S.**.

**Interval Orders: Combinatorial Structure and Algorithms**.

Doctoral thesis, TU Berlin, 1992.

## 1993

**Müller, R.**.

**Bounds for linear VLSI layout problems**.

Doctoral thesis, TU Berlin, 1993.

## 1994

**Weihe, C.**.

**Flow and Routing Problems in Planar Graphs**.

Doctoral thesis, TU Berlin, 1994.

**Ripphausen-Lipa, H.**.

**Efficient Algorithms for Disjoint Steiner Trees Packing Problems in Planar Graphs**.

Doctoral thesis, TU Berlin, 1994.

## 1995

**Skutella, M.**.

**Konjugiertenklassen und Harish-Chandra-Serien symplektischer und orthogonaler Gruppen**.

Diploma thesis, RWTH Aachen, 1995. In German.

## 1996

**Schäffter, M.**.

**Scheduling Jobs with Communication Delays: Complexity Results and Approximation Algorithms**.

Doctoral thesis, TU Berlin, 1996.

**Parra, A.**.

**Structural and Algorithmic Aspects of Chordal Graph Embeddings**.

Doctoral thesis, TU Berlin, 1996.

**Schulz, A. S.**.

**Polytopes and Scheduling**.

Doctoral thesis, TU Berlin, 1996.

## 1997

**Müller-Hannemann**.

**Quadrilateral Mesh Generation in Computer-Aided Design**.

Doctoral thesis, TU Berlin, 1997.

**Malesinska, E.**.

**Graph-Theoretical Models for Frequency Assignment Problems**.

Doctoral thesis, TU Berlin, 1997.

**Bley, A.**.

**Node-Disjoint Length-Restricted Paths**.

Diploma thesis, TU Berlin, 1997.

**Schulz, A. S. and Skutella, M.**.

**Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria**.

In **Burkard, Rainer and Woeginger, Gerhard J. (ed.)**, *Algorithms – ESA '97*, pp. 416–429, Springer, 1997.

**Schulz, A. S. and Skutella, M.**.

**Random-based scheduling: New approximations and LP lower bounds**.

In **Rolim, José D. P. (ed.)**, *Randomization and Approximation Techniques in Computer Science*, pp. 119–133, Springer, 1997.

**Skutella, M.**.

**Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem**.

In *Proceedings of the 8th Annual ACM–SIAM Symposium on Discrete Algorithms*, pp. 501–508, New Orleans, LA, 1997.

## 1998

**Gröpl, C. and Skutella, M.**.

**Parallel Repetition of MIP(2,1) Systems**.

In **Mayr, Ernst W. and Prömel, Hans Jürgen and Steger, Angelika (ed.)**, *Lectures on Proof Verification and Approximation Algorithms*, pp. 161–177, Springer, 1998.

**Bley, A., Grötschel, M. and Wessäly, R.**.

**Design of Broadband Virtual Private Networks: Model and Heuristics for the B-WiN**.

In **N. Dean and D.F. Hsu and R. Ravi (ed.)**, *Robust Communication Networks: Interconnection and Survivability*, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 53, pp. 1–16, AMS, 1998.

**Skutella, M.**.

**Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem**.

*Mathematics of Operations Research*, Vol. 23, pp. 909–929, 1998.

**Skutella, M.**.

**Semidefinite Relaxations for Parallel Machine Scheduling**.

In *Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science*, pp. 472–481, Palo Alto, CA, 1998.

**Skutella, M.**.

**Approximation and randomization in scheduling**.

Doctoral thesis, Technische Universität Berlin, Germany, 1998.

## 1999

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

**Köhler, E.**.

**Graphs without Asteroidal Triples**.

Doctoral thesis, TU Berlin, 1999.

**Hartmann, S.**.

**Layout Problems in VLSI Circuit Design**.

Doctoral thesis, TU Berlin, 1999.

**Skutella, M.**.

**Convex Quadratic Programming Relaxations for Network Scheduling Problems**.

In **Ne\vset\vril, Jaroslav (ed.)**, *Algorithms – ESA '99*, pp. 127–138, Springer, 1999.

**Skutella, M. and Woeginger, G. J.**.

**A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines**.

In *Proceedings of the 31st Annual ACM Symposium on Theory of Computing*, pp. 400–407, Atlanta, GA, 1999.

## 2000

**Goemans, M. X. and Skutella, M.**.

**Cooperative facility location games**.

In *Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms*, pp. 76–85, San Francisco, CA, 2000.

**Hoogeveen, H., Skutella, M. and Woeginger, G. J.**.

**Preemptive scheduling with rejection**.

In **Mike Paterson (ed.)**, *Algorithms – ESA '00*, pp. 268–277, Springer, 2000.

**Möhring, R. H., Skutella, M. and Stork, F.**.

**Forcing Relations for AND/OR Precedence Constraints**.

In *Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms*, pp. 235–236, San Francisco, CA, 2000.

**Bienstock, D. and Bley, A.**.

**Capacitated Network Design with Multicast Commodities**.

In *Proceedings of the 8th International Conference on Telecommunication Systems (ICTSM 2000), Modeling and Analysis, Nashville, USA*, 2000.

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

**Optimierung des G-WiN**.

*DFN-Mitteilungen*, Vol. 54, pp. 13–15, 2000.

**Skutella, M.**.

**Approximating the single source unsplittable min-cost flow problem**.

In *Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science*, pp. 136–145, Redondo Beach, CA, 2000.

**Skutella, M. and Woeginger, G. J.**.

**A PTAS for minimizing the total weighted completion time on identical parallel machines**.

*Mathematics of Operations Research*, Vol. 25, pp. 63–75, 2000.

## 2001

**Uetz, M.**.

**Algorithms for Deterministic and Stochastic Scheduling**.

Doctoral thesis, TU Berlin, 2001.

**Naatz, M.**.

**Acyclic Orientations of Mixed Graphs**.

Doctoral thesis, TU Berlin, 2001.

**Stork, F.**.

**Stochastic Resource-Constrained Project Scheduling**.

Doctoral thesis, TU Berlin, 2001.

**Skutella, M.**.

**Convex quadratic and semidefinite programming relaxations in scheduling**.

*Journal of the ACM*, Vol. 48, pp. 206–242, 2001.

**Skutella, M. and Uetz, M.**.

**Scheduling precedence-constrained jobs with stochastic processing times on parallel machines**.

In *Proceedings of the 12th Annual ACM–SIAM Symposium on Discrete Algorithms*, pp. 589–590, Washington, DC, 2001.

## 2002

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

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

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

**The quickest multicommodity flow problem**.

In **Cook, William J. and Schulz, Andreas S. (ed.)**, *Integer Programming and Combinatorial Optimization*, pp. 36–53, Springer, 2002.

**Goemans, M. X., Queyranne, M., Schulz, A. S., Skutella, M. and Wang, Y.**.

**Single machine scheduling with release dates**.

*SIAM Journal on Discrete Mathematics*, Vol. 15, pp. 165–192, 2002.

**Köhler, E., Langkau, K. and Skutella, M.**.

**Time-Expanded Graphs for Flow-Dependent Transit Times**.

In **Möhring, Rolf H. and Raman, Rajeev (ed.)**, *Algorithms – ESA '02*, pp. 599–611, Springer, 2002.

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

**Flows over time with load-dependent transit times**.

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

**Megow, N.**.

**Performance analysis of on-line algorithms in machine scheduling**.

Diploma thesis, Technische Universität Berlin, 2002.

**Schulz, A. S. and Skutella, M.**.

**Scheduling Unrelated Machines by Randomized Rounding**.

*SIAM Journal on Discrete Mathematics*, Vol. 15, pp. 450–469, 2002.

**Schulz, A. S. and Skutella, M.**.

**The Power of α-Points in Preemptive Single Machine Scheduling**.

*Journal of Scheduling*, Vol. 5, pp. 121–133, 2002.

**Skutella, M.**.

**Approximating the single source unsplittable min-cost flow problem**.

*Mathematical Programming*, Vol. 91, pp. 493–514, 2002.

## 2003

**Baier, G.**.

**Flows with Path Restrictions**.

Doctoral thesis, TU Berlin, 2003.

**Kääb, V.**.

**Scheduling with AND/OR-Networks**.

Doctoral thesis, TU Berlin, 2003.