Martin Skutella

Articles in Journals and Conference Proceedings

• Fabrizio Grandoni, Volker Kaibel, Gianpaolo Oriolo & Martin Skutella,
  A short proof of the VPN tree routing conjecture on ring networks,
  Operations Research Letters, to appear.

• Maren Martens, Fernanda Salazar & Martin Skutella,
  Representing Single Source Multicommodity Flows as Convex Combinations of Unsplittable Flows,
  in Lars Arge & Emo Welzl (eds.): Algorithms - ESA 2007, Lecture Notes in Computer Science, Springer: Berlin, 2007, 395-406, Proceedings of the 15th Annual European Symposium on Algorithms (ESA'07).

• Joachim Reichel & Martin Skutella,
  Evolutionary Algorithms and Matroid Optimization Problems,
  in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'07), to appear.

• Nadine Baumann & Martin Skutella,
  Solving Evacuation Problems Efficiently: Earliest Arrival Flows with Multiple Sources,
  in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 339-408.

• Fritz Eisenbrand, Andreas Karrenbauer, Martin Skutella & Chihao Xu,
  Multiline Addressing by Network Flow,
  in Yossi Azar & Thomas Erlebach (eds.): Algorithms - ESA 2006, Lecture Notes in Computer Science 4168, Springer: Berlin, 2006, 744-755, Proceedings of the 14th Annual European Symposium on Algorithms (ESA'06).

• Luca Becchetti, Peter Korteweg, Alberto Marchetti-Spaccamela, Martin Skutella & Leen Stougie,
  Latency Constrained Aggregation in Sensor Networks,
  in Yossi Azar & Thomas Erlebach (eds.): Algorithms - ESA 2006, Lecture Notes in Computer Science 4168, Springer: Berlin, 2006, 88-99, Proceedings of the 14th Annual European Symposium on Algorithms (ESA'06).

• Georg Baier, Thomas Erlebach, Alex Hall, Ekkehard Köhler, Heiko Schilling & Martin Skutella,
  Length-Bounded Cuts and Flows,
  in M. Bugliesi, B. Preneel, V. Sassone & I. Wegener: Automata, Languages and Programming, Lecture Notes in Computer Science 4051, Springer: Berlin, 2006, 679-690, Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP'06).

• Maren Martens & Martin Skutella,
  Length-Bounded and Dynamic k-Splittable Flows,
  in Hans-Dietrich Haasis, Herbert Kopfer & Jörn Schönberger (eds.): Operations Research Proceedings 2005, Springer: Berlin, 2006, 297-302, Proceedings of the International Scientific Annual Conference "Operations Research 2005".

• Ronald Koch, Martin Skutella & Ines Spenke,
  Maximum k-Splittable s,t-Flows,
  Theory of Computing Systems, to appear.

  An extended abstract
  Approximation and Complexity of k-Splittable Flows,
  appeared in Thomas Erlebach and Giuseppe Persiano (eds.): Approximation and Online Algorithms, Lecture Notes in Computer Science 3879, Springer: Berlin, 2006, 244-257, Proceedings of the Third International Workshop on Approximation and Online Algorithms (WAOA'05).

• Martin Skutella,
  List scheduling in order of alpha-points on a single machine,
  in E. Bampis, K. Jansen and C. Kenyon (eds.): Efficient Approximation and Online Algorithms: Recent Progress on Classical Combinatorial Optimization Problems and New Applications, Lecture Notes in Computer Science 3484, Springer: Berlin, 2006, pp. 250-291.

• Fritz Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo & Martin Skutella,
  New Approaches for Virtual Private Network Design,
  SIAM Journal on Computing, to appear.

  An extended abstract appeared in L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, and M. Yung (eds.): Automata, Languages and Programming, Lecture Notes in Computer Science 3580, Springer: Berlin, 2005, 1151-1162, Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05).

• Maren Martens & Martin Skutella,
  Flows on Few Paths: Algorithms and Lower Bounds,
  Networks 48(2), 68-76, 2006.

  An extended abstract appeared in Susanne Albers and Tomasz Radzik (eds.): Algorithms - ESA 2004, Lecture Notes in Computer Science 3221, Springer: Berlin, 2004, 520-531, Proceedings of the 12th Annual European Symposium on Algorithms (ESA'04).

• Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos & Martin Skutella,
  Approximating k-Hop Minimum-Spanning Trees,
  Operations Research Letters 33(2), 115-120, 2005.

• Peter Sanders, Naveen Sivadasan & Martin Skutella,
  Online Scheduling with Bounded Migration,
  in J. Diaz, J. Karhumäki, A. Lepistö, and D. Sannella (eds.): Automata, Languages and Programming, Lecture Notes in Computer Science 3142, Springer: Berlin, 2004, 1111-1122, Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04).

• Alex Hall, Katharina Langkau & Martin Skutella,
  An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times,
  Algorithmica 47(3), 299-321, 2007.

  An extended abstract appeared in Sanjeev Arora, Klaus Jansen, José D. P. Rolim, and Amit Sahai (eds.): Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Computer Science 2764, Springer: Berlin, 2003, 71-82, Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'03).

• Lisa Fleischer & Martin Skutella,
  Quickest Flows Over Time,
  SIAM Journal on Computing 36(6), 1600-1630, 2007.

  Different parts of this work have appeared in preliminary form in our IPCO'02 and our SODA'03 papers which are listed below.

• Alex Hall, Steffen Hippler & Martin Skutella,
  Multicommodity Flows Over Time: Efficient Algorithms and Complexity,
  Theoretical Computer Science (special issue devoted to ICALP 2003), to appear.

  An extended abstract appeared in Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger (eds.): Automata, Languages and Programming, Lecture Notes in Computer Science 2719, Springer: Berlin, 2003, 397-409, Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP'03).

• Sándor P. Fekete, Martin Skutella & Gerhard J. Woeginger,
  The complexity of economic equilibria for house allocation markets,
  Information Processing Letters 88(5), 219-223, 2003.

• Lisa Fleischer & Martin Skutella,
  Minimum Cost Flows Over Time without Intermediate Storage,
  in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03), Society of Industrial and Applied Mathematics (2003), 66-75.

• Ekkehard Köhler, Rolf H. Möhring & Martin Skutella,
  Traffic Networks and Flows Over Time,
  in Jürg Kramer (ed.): DFG Research Center: Mathematics for Key Technologies, Berliner Mathematische Gesellschaft, 49-70, 2002.

• Georg Baier, Ekkehard Köhler & Martin Skutella,
  The k-splittable flow problem,
  Algorithmica 42(3-4), 231-248, 2005.
  (Special issue devoted to ESA 2002.)

  An extended abstract appeared in Rolf H. Möhring and Rajeev Raman (eds.): Algorithms - ESA '02, Lecture Notes in Computer Science 2461, Springer: Berlin, 2002, 101-113, Proceedings of the 10th Annual European Symposium on Algorithms (ESA'02).

• Ekkehard Köhler, Katharina Langkau & Martin Skutella,
  Time-Expanded Graphs for Flow-Dependent Transit Times,
  in Rolf H. Möhring and Rajeev Raman (eds.): Algorithms - ESA '02, Lecture Notes in Computer Science 2461, Springer: Berlin, 2002, 599-611, Proceedings of the 10th Annual European Symposium on Algorithms (ESA'02).

• Lisa Fleischer & Martin Skutella,
  The Quickest Multicommodity Flow Problem,
  in William J. Cook and Andreas S. Schulz (eds.): Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 2337, Springer: Berlin, 2002, 36-53, Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO'02).

• Ekkehard Köhler & Martin Skutella,
  Flows over time with load-dependent transit times,
  SIAM Journal on Optimization 15(4), 1185-1202, 2005.

  An extended abstract appeared in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02), Society of Industrial and Applied Mathematics (2002), 174-183.

• Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell & Martin Skutella,
  The freeze-tag problem: How to wake up a swarm of robots,
  Algorithmica 46(2), 193-221, 2006.

  An extended abstract appeared in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02), Society of Industrial and Applied Mathematics (2002), 568-577.

• Martin Skutella & Marc Uetz,
  Stochastic Machine Scheduling with Precedence Constraints,
  SIAM Journal on Computing 34(4), 788-802, 2005.

  Part of this work appeared as:
  Scheduling precedence-constrained jobs with stochastic processing times on parallel machines,
  in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'01), Society of Industrial and Applied Mathematics (2001), 589-590.

• Martin Skutella,
  Approximating the single source unsplittable min-cost flow problem,
  Mathematical Programming, Ser. B 91(3), 493-514, 2002.

  An extended abstract appeared in Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS'00), 136-145.

• Han Hoogeveen, Martin Skutella & Gerhard J. Woeginger,
  Preemptive scheduling with rejection,
  Mathematical Programming, Ser. B 94(2-3), 361-374, 2003.

  An extended abstract appeared in Mike Paterson (ed.): Algorithms - ESA 2000, Lecture Notes in Computer Science 1879, Springer: Berlin, 2000, 268-277, Proceedings of the 8th Annual European Symposium on Algorithms (ESA'00).

• Martin Skutella,
  Convex quadratic and semidefinite programming relaxations in scheduling,
  Journal of the Association for Computing Machinery 48(2), 206-242, 2001.

  This article combines my conference papers from FOCS'98 and ESA'99 which can be found below.

• Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella & Yaoguang Wang,
  Single machine scheduling with release dates,
  SIAM Journal on Discrete Mathematics 15(2), 165-192, 2002.

• Michel X. Goemans & Martin Skutella,
  Cooperative facility location games,
  Journal of Algorithms 50(2), 194-214, 2004.
  (Special issue devoted to SODA 2000.)

  An extended abstract appeared in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00), Society of Industrial and Applied Mathematics (2000), 76-85.

• Rolf H. Möhring, Martin Skutella & Frederik Stork,
  Scheduling with AND/OR precedence constraints,
  SIAM Journal on Computing 33(2), 393-415, 2004.

  Part of this work appeared as:
  Forcing relations for AND/OR precedence constraints,
  in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00), Society of Industrial and Applied Mathematics (2000), 235-236.

• Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Cliff Stein & Maxim Sviridenko,
  Approximation schemes for minimizing average weighted completion time with release dates,
  in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS'99), 32-43.

• Martin Skutella,
  Convex quadratic programming relaxations for network scheduling problems,
  in Jaroslav Nesetril (ed.): Algorithms - ESA '99, Lecture Notes in Computer Science 1643, Springer: Berlin, 1999, 127-138, Proceedings of the 7th Annual European Symposium on Algorithms (ESA'99).

• Martin Skutella & Gerhard J. Woeginger,
  A PTAS for minimizing the total weighted completion time on identical parallel machines,
  Mathematics of Operations Research 25(1), 63-75, 2000.

  An extended abstract appeared in Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC'99), pp. 400-407.

  If you are interested in the main ideas and intuitions of the result, you might want to have a look at my slides.

• Martin Skutella,
  Semidefinite Relaxations for Parallel Machine Scheduling,
  in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS'98), pp. 472-481.

• Andreas S. Schulz & Martin Skutella,
  Scheduling Unrelated Machines by Randomized Rounding,
  SIAM Journal on Discrete Mathematics 15(4), 450-469, 2002.

  This article contains the results from our ESA'97 paper and from Section 4 of our Random'97 paper which can be found below.

• Andreas S. Schulz & Martin Skutella,
  The Power of alpha-Points in Preemptive Single Machine Scheduling,
  Journal of Scheduling 5(2), 121-133, 2002.

• Clemens Gröpl & Martin Skutella,
  Parallel Repetition of MIP(2,1) Systems,
  in Ernst W. Mayr, Hans Jürgen Prömel, and Angelika Steger (eds.): Lectures on Proof Verification and Approximation Algorithms, Lecture Notes in Computer Science 1367, Springer: Berlin, 1998, pp. 161-177.

• Andreas S. Schulz & Martin Skutella,
  Random-Based Scheduling: New Approximations and LP Lower Bounds,
  in José Rolim (ed.): Randomization and Approximation Techniques in Computer Science, Lecture Notes in Computer Science 1269, Springer: Berlin, 1997, pp. 119-133, Proceedings of the 1st International Symposium on Randomization and Approximation Techniques in Computer Science (Random'97).

• Andreas S. Schulz & Martin Skutella,
  Scheduling-LPs Bear Probabilities: Randomized Approximations for Min-Sum Criteria,
  in Rainer Burkard and Gerhard J. Woeginger (eds.): Algorithms - ESA '97, Lecture Notes in Computer Science 1284, Springer: Berlin, 1997, pp. 416-429, Proceedings of the 5th Annual European Symposium on Algorithms (ESA'97).

• Martin Skutella,
  Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem,
  Mathematics of Operations Research 23(4), 909-929, 1998.

  An extended abstract appeared in Michael Saks et al., editors, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97). Society of Industrial and Applied Mathematics (1997), 501-508.

Technical Reports

Theses

• Approximation and Randomization in Scheduling, [pdf]  [ps]  [ps.Z]  [ps.gz],
  PhD thesis, Fachbereich Mathematik, Technische Universität Berlin, Germany, 1998.

• Konjugiertenklassen und Harish-Chandra-Serien symplektischer und orthogonaler Gruppen
  Diploma thesis (in German), Fachbereich Mathematik, Rheinisch-Westfälische Technische Hochschule Aachen, Germany, 1995.

• Bruce Hoppe, Efficient Dynamic Network Flow Algorithms, PhD thesis, Cornell University, 1995.

Copyright notice

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.