To top

Publications

  • Spatiotemporal reconstruction of ancient road networks through sequential cost–benefit analysis (, , and )
    PNAS Nexus, .
    DOI Bibtex
    @article{StahlbergSagnolDuckeKlimm2022,
    author = {Maximilian J. Stahlberg and Guillaume Sagnol and Benjamin Ducke and Max Klimm},
    title = {Spatiotemporal reconstruction of ancient road networks through sequential cost--benefit analysis},
    journal = {PNAS Nexus},
    year = {to appear},
    doi = {10.1093/pnasnexus/pgac313},
    }
  • On the Robustness of Potential-Based Flow Networks (, , and )
    Math. Program., .
    DOI Bibtex
    @article{KlimmPfetschRaber+2022,
    author = {Klimm, Max and Pfetsch, Marc E. and Raber, Rico and Skutella, Martin},
    title = {On the Robustness of Potential-Based Flow Networks},
    journal = {Math. Program.},
    year = {to appear},
    doi = {10.1007/s10107-021-01760-w},
    }
  • Combinatorial generation via permutation languages. III. Rectangulations ( and )
    Discret. Comput. Geom., .
    Extended abstract appeared in Proc. of SoCG 2021
    DOI Bibtex
    @article{MerinoMuetze2022,
    author = {Merino, Arturo and M\"{u}tze, Torsten},
    title = {{Combinatorial generation via permutation languages. III. Rectangulations}},
    journal = {Discret. Comput. Geom.},
    year = {to appear},
    doi = {10.48550/arXiv.2103.09333},
    }
  • Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling (, , and )
    IPCO 2023 – Proc. 24th Conference on Integer Programming and Combinatorial Optimization.
    PDF arxiv Bibtex
    @inproceedings{JaegerSagnolSchmidtGW2023,
    arxiv = {2211.02044},
    author = {Sven Jäger and Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt and Philipp Warode},
    title = {Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling},
    year = {2023},
    booktitle = {IPCO 2023 – Proc. 24th Conference on Integer Programming and Combinatorial Optimization},
    }
  • Single source unsplittable flows with arc-wise lower and upper bounds ( and )
    Math. Program., 192(1):477–496, .
    Extended abstract appeared in Proc. of IPCO 2020
    DOI Bibtex
    @article{MorellSkutella2021,
    author = {Morell, Sarah and Skutella, Martin},
    journal = {Math. Program.},
    title = {Single source unsplittable flows with arc-wise lower and upper bounds},
    pages = {477--496},
    year = {2022},
    volume = {192},
    number = {1},
    doi = {10.1007/s10107-021-01704-4},
    }
  • On a Combinatorial Generation Problem of Knuth (, and )
    SIAM J. Comput., 51(3):379-423, .
    Extended abstract appeared in Proc. of SODA 2021
    DOI Bibtex
    @article{MerinoMickaMuetze2022,
    author = {Merino, Arturo and Mička, Ondřej and M\"{u}tze, Torsten},
    title = {{On a Combinatorial Generation Problem of Knuth}},
    journal = {SIAM J. Comput.},
    year = {2022},
    volume = {51},
    number = {3},
    pages = {379-423},
    doi = {10.1137/20M1377394},
    }
  • Packing Under Convex Quadratic Constraints (, , and )
    Math. Program., 192(1):361–386, .
    Extended abstract appeared in Proc. of IPCO 2020
    DOI Bibtex
    @article{KlimmPfetschRaber+2021,
    author = {Max Klimm and Marc E. Pfetsch and Rico Raber and Martin Skutella},
    journal = {Math. Program.},
    volume = {192},
    number = {1},
    title = {Packing Under Convex Quadratic Constraints},
    year = {2022},
    pages = {361--386},
    doi = {10.1007/s10107-021-01675-6},
    }
  • PICOS: A Python interface to conic optimization solvers ( and )
    J. Open Source Softw., 7(70):3915, .
    DOI Bibtex
    @article{SagnolStahlberg2022,
    author = {Sagnol, Guillaume and Stahlberg, Maximilian},
    title = {{PICOS}: A Python interface to conic optimization solvers},
    journal = {J. Open Source Softw.},
    year = {2022},
    volume = {7},
    number = {70},
    pages = {3915},
    doi = {10.21105/joss.03915},
    }
  • Using reinforcement learning to control traffic signals in a real-world scenario: An approach based on linear function approximation (, and )
    IEEE Transactions on Intelligent Transportation Systems, 23(7):9126–9135, .
    [url] DOI Bibtex
    @article{AlegreZiemkeBazzan2020RLTrafficSignalsCottbus,
    author = {Lucas N. Alegre and Theresa Ziemke and Ana L. C. Bazzan},
    title = {Using reinforcement learning to control traffic signals in a real-world scenario: An approach based on linear function approximation},
    journal = {IEEE Transactions on Intelligent Transportation Systems},
    year = {2022},
    volume = {23},
    number = {7},
    pages = {9126--9135},
    doi = {10.1109/TITS.2021.3091014},
    url = {https://ieeexplore.ieee.org/document/9468362},
    }
  • The Effect of Speed Limits and Traffic Signal Control on Emissions (, and )
    Procedia Computer Science, 201:568–573, .
    [url] DOI Bibtex
    @article{RhodeWagnerZiemke2022EffectOfSpeedLimitsAndSignalsOnEmissions,
    author = {Jonathan Rhode and Peter Wagner and Theresa Ziemke},
    title = {The Effect of Speed Limits and Traffic Signal Control on Emissions},
    journal = {Procedia Computer Science},
    year = {2022},
    volume = {201},
    pages = {568--573},
    issn = {1877-0509},
    doi = {https://doi.org/10.1016/j.procs.2022.03.073},
    url = {https://www.sciencedirect.com/science/article/pii/S1877050922004860},
    }
  • Efficient generation of elimination trees and graph associahedra (, and )
    SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms, pp. 2128-2140.
    DOI Bibtex
    @inproceedings{CardinalMerinoMuetze2022,
    author = {Cardinal, Jean and Merino, Arturo and Mütze, Torsten},
    booktitle = {SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms},
    pages = {2128-2140},
    doi = {10.1137/1.9781611977073.84},
    title = {Efficient generation of elimination trees and graph associahedra},
    year = {2022},
    }
  • Competitive Algorithms for Symmetric Rendezvous on the Line (, , and )
    SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms, pp. 329–347.
    [url] DOI Bibtex
    @inproceedings{KlimmSagnolSkutella+2022,
    author = {Klimm, Max and Sagnol, Guillaume and Skutella, Martin and Van Tran, Khai},
    booktitle = {SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms},
    title = {Competitive Algorithms for Symmetric Rendezvous on the Line},
    doi = {10.1137/1.9781611977073.16},
    pages = {329--347},
    year = {2022},
    url = {https://epubs.siam.org/doi/reader/10.1137/1.9781611977073.16},
    }
  • A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method (, and )
    SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms, pp. 90–102.
    DOI Bibtex
    @inproceedings{SchloeterSkutTran2022,
    author = {Schl\"oter, Miriam and Skutella, Martin and Tran, Khai Van},
    booktitle = {SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms},
    pages = {90--102},
    doi = {10.1137/1.9781611977073.5},
    title = {A Faster Algorithm for Quickest Transshipments via an Extended Discrete {N}ewton Method},
    year = {2022},
    }
  • The Hamilton compression of highly symmetric graphs (, and )
    MFCS 2022 – Proc. 47th International Symposium on Mathematical Foundations of Computer Science, pp. 54:1–54:14.
    DOI Bibtex
    @inproceedings{GregorMerinoMuetze2022a,
    author = {Gregor, Petr and Merino, Arturo and M\"{u}tze, Torsten},
    booktitle = {MFCS 2022 – Proc. 47th International Symposium on Mathematical Foundations of Computer Science},
    pages = {54:1--54:14},
    doi = {10.4230/LIPIcs.MFCS.2022.54},
    title = {{The Hamilton compression of highly symmetric graphs}},
    year = {2022},
    }
  • Star Transposition Gray Codes for Multiset Permutations (, and )
    STACS 2022 – Proc. 39th International Symposium on Theoretical Aspects of Computer Science, pp. 34:1–34:14.
    DOI Bibtex
    @inproceedings{GregorMerinoMuetze2022,
    author = {Gregor, Petr and Merino, Arturo and M\"{u}tze, Torsten},
    booktitle = {STACS 2022 – Proc. 39th International Symposium on Theoretical Aspects of Computer Science},
    pages = {34:1--34:14},
    doi = {10.4230/LIPIcs.STACS.2022.34},
    title = {{Star Transposition Gray Codes for Multiset Permutations}},
    year = {2022},
    }
  • All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges (, and )
    FUN 2022 – Proc. 11th International Conference on Fun with Algorithms, pp. 22:1–22:28.
    DOI Bibtex
    @inproceedings{MerinoMuetzeWilliams2022,
    author = {Merino, Arturo and M\"{u}tze, Torsten and Williams, Aaron},
    booktitle = {FUN 2022 – Proc. 11th International Conference on Fun with Algorithms},
    pages = {22:1--22:28},
    doi = {10.4230/LIPIcs.FUN.2022.22},
    title = {{All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges}},
    year = {2022},
    }
  • Improved Bounds for Stochastic Extensible Bin Packing under Distributional Assumptions ( and )
    ISCO 2022 – Proc. 7th International Symposium on Combinatorial Optimization, pp. 228–241.
    PDF DOI arxiv Bibtex
    @inproceedings{SagnolSchmidtGW22,
    title = {Improved Bounds for Stochastic Extensible Bin Packing under Distributional Assumptions},
    author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel},
    booktitle = {ISCO 2022 – Proc. 7th International Symposium on Combinatorial Optimization},
    year = {2022},
    doi = {10.1007/978-3-031-18530-4_17},
    series = {Lecture Notes in Computer Science},
    volume = {13526},
    pages = {228--241},
    arxiv = {2002.00060},
    }
  • Removing inessential points in $c-$ and $A-$optimal design ( and )
    J. Stat. Plan. Inference, 213:233–252, .
    [url] DOI Bibtex
    @article{PronzatoSagnol2021,
    author = {Pronzato, Luc and Sagnol, Guillaume},
    title = {Removing inessential points in $c-$ and $A-$optimal design},
    journal = {J. Stat. Plan. Inference},
    year = {2021},
    doi = {10.1016/j.jspi.2020.11.011},
    volume = {213},
    pages = {233--252},
    url = {https://hal.science/hal-02868664},
    }
  • A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs (, and )
    Oper. Res. Lett., 49(6):842–843, .
    DOI Bibtex
    @article{CheriyanRaviSkutella2021,
    author = {Cheriyan, Joseph and Ravi, R. and Skutella, Martin},
    journal = {Oper. Res. Lett.},
    pages = {842--843},
    title = {A simple proof of the {M}oore-{H}odgson Algorithm for minimizing the number of late jobs},
    volume = {49},
    number = {6},
    year = {2021},
    doi = {10.1016/j.orl.2021.09.005},
    }
  • Flows Over Time as Continuous Limits of Packet-Based Network Simulations (, , , , and )
    Transportation Research Procedia, 52:123–130, .
    DOI Bibtex
    @article{ZiemkeSeringVargas+2021,
    author = {Ziemke, Theresa and Sering, Leon and V{argas Koch}, Laura and Zimmer, Max and Nagel, Kai and Skutella, Martin},
    journal = {Transportation Research Procedia},
    doi = {10.1016/j.trpro.2021.01.014},
    pages = {123--130},
    title = {Flows Over Time as Continuous Limits of Packet-Based Network Simulations},
    volume = {52},
    year = {2021},
    }
  • Reinforcement learning vs. rule-based adaptive traffic signal control: A Fourier basis linear function approximation for traffic signal control (, and )
    AI Communications, 34(1):89–103, .
    [url] DOI Bibtex
    @article{ZiemkeEtAl2020RLTrafficSignalControlSingleIntersectionExtension,
    author = {Theresa Ziemke and Lucas N. Alegre and Ana L. C. Bazzan},
    title = {Reinforcement learning vs. rule-based adaptive traffic signal control: {A} {F}ourier basis linear function approximation for traffic signal control},
    journal = {AI Communications},
    year = {2021},
    volume = {34},
    number = {1},
    pages = {89--103},
    doi = {10.3233/AIC-201580},
    url = {https://content.iospress.com/articles/ai-communications/aic201580},
    }
  • Automated generation of traffic signals and lanes for MATSim based on OpenStreetMap ( and )
    Procedia Computer Science, 184:745–752, .
    [url] DOI Bibtex
    @article{ZiemkeBraun2020OsmSignalsAndLanes,
    author = {Theresa Ziemke and S\"ohnke Braun},
    title = {Automated generation of traffic signals and lanes for {MATS}im based on {O}pen{S}treet{M}ap},
    journal = {Procedia Computer Science},
    year = {2021},
    volume = {184},
    pages = {745--752},
    issn = {1877-0509},
    doi = {https://doi.org/10.1016/j.procs.2021.03.093},
    url = {https://www.sciencedirect.com/science/article/pii/S1877050921007328},
    }
  • Towards Lower Bounds on the Depth of ReLU Neural Networks (, , and )
    NeurIPS 2021 – Proc. 35th Conference on Neural Information Processing Systems, pp. 3336–3348.
    Bibtex
    @inproceedings{HertrichBasuDiSumma+2021,
    author = {Hertrich, Chistoph and Basu, Amitabh and Di Summa, Marco and Skutella, Martin},
    booktitle = {NeurIPS 2021 – Proc. 35th Conference on Neural Information Processing Systems},
    title = {Towards Lower Bounds on the Depth of ReLU Neural Networks},
    year = {2021},
    pages = {3336--3348},
    }
  • On a Combinatorial Generation Problem of Knuth (, and )
    SODA 2021 – Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms, pp. 735–743.
    DOI Bibtex
    @inproceedings{MerinoMickaMuetze2021,
    author = {Merino, Arturo and Mička, Ondřej and M\"{u}tze, Torsten},
    booktitle = {SODA 2021 – Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms},
    pages = {735–743},
    doi = {10.1137/1.9781611976465.46},
    title = {{On a Combinatorial Generation Problem of Knuth}},
    year = {2021},
    }
  • Minimum-cost integer circulations in given homology classes (, and )
    SODA 2021 – Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms, pp. 2725–2739.
    Bibtex
    @inproceedings{morell2021minimum,
    title = {Minimum-cost integer circulations in given homology classes},
    author = {Morell, Sarah and Seidel, Ina and Weltge, Stefan},
    booktitle = {SODA 2021 – Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms},
    pages = {2725--2739},
    year = {2021},
    }
  • Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size ( and )
    AAAI 2021 – Proc. 35th AAAI Conference on Artificial Intelligence, pp. 7685–7693.
    Bibtex
    @inproceedings{HertrichSkutella2021,
    author = {Hertrich, Christoph and Skutella, Martin},
    booktitle = {AAAI 2021 – Proc. 35th AAAI Conference on Artificial Intelligence},
    pages = {7685--7693},
    title = {Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size},
    year = {2021},
    }
  • Restricted Adaptivity in Stochastic Scheduling ( and )
    ESA 2021 – Proc. 29th European Symposium on Algorithms, pp. 79:1–79:14.
    PDF DOI arxiv Bibtex
    @inproceedings{SagnolSchmidtGW21,
    author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel},
    title = {{Restricted Adaptivity in Stochastic Scheduling}},
    booktitle = {ESA 2021 – Proc. 29th European Symposium on Algorithms},
    pages = {79:1--79:14},
    series = {LIPIcs},
    year = {2021},
    volume = {204},
    doi = {10.4230/LIPIcs.ESA.2021.79},
    arxiv = {2106.15393},
    }
  • Efficient Generation of Rectangulations via Permutation Languages ( and )
    SoCG 2021 – Proc. 37th International Symposium on Computational Geometry, pp. 54:1–54:18.
    DOI Bibtex
    @inproceedings{MerinoMuetze2021,
    author = {Merino, Arturo and M\"{u}tze, Torsten},
    booktitle = {SoCG 2021 – Proc. 37th International Symposium on Computational Geometry},
    pages = {54:1--54:18},
    doi = {10.4230/LIPIcs.SoCG.2021.54},
    title = {{Efficient Generation of Rectangulations via Permutation Languages}},
    year = {2021},
    }
  • Convergence of a Packet Routing Model to Flows Over Time (, and )
    Proceedings of the 22nd ACM Conference on Economics and Computation, Association for Computing Machinery, pp. 797–816.
    [url] DOI Bibtex
    @inproceedings{SeringEtAl2021ConvergenceFlowOverTimes,
    author = {Leon Sering and Laura Vargas Koch and Theresa Ziemke},
    title = {{C}onvergence of a {P}acket {R}outing {M}odel to {F}lows {O}ver {T}ime},
    booktitle = {Proceedings of the 22nd ACM Conference on Economics and Computation},
    year = {2021},
    pages = {797--816},
    address = {New York, NY, USA},
    publisher = {Association for Computing Machinery},
    doi = {10.1145/3465456.3467626},
    isbn = {9781450385541},
    url = {https://dl.acm.org/doi/10.1145/3465456.3467626},
    }
  • Approximation in Deterministic and Stochastic Machine Scheduling ()
    PhD thesis, TU Berlin, .
    [url] DOI Bibtex
    @phdthesis{ThesisJaeger,
    author = {Jäger, Sven J.},
    title = {Approximation in Deterministic and Stochastic Machine Scheduling},
    school = {TU Berlin},
    year = {2021},
    type = {Doctoral Thesis},
    address = {Berlin},
    doi = {10.14279/depositonce-12198},
    url = {http://dx.doi.org/10.14279/depositonce-12198},
    keywords = {approximation algorithms, online algorithms, machine scheduling, stochastic scheduling, Approximationsalgorithmen, Online-Algorithmen, Machinenbelegungsplanung, stochastische Ablaufplanung},
    }
  • Approximate and exact D-optimal designs for $2^k$ factorial experiments for Generalized Linear Models via SOCP ( and )
    Stat. Pap., 61:2737–2767, .
    [url] DOI Bibtex
    @article{DuarteSagnol2020,
    author = {Duarte, Belmiro P.M. and Sagnol, Guillaume},
    title = {Approximate and exact D-optimal designs for $2^k$ factorial experiments for Generalized Linear Models via SOCP},
    year = {2020},
    doi = {10.1007/s00362-018-01075-7},
    journal = {Stat. Pap.},
    volume = {61},
    pages = {2737--2767},
    url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-66256},
    }
  • Packing Under Convex Quadratic Constraints (, , and )
    IPCO 2020 – Proc. 21st Conference on Integer Programming and Combinatorial Optimization, pp. 266–279.
    Extended version appeared in Math. Program. 2021
    DOI Bibtex
    @inproceedings{KlimmPfetschRaber+2020,
    author = {Max Klimm and Marc E. Pfetsch and Rico Raber and Martin Skutella},
    booktitle = {IPCO 2020 – Proc. 21st Conference on Integer Programming and Combinatorial Optimization},
    doi = {10.1007/978-3-030-45771-6\_21},
    pages = {266--279},
    title = {Packing Under Convex Quadratic Constraints},
    year = {2020},
    }
  • Single source unsplittable flows with arc-wise lower and upper bounds ( and )
    IPCO 2020 – Proc. 21st Conference on Integer Programming and Combinatorial Optimization, pp. 294–306.
    Full paper appeared in Math. Program. 2021
    DOI Bibtex
    @inproceedings{MorellSkutella-IPCO2020,
    author = {Morell, Sarah and Skutella, Martin},
    booktitle = {IPCO 2020 – Proc. 21st Conference on Integer Programming and Combinatorial Optimization},
    doi = {10.1007/978-3-030-45771-6\_23},
    pages = {294--306},
    title = {Single source unsplittable flows with arc-wise lower and upper bounds},
    year = {2020},
    }
  • On the Two-Dimensional Knapsack Problem for Convex Polygons ( and )
    ICALP 2020 – Proc. 47th International Colloquium on Automata, Languages and Programming, pp. 84:1–84:16.
    DOI Bibtex
    @inproceedings{MerinoWiese2020,
    author = {Arturo Merino and Andreas Wiese},
    booktitle = {ICALP 2020 – Proc. 47th International Colloquium on Automata, Languages and Programming},
    pages = {84:1--84:16},
    doi = {10.4230/LIPIcs.ICALP.2020.84},
    title = {{On the Two-Dimensional Knapsack Problem for Convex Polygons}},
    year = {2020},
    }
  • On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems (, , , and )
    IPDPS 2020 – Proc. 34thIEEE International Parallel and Distributed Processing Symposium, pp. 1061–1070.
    DOI Bibtex
    @inproceedings{MarchettiMegowSchloeter+2020,
    author = {Marchetti-Spaccamela, Alberto and Megow, Nicole and Schl\"oter, Jens and Skutella, Martin and Stougie, Leen},
    booktitle = {IPDPS 2020 – Proc. 34thIEEE International Parallel and Distributed Processing Symposium},
    pages = {1061--1070},
    title = {On the Complexity of Conditional {DAG} Scheduling in Multiprocessor Systems},
    year = {2020},
    doi = {10.1109/IPDPS47924.2020.00112},
    }
  • A reinforcement learning approach with Fourier basis linear function approximation for traffic signal control (, and )
    CEUR Workshop Proceedings, pp. 55–62.
    [pdf] Bibtex
    @inproceedings{ZiemkeEtAl2020RLTrafficSignalControlSingleIntersection,
    author = {Theresa Ziemke and Lucas N. Alegre and Ana L. C. Bazzan},
    title = {A reinforcement learning approach with {F}ourier basis linear function approximation for traffic signal control},
    booktitle = {CEUR Workshop Proceedings},
    year = {2020},
    volume = {2701},
    series = {ATT 2020 Agents in Traffic and Transportation},
    pages = {55--62},
    url = {http://ceur-ws.org/Vol-2701/paper_2.pdf},
    }
  • Nash Flows Over Time ()
    PhD thesis, TU Berlin, .
    [url] DOI Bibtex
    @phdthesis{ThesisSering,
    author = {Sering, Leon},
    title = {Nash Flows Over Time},
    school = {TU Berlin},
    year = {2020},
    type = {Doctoral Thesis},
    doi = {10.14279/depositonce-10640},
    url = {http://dx.doi.org/10.14279/depositonce-10640},
    keywords = {flow over time, dynamic equilibria, deterministic queuing model, dynamic traffic assignment, spillback, kinematic waves, multi-commodity flows, zeitabhängige Flüsse, dynamische Gleichgewichte, deterministisches Warteschlangenmodell, dynamischer Verkehrsfluss, Rückstau, kinematische Wellen, Mehrgüterflüsse},
    }
  • Some Aspects of Graph Sparsification in Theory and Practice ()
    PhD thesis, TU Berlin, .
    [url] DOI Bibtex
    @phdthesis{ThesisDaeubel,
    author = {Däubel, Karl},
    title = {Some Aspects of Graph Sparsification in Theory and Practice},
    school = {TU Berlin},
    year = {2020},
    type = {Doctoral Thesis},
    doi = {10.14279/depositonce-10226},
    url = {http://dx.doi.org/10.14279/depositonce-10226},
    keywords = {graph sparsification, graph contractions, multiscale optimization, ring loading, chain decompositions, Graphvereinfachung, Graphkontraktionen, multiscale Optimierung, Kettenzerlegungen},
    }
  • The Simplex Algorithm is NP-Mighty ( and )
    ACM Trans. Algorithms, 15(1):5:1–5:19, .
    Extended abstract appeared in Proc. of SODA 2015
    DOI Bibtex
    @article{DisserSkutella2019,
    author = {Disser, Yann and Skutella, Martin},
    title = {The Simplex Algorithm is NP-Mighty},
    journal = {ACM Trans. Algorithms},
    volume = {15},
    number = {1},
    pages = {5:1--5:19},
    year = {2019},
    doi = {10.1145/3280847},
    }
  • Paths to stable allocations ( and )
    Int. J. Game Theory, 48(3):835–862, .
    DOI Bibtex
    @article{CsehSkutella2019,
    author = {Cseh, {\'{A}}gnes and Skutella, Martin},
    title = {Paths to stable allocations},
    journal = {Int. J. Game Theory},
    volume = {48},
    number = {3},
    pages = {835--862},
    year = {2019},
    doi = {10.1007/s00182-019-00664-6},
    }
  • Algorithmic results for potential-based flows: Easy and hard cases (, , , and )
    Networks, 73(3):306–324, .
    DOI Bibtex
    @article{GrossPfetschSchewe+2019,
    author = {Gro{\ss}, Martin and Pfetsch, Marc E. and Schewe, Lars and Schmidt, Martin and Skutella, Martin},
    title = {Algorithmic results for potential-based flows: Easy and hard cases},
    journal = {Networks},
    volume = {73},
    number = {3},
    pages = {306--324},
    year = {2019},
    doi = {10.1002/net.21865},
    }
  • An unexpected connection between Bayes $A-$optimal designs and the Group Lasso ( and )
    Stat. Pap., 60(2):215–234, .
    PDF DOI arxiv Bibtex
    @article{SagnolPauwels2019,
    author = {Sagnol, Guillaume and Pauwels, Edouard},
    title = {An unexpected connection between Bayes $A-$optimal designs and the Group Lasso},
    journal = {Stat. Pap.},
    year = {2019},
    arxiv = {1809.01931},
    doi = {10.1007/s00362-018-01062-y},
    volume = {60},
    number = {2},
    pages = {215--234},
    }
  • Maximizing the storage capacity of gas networks: a global MINLP approach (, , , , , , and )
    Optim. Eng., 20:543–573, .
    DOI Bibtex
    @article{BurlascuEggerGrossEtAl-2019,
    author = {Burlacu, Robert and Egger, Herbert and Gro{\ss}, Martin and Martin, Alexander and Pfetsch, Marc~E. and Schewe, Lars and Sirvent, Mathias and Skutella, Martin},
    doi = {10.1007/s11081-018-9414-5},
    journal = {Optim. Eng.},
    pages = {543--573},
    title = {Maximizing the storage capacity of gas networks: a global {MINLP} approach},
    volume = {20},
    year = {2019},
    }
  • Optimization and simulation of fixed-time traffic signal control in real-world applications (, , and )
    Procedia Computer Science, Elsevier BV, 151:826–833, .
    DOI Bibtex
    @article{ThunigSchefflerStrehlerNagel2019MatsimCtenSignalOptCottbus,
    author = {Theresa Thunig and Robert Scheffler and Martin Strehler and Kai Nagel},
    title = {Optimization and simulation of fixed-time traffic signal control in real-world applications},
    journal = {Procedia Computer Science},
    year = {2019},
    volume = {151},
    pages = {826--833},
    issn = {1877-0509},
    doi = {10.1016/j.procs.2019.04.113},
    publisher = {Elsevier {BV}},
    }
  • Adaptive traffic signal control for real-world scenarios in agent-based transport simulations (, and )
    Transportation Research Procedia, Elsevier BV, 37:481–488, .
    [url] DOI Bibtex
    @article{ThunigKuehnelNagel2018ExtendingLaemmerToFixedStages,
    author = {Theresa Thunig and Nico K\"uhnel and Kai Nagel},
    title = {Adaptive traffic signal control for real-world scenarios in agent-based transport simulations},
    journal = {Transportation Research Procedia},
    year = {2019},
    volume = {37},
    pages = {481--488},
    issn = {2352-1465},
    doi = {10.1016/j.trpro.2018.12.215},
    publisher = {Elsevier {BV}},
    url = {http://www.sciencedirect.com/science/article/pii/S2352146518306343},
    }
  • The Minimum Cost Query Problem on Matroids with Uncertainty Areas ( and )
    ICALP 2019 – Proc. 46th International Colloquium on Automata, Languages and Programming, pp. 83:1–83:14.
    DOI Bibtex
    @inproceedings{MerinoSoto2019,
    author = {Arturo Merino and Jos{\'e} A. Soto},
    booktitle = {ICALP 2019 – Proc. 46th International Colloquium on Automata, Languages and Programming},
    pages = {83:1--83:14},
    doi = {10.4230/LIPIcs.ICALP.2019.83},
    title = {{The Minimum Cost Query Problem on Matroids with Uncertainty Areas}},
    year = {2019},
    }
  • Effects of user adaption on traffic-responsive signal control in agent-based transport simulations ( and )
    6th International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), pp. 1–7.
    [url] DOI Bibtex
    @inproceedings{ThunigNagel2019SignalsUnderRouteChoice,
    author = {Thunig, Theresa and Nagel, Kai},
    title = {Effects of user adaption on traffic-responsive signal control in agent-based transport simulations},
    booktitle = {6th International Conference on Models and Technologies for Intelligent Transportation Systems ({MT}-{ITS})},
    year = {2019},
    pages = {1--7},
    doi = {10.1109/MTITS.2019.8883373},
    url = {https://ieeexplore.ieee.org/document/8883373},
    }
  • Multicriteria Linear Optimisation with Applications in Sustainable Manufacturing ()
    PhD thesis, TU Berlin, .
    [url] DOI Bibtex
    @phdthesis{ThesisSchenker,
    author = {Schenker, Sebastian},
    title = {Multicriteria Linear Optimisation with Applications in Sustainable Manufacturing},
    school = {TU Berlin},
    year = {2019},
    type = {Doctoral Thesis},
    address = {Berlin},
    doi = {10.14279/depositonce-9244},
    url = {http://dx.doi.org/10.14279/depositonce-9244},
    keywords = {mathematical optimisation, linear programming, integer programming, linear optimisation, multicriteria optimisation, mathematische Optimierung, lineare Programmierung, ganzzahlige Programmierung, lineare Optimierung},
    }
  • Robust Randomized Matchings (, and )
    Math. Oper. Res., 43(2):675–692, .
    Extended abstract appeared in Proc. of SODA 2015
    DOI Bibtex
    @article{MatuschkeSkutellaSoto2018,
    author = {Matuschke, Jannik and Skutella, Martin and Soto, José A.},
    title = {Robust Randomized Matchings},
    journal = {Math. Oper. Res.},
    volume = {43},
    number = {2},
    pages = {675--692},
    year = {2018},
    doi = {10.1287/moor.2017.0878},
    }
  • An algorithm based on Semidefinite Programming for finding minimax optimal designs (, and )
    Comput. Stat. Data Anal., 119:99–117, .
    [url] DOI Bibtex
    @article{DuarteSagnolWong2018,
    author = {Duarte, Belmiro P.M. and Sagnol, Guillaume and Wong, Weng Kee},
    title = {An algorithm based on Semidefinite Programming for finding minimax optimal designs},
    journal = {Comput. Stat. Data Anal.},
    volume = {119},
    pages = {99--117},
    year = {2018},
    doi = {10.1016/j.csda.2017.09.008},
    url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-66249},
    }
  • The Cone of Flow Matrices: Approximation Hierarchies and Applications (, and )
    Networks, 72(1):128–150, .
    Extended abstract appeared in Proc. of INOC 2017
    [url] DOI Bibtex
    @article{SagnolBlancoSauvage2018,
    author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibault},
    title = {The Cone of Flow Matrices: Approximation Hierarchies and Applications},
    journal = {Networks},
    doi = {10.1002/net.21820},
    year = {2018},
    volume = {72},
    number = {1},
    pages = {128--150},
    url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-64399},
    }
  • Robust allocation of operating rooms: A cutting plane approach to handle lognormal case durations (, , , , , and )
    Eur. J. Oper. Res., 271(2):420–435, .
    [url] DOI Bibtex
    @article{SagnolBarnerBorndoerferetal.2018,
    title = {Robust allocation of operating rooms: A cutting plane approach to handle lognormal case durations},
    journal = {Eur. J. Oper. Res.},
    year = {2018},
    volume = {271},
    number = {2},
    pages = {420--435},
    doi = {10.1016/j.ejor.2018.05.022},
    author = {Sagnol, Guillaume and Barner, Christoph and Bornd{\"o}rfer, Ralf and Grima, Micka{\"e}l and Seeling, Matthes and Spies, Claudia and Wernecke, Klaus},
    url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-58502},
    }
  • On the complexity of instationary gas flows (, and )
    Oper. Res. Lett., 46(3):286–290, .
    DOI Bibtex
    @article{GrossPfetschSkutella2018,
    author = {Gro{\ss}, Martin and Pfetsch, Marc E. and Skutella, Martin},
    title = {On the complexity of instationary gas flows},
    journal = {Oper. Res. Lett.},
    volume = {46},
    number = {3},
    pages = {286--290},
    year = {2018},
    doi = {10.1016/j.orl.2018.01.007},
    }
  • Implementing an adaptive traffic signal control algorithm in an agent-based transport simulation (, and )
    Procedia Computer Science, Elsevier BV, 130:894–899, .
    DOI Bibtex
    @article{KuehnelThunigNagel2018ImplementLaemmerInMATSim,
    author = {Nico K\"uhnel and Theresa Thunig and Kai Nagel},
    title = {Implementing an adaptive traffic signal control algorithm in an agent-based transport simulation},
    journal = {Procedia Computer Science},
    year = {2018},
    volume = {130},
    pages = {894--899},
    doi = {10.1016/j.procs.2018.04.086},
    publisher = {Elsevier {BV}},
    }
  • Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling ( and )
    STACS 2018 – Proc. 35th International Symposium on Theoretical Aspects of Computer Science, pp. 43:1–43:14.
    DOI Bibtex
    @inproceedings{JagerSkutella2018,
    author = {J{\"{a}}ger, Sven and Skutella, Martin},
    title = {Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling},
    booktitle = {STACS 2018 – Proc. 35th International Symposium on Theoretical Aspects of Computer Science},
    pages = {43:1--43:14},
    year = {2018},
    doi = {10.4230/LIPIcs.STACS.2018.43},
    }
  • Multi-Source Multi-Sink Nash Flows over Time ( and )
    ATMOS 2018 – Proc. 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, pp. 12:1–12:20.
    DOI Bibtex
    @inproceedings{SeringSkutella2018,
    author = {Sering, Leon and Skutella, Martin},
    title = {Multi-Source Multi-Sink Nash Flows over Time},
    booktitle = {ATMOS 2018 – Proc. 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
    pages = {12:1--12:20},
    year = {2018},
    doi = {10.4230/OASIcs.ATMOS.2018.12},
    }
  • Diversity Maximization in Doubling Metrics (, and )
    ISAAC 2018 – Proc. 29th International Symposium on Algorithms and Computation.
    Bibtex
    @inproceedings{cevallos2018diversity,
    title = {Diversity Maximization in Doubling Metrics},
    author = {Cevallos, Alfonso and Eisenbrand, Friedrich and Morell, Sarah},
    booktitle = {ISAAC 2018 – Proc. 29th International Symposium on Algorithms and Computation},
    year = {2018},
    }
  • A Fully Polynomial Time Approximation Scheme for Packing While Traveling (, , , and )
    ALGOCLOUD 2018 – Proc. 4th International Symposium on Algorithmic Aspects of Cloud Computing, pp. 59–72.
    DOI Bibtex
    @inproceedings{NeumannPolyakovskiySkutella2018,
    author = {Neumann, Frank and Polyakovskiy, Frank and Skutella, Martin and Stougie, Leen and Wu, Junhua},
    title = {A Fully Polynomial Time Approximation Scheme for Packing While Traveling},
    booktitle = {ALGOCLOUD 2018 – Proc. 4th International Symposium on Algorithmic Aspects of Cloud Computing},
    pages = {59--72},
    year = {2018},
    doi = {10.1007/978-3-030-19759-9\_5},
    }
  • Approximation Hierarchies for the Cone of Flow Matrices (, and )
    INOC 2017 – Proc. 8th International Network Optimization Conference, pp. 275 – 284.
    [url] DOI Bibtex
    @inproceedings{SagnolBlancoSauvageInoc2017,
    title = {Approximation Hierarchies for the Cone of Flow Matrices},
    author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibault},
    year = {2018},
    booktitle = {INOC 2017 – Proc. 8th International Network Optimization Conference},
    volume = {64},
    pages = {275 -- 284},
    doi = {10.1016/j.endm.2018.02.002},
    series = {Electron. Notes Discret. Math.},
    url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-64399},
    }
  • The Price of Fixed Assignments in Stochastic Extensible Bin Packing (, and )
    WAOA 2018 – Proc. 16th Workshop on Approximation and Online Algorithms, pp. 327–347.
    PDF DOI arxiv Bibtex
    @inproceedings{SagnolSchmidtGWTesch2018,
    title = {The Price of Fixed Assignments in Stochastic Extensible Bin Packing},
    year = {2018},
    author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel and Tesch, Alexander},
    booktitle = {WAOA 2018 – Proc. 16th Workshop on Approximation and Online Algorithms},
    volume = {11312},
    pages = {327--347},
    doi = {10.1007/978-3-030-04693-4_20},
    arxiv = {2002.00060},
    }
  • Uncertainty Exploration : Algorithms, Competitive Analysis, and Computational Experiments ()
    PhD thesis, TU Berlin, .
    [url] DOI Bibtex
    @phdthesis{ThesisMeissner,
    author = {Meißner, Julie},
    title = {Uncertainty Exploration : Algorithms, Competitive Analysis, and Computational Experiments},
    school = {TU Berlin},
    year = {2018},
    type = {Doctoral Thesis},
    address = {Berlin},
    doi = {10.14279/depositonce-7327},
    url = {http://dx.doi.org/10.14279/depositonce-7327},
    }
  • Flows Over Time and Submodular Function Minimization ()
    PhD thesis, TU Berlin, .
    [url] DOI Bibtex
    @phdthesis{ThesisSchloeter,
    author = {Schlöter, Miriam},
    title = {Flows Over Time and Submodular Function Minimization},
    school = {TU Berlin},
    year = {2018},
    type = {Doctoral Thesis},
    address = {Berlin},
    doi = {10.14279/depositonce-7531},
    url = {http://dx.doi.org/10.14279/depositonce-7531},
    keywords = {flows over time, submodular function minimization, earliest arrival flows, quickest transshipments, evacuation, zeitabhängige Flüsse, submodulare Funktion, Minimierung, Evakuierung},
    }
  • Randomization Helps Computing a Minimum Spanning Tree under Uncertainty (, and )
    SIAM J. Comput., 46(4):1217–1240, .
    Extended abstract appeared in Proc. of ESA 2015
    DOI Bibtex
    @article{MegowMeissnerSkutella2017,
    author = {Megow, Nicole and Mei{\ss}ner, Julie and Skutella, Martin},
    title = {Randomization Helps Computing a Minimum Spanning Tree under Uncertainty},
    journal = {SIAM J. Comput.},
    volume = {46},
    number = {4},
    pages = {1217--1240},
    year = {2017},
    doi = {10.1137/16M1088375},
    }
  • Optimal duty rostering for toll enforcement inspectors (, , and )
    Ann. Oper. Res., 252(2):383–406, .
    [url] DOI Bibtex
    @article{BorndoerferSagnolSchlechteetal.2017,
    author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schlechte, Thomas and Swarat, Elmar},
    title = {Optimal duty rostering for toll enforcement inspectors},
    journal = {Ann. Oper. Res.},
    doi = {10.1007/s10479-016-2152-1},
    year = {2017},
    volume = {252},
    number = {2},
    pages = {383--406},
    url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-45107},
    }
  • Protection of flows under targeted attacks (, , , and )
    Oper. Res. Lett., 45(1):53–59, .
    DOI Bibtex
    @article{MatuschkeMcCormickOriolo+2017,
    author = {Matuschke, Jannik and McCormick, S. Thomas and Oriolo, Gianpaolo and Peis, Britta and Skutella, Martin},
    title = {Protection of flows under targeted attacks},
    journal = {Oper. Res. Lett.},
    volume = {45},
    number = {1},
    pages = {53--59},
    year = {2017},
    doi = {10.1016/j.orl.2016.11.005},
    }
  • The structure of user equilibria: Dynamic coevolutionary simulations vs. cyclically expanded networks ( and )
    Procedia Computer Science, 109:648–655, .
    [url] DOI Bibtex
    @article{ThunigNagel2017UeInMatsimVsKsModel,
    author = {Thunig, Theresa and Nagel, Kai},
    title = {The structure of user equilibria: Dynamic coevolutionary simulations vs. cyclically expanded networks},
    journal = {Procedia Computer Science},
    year = {2017},
    volume = {109},
    pages = {648--655},
    doi = {10.1016/j.procs.2017.05.371},
    url = {https://doi.org/10.1016/j.procs.2017.05.371},
    }
  • Fast and Memory-Efficient Algorithms for Evacuation Problems ( and )
    SODA 2017 – Proc. 28th ACM-SIAM Symposium on Discrete Algorithms, pp. 821–840.
    DOI Bibtex
    @inproceedings{SchloeterSkutella2017,
    author = {Schl{\"{o}}ter, Miriam and Skutella, Martin},
    title = {Fast and Memory-Efficient Algorithms for Evacuation Problems},
    booktitle = {SODA 2017 – Proc. 28th ACM-SIAM Symposium on Discrete Algorithms},
    pages = {821--840},
    year = {2017},
    doi = {10.1137/1.9781611974782.52},
    }
  • Towards a robust and wide-area traffic signal control for inner-city areas ( and )
    2017 5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), pp. 804–809.
    [url] DOI Bibtex
    @inproceedings{ThunigNagel2017BackPressureSignals,
    author = {Theresa Thunig and Kai Nagel},
    title = {Towards a robust and wide-area traffic signal control for inner-city areas},
    booktitle = {2017 5th {IEEE} International Conference on Models and Technologies for Intelligent Transportation Systems ({MT}-{ITS})},
    year = {2017},
    pages = {804--809},
    doi = {10.1109/mtits.2017.8005622},
    url = {https://ieeexplore.ieee.org/document/8005622},
    }
  • Unrelated Machine Scheduling with Stochastic Processing Times (, and )
    Math. Oper. Res., 41(3):851–864, .
    Extended abstract appeared in Proc. of STACS 2014
    DOI Bibtex
    @article{SkutellaSviridenkoUetz2016,
    author = {Skutella, Martin and Sviridenko, Maxim and Uetz, Marc},
    journal = {Math. Oper. Res.},
    pages = {851--864},
    title = {Unrelated Machine Scheduling with Stochastic Processing Times},
    volume = {41},
    number = {3},
    doi = {10.1287/moor.2015.0757},
    year = {2016},
    }
  • Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures ( and )
    Math. Oper. Res., 41(3):991–1021, .
    DOI Bibtex
    @article{SkutellaVerschae2016,
    author = {Skutella, Martin and Verschae, José},
    title = {Robust Polynomial-Time Approximation Schemes for Parallel Machine
    Scheduling with Job Arrivals and Departures},
    journal = {Math. Oper. Res.},
    volume = {41},
    number = {3},
    pages = {991--1021},
    year = {2016},
    doi = {10.1287/moor.2015.0765},
    }
  • The Power of Recourse for Online MST and TSP (, , and )
    SIAM J. Comput., 45(3):859–880, .
    Extended abstract appeared in Proc. of ICALP 2012
    DOI Bibtex
    @article{MegowSkutellaVerschae+2016,
    author = {Megow, Nicole and Skutella, Martin and Verschae, José and Wiese, Andreas},
    title = {The Power of Recourse for Online {MST} and {TSP}},
    journal = {SIAM J. Comput.},
    volume = {45},
    number = {3},
    pages = {859--880},
    year = {2016},
    doi = {10.1137/130917703},
    }
  • A Note on the Ring Loading Problem ()
    SIAM J. Discret. Math., 30(1):327–342, .
    Extended abstract appeared in Proc. of SODA 2015
    DOI Bibtex
    @article{Skutella2016a,
    author = {Skutella, Martin},
    title = {A Note on the Ring Loading Problem},
    journal = {SIAM J. Discret. Math.},
    volume = {30},
    number = {1},
    pages = {327--342},
    year = {2016},
    doi = {10.1137/14099588X},
    }
  • A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ()
    Oper. Res. Lett., 44(5):676–679, .
    DOI Bibtex
    @article{Skutella2016,
    author = {Skutella, Martin},
    title = {A 2.542-approximation for precedence constrained single machine scheduling
    with release dates and total weighted completion time objective},
    journal = {Oper. Res. Lett.},
    volume = {44},
    number = {5},
    pages = {676--679},
    year = {2016},
    doi = {10.1016/j.orl.2016.07.016},
    }
  • Braess's paradox in an agent-based transport model ( and )
    Procedia Computer Science, 83:946–951, .
    [url] DOI Bibtex
    @article{ThunigNagel2016BraessMATSim,
    author = {Theresa Thunig and Kai Nagel},
    title = {Braess's paradox in an agent-based transport model},
    journal = {Procedia Computer Science},
    year = {2016},
    volume = {83},
    pages = {946--951},
    doi = {10.1016/j.procs.2016.04.190},
    url = {http://www.sciencedirect.com/science/article/pii/S187705091630223X},
    }
  • PolySCIP (, , and )
    ICMS 2016 – Proc. 5th International Congress on Mathematical Software, pp. 259–264.
    DOI Bibtex
    @inproceedings{BorndoerferSchenkerSkutella+2016,
    author = {Borndörfer, Ralf and Schenker, Sebastian and Skutella, Martin and Strunk, Timo},
    title = {PolySCIP},
    booktitle = {ICMS 2016 – Proc. 5th International Congress on Mathematical Software},
    pages = {259--264},
    year = {2016},
    doi = {10.1007/978-3-319-42432-3\_32},
    }
  • IPCO 2016 – Proc. 18th Conference on Integer Programming and Combinatorial Optimization (Quentin Louveaux, Martin Skutella, eds.), .
    DOI Bibtex
    @proceedings{LouveauxSkutella2016,
    editor = {Louveaux, Quentin and Skutella, Martin},
    series = {Lecture Notes in Computer Science},
    title = {IPCO 2016 – Proc. 18th Conference on Integer Programming and Combinatorial Optimization},
    doi = {10.1007/978-3-319-33461-5},
    year = {2016},
    }
  • Complexity and Algorithms in Matching Problems Under Preferences ()
    PhD thesis, TU Berlin, .
    [pdf] Bibtex
    @phdthesis{ThesisCseh2016,
    title = {Complexity and Algorithms in Matching Problems Under Preferences},
    author = {Cseh, Ágnes},
    year = {2016},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    url = {https://www.coga.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/theses/ThesisCseh2016.pdf},
    }
  • An incremental algorithm for the uncapacitated facility location problem (, and )
    Networks, 65(4):306–311, .
    DOI Bibtex
    @article{ArulselvanMaurerSkutella2015,
    author = {Arulselvan, Ashwin and Maurer, Olaf and Skutella, Martin},
    title = {An incremental algorithm for the uncapacitated facility location problem},
    journal = {Networks},
    volume = {65},
    number = {4},
    pages = {306--311},
    year = {2015},
    doi = {10.1002/net.21595},
    }
  • A tight bound on the speed-up through storage for quickest multi-commodity flows ( and )
    Oper. Res. Lett., 43(1):93–95, .
    DOI Bibtex
    @article{GrossSkutella2015,
    author = {Gro{\ss}, Martin and Skutella, Martin},
    title = {A tight bound on the speed-up through storage for quickest multi-commodity
    flows},
    journal = {Oper. Res. Lett.},
    volume = {43},
    number = {1},
    pages = {93--95},
    year = {2015},
    doi = {10.1016/j.orl.2014.12.008},
    }
  • Graph orientation and flows over time (, and )
    Networks, 66(3):196–209, .
    Extended abstract appeared in Proc. of ISAAC 2014
    DOI Bibtex
    @article{ArulselvanGrossSkutella2015,
    author = {Arulselvan, Ashwin and Gro{\ss}, Martin and Skutella, Martin},
    title = {Graph orientation and flows over time},
    journal = {Networks},
    volume = {66},
    number = {3},
    pages = {196--209},
    year = {2015},
    doi = {10.1002/net.21623},
    }
  • A note on the ring loading problem ()
    SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 37–46.
    Full paper appeared in SIAM J. Discret. Math. 2016
    DOI Bibtex
    @inproceedings{Skutella2015,
    author = {Skutella, Martin},
    title = {A note on the ring loading problem},
    booktitle = {SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms},
    pages = {37--46},
    year = {2015},
    doi = {10.1137/1.9781611973730.4},
    }
  • The Simplex Algorithm is NP-Mighty ( and )
    SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 858–872.
    Full paper appeared in ACM Trans. Algorithms 2019
    DOI Bibtex
    @inproceedings{DisserSkutella2015,
    author = {Disser, Yann and Skutella, Martin},
    title = {The Simplex Algorithm is NP-Mighty},
    booktitle = {SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms},
    pages = {858--872},
    year = {2015},
    doi = {10.1137/1.9781611973730.59},
    }
  • Robust randomized matchings (, and )
    SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 1904–1915.
    Full paper appeared in SIAM J. Comput. 2018
    DOI Bibtex
    @inproceedings{MatuschkeSkutellaSoto2015,
    author = {Matuschke, Jannik and Skutella, Martin and Soto, José A.},
    title = {Robust randomized matchings},
    booktitle = {SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms},
    pages = {1904--1915},
    year = {2015},
    doi = {10.1137/1.9781611973730.127},
    }
  • Node-Balancing by Edge-Increments (, , and )
    ESA 2015 – Proc. 23rd European Symposium on Algorithms, pp. 450–458.
    DOI Bibtex
    @inproceedings{EisenbrandMoranPinchasi+2015,
    author = {Eisenbrand, Friedrich and Moran, Shay and Pinchasi, Rom and Skutella, Martin},
    title = {Node-Balancing by Edge-Increments},
    booktitle = {ESA 2015 – Proc. 23rd European Symposium on Algorithms},
    pages = {450--458},
    year = {2015},
    doi = {10.1007/978-3-662-48350-3\_38},
    }
  • Randomization Helps Computing a Minimum Spanning Tree under Uncertainty (, and )
    ESA 2015 – Proc. 23rd European Symposium on Algorithms, pp. 878–890.
    Full paper appeared in SIAM J. Comput. 2017
    DOI Bibtex
    @inproceedings{MegowMeissnerSkutella2015,
    author = {Megow, Nicole and Mei{\ss}ner, Julie and Skutella, Martin},
    title = {Randomization Helps Computing a Minimum Spanning Tree under Uncertainty},
    booktitle = {ESA 2015 – Proc. 23rd European Symposium on Algorithms},
    pages = {878--890},
    year = {2015},
    doi = {10.1007/978-3-662-48350-3\_73},
    }
  • Convex Quadratic Programming in Scheduling ()
    Chapter in Gems of Combinatorial Optimization and Graph Algorithms, .
    DOI Bibtex
    @incollection{Skutella2015a,
    author = {Skutella, Martin},
    title = {Convex Quadratic Programming in Scheduling},
    booktitle = {Gems of Combinatorial Optimization and Graph Algorithms},
    pages = {125--132},
    year = {2015},
    doi = {10.1007/978-3-319-24971-1\_12},
    }
  • WAOA 2015 – Proc. 13th Workshop on Approximation and Online Algorithms (Laura Sanità, Martin Skutella, eds.), .
    DOI Bibtex
    @proceedings{SanitaSkutella2015,
    editor = {Sanit{\`{a}}, Laura and Skutella, Martin},
    title = {WAOA 2015 – Proc. 13th Workshop on Approximation and Online Algorithms},
    year = {2015},
    doi = {10.1007/978-3-319-28684-6},
    }
  • Gems of Combinatorial Optimization and Graph Algorithms (Andreas S. Schulz, Martin Skutella, Sebastian Stiller, Dorothea Wagner, eds.), .
    DOI Bibtex
    @proceedings{SchulzSkutellaStiller+2015,
    editor = {Schulz, Andreas S. and Skutella, Martin and Stiller, Sebastian and Wagner, Dorothea},
    title = {Gems of Combinatorial Optimization and Graph Algorithms},
    year = {2015},
    doi = {10.1007/978-3-319-24971-1},
    }
  • Network Design with Facility Location ()
    PhD thesis, TU Berlin, .
    [pdf] Bibtex
    @phdthesis{ThesisRezapour2015,
    title = {Network Design with Facility Location},
    author = {Rezapour, Mohsen},
    year = {2015},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    url = {https://www.coga.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/theses/ThesisRezapour2015.pdf},
    }
  • Generalizations of Flows over Time with Applications in Evacuation Optimization ()
    PhD thesis, TU Berlin, .
    [pdf] Bibtex
    @phdthesis{ThesisKappmeier2015,
    title = {Generalizations of Flows over Time with Applications in Evacuation Optimization},
    author = {Kappmeier, Jan-Philipp},
    year = {2015},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    url = {https://www.coga.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/theses/ThesisKappmeier2015.pdf},
    }
  • Earliest arrival flows in networks with multiple sinks ( and )
    Discret. Appl. Math., 164:320–327, .
    DOI Bibtex
    @article{SchmidtSkutella2014,
    author = {Schmidt, Melanie and Skutella, Martin},
    title = {Earliest arrival flows in networks with multiple sinks},
    journal = {Discret. Appl. Math.},
    volume = {164},
    pages = {320--327},
    year = {2014},
    doi = {10.1016/j.dam.2011.09.023},
    }
  • Stochastic Scheduling on Unrelated Machines (, and )
    STACS 2014 – Proc. 31st International Symposium on Theoretical Aspects of Computer Science, pp. 639–650.
    Full paper appeared in Math. Oper. Res. 2016
    DOI Bibtex
    @inproceedings{SkutellaSviridenkoUetz2014,
    author = {Skutella, Martin and Sviridenko, Maxim and Uetz, Marc},
    title = {Stochastic Scheduling on Unrelated Machines},
    booktitle = {STACS 2014 – Proc. 31st International Symposium on Theoretical Aspects of Computer Science},
    pages = {639--650},
    year = {2014},
    doi = {10.4230/LIPIcs.STACS.2014.639},
    }
  • Paths to Stable Allocations ( and )
    SAGT 2014 – Proc. 7th International Symposium on Algorithmic Game Theory, pp. 61–73.
    Full paper appeared in Int. J. Game Theory 2019
    DOI Bibtex
    @inproceedings{CsehSkutella2014,
    author = {Cseh, {\'{A}}gnes and Skutella, Martin},
    title = {Paths to Stable Allocations},
    booktitle = {SAGT 2014 – Proc. 7th International Symposium on Algorithmic Game Theory},
    pages = {61--73},
    year = {2014},
    doi = {10.1007/978-3-662-44803-8\_6},
    }
  • Graph Orientation and Flows over Time (, and )
    ISAAC 2014 – Proc. 25th International Symposium on Algorithms and Computation, pp. 741–752.
    Full paper appeared in Networks 2015
    DOI Bibtex
    @inproceedings{ArulselvanGrossSkutella2014,
    author = {Arulselvan, Ashwin and Gro{\ss}, Martin and Skutella, Martin},
    title = {Graph Orientation and Flows over Time},
    booktitle = {ISAAC 2014 – Proc. 25th International Symposium on Algorithms and Computation},
    pages = {741--752},
    year = {2014},
    doi = {10.1007/978-3-319-13075-0\_58},
    }
  • Approximation Algorithms for Complex Network Flow Over Time Problems ()
    PhD thesis, TU Berlin, .
    [pdf] Bibtex
    @phdthesis{ThesisGross2014,
    title = {Approximation Algorithms for Complex Network Flow Over Time Problems},
    author = {Gro\ss, Martin},
    year = {2014},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    url = {https://www.coga.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/theses/ThesisGross2014.pdf},
    }
  • Robot Tour Planning with High Determination Costs ()
    PhD thesis, TU Berlin, .
    [pdf] Bibtex
    @phdthesis{ThesisWelz2014,
    title = {Robot Tour Planning with High Determination Costs},
    author = {Welz, Wolfgang},
    year = {2014},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    url = {https://www.coga.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/theses/ThesisWelz2014.pdf},
    projectname = {MI1},
    }
  • Stable Flows over Time (, and )
    Algorithms, 6(3):532–545, .
    DOI Bibtex
    @article{CsehMatuschkeSkutella2013,
    author = {Cseh, {\'{A}}gnes and Matuschke, Jannik and Skutella, Martin},
    title = {Stable Flows over Time},
    journal = {Algorithms},
    volume = {6},
    number = {3},
    pages = {532--545},
    year = {2013},
    doi = {10.3390/a6030532},
    }
  • Task assignment, sequencing and path-planning in robotic welding cells (, , , and )
    MMAR 2013 – Proc. 18th International Conference on Methods and Models in Automation and Robotics, pp. 252–257.
    DOI Bibtex
    @inproceedings{LandryHenrionHoemberg+2013,
    author = {Landry, Chantal and Henrion, Ren{\'{e}} and H{\"{o}}mberg, Dietmar and Skutella, Martin and Welz, Wolfgang},
    title = {Task assignment, sequencing and path-planning in robotic welding cells},
    booktitle = {MMAR 2013 – Proc. 18th International Conference on Methods and Models in Automation and Robotics},
    pages = {252--257},
    year = {2013},
    doi = {10.1109/MMAR.2013.6669915},
    }
  • Algorithms and Linear Programming Relaxations for Scheduling Unrelated Parallel Machines ()
    SEA 2013 – Proc. 12th International Symposium on Experimental Algorithms, pp. 1–3.
    DOI Bibtex
    @inproceedings{Skutella2013,
    author = {Skutella, Martin},
    title = {Algorithms and Linear Programming Relaxations for Scheduling Unrelated
    Parallel Machines},
    booktitle = {SEA 2013 – Proc. 12th International Symposium on Experimental Algorithms},
    pages = {1--3},
    year = {2013},
    doi = {10.1007/978-3-642-38527-8\_1},
    }
  • Network Flows and Network Design in Theory and Practice ()
    PhD thesis, TU Berlin, .
    [pdf] Bibtex
    @phdthesis{ThesisMatuschke2013,
    title = {Network Flows and Network Design in Theory and Practice},
    author = {Matuschke, Jannik},
    year = {2013},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    url = {https://www.coga.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/theses/ThesisMatuschke2013.pdf},
    }
  • Benefits of Sexual Reproduction in Evolutionary Computation ()
    PhD thesis, TU Berlin, .
    [pdf] Bibtex
    @phdthesis{ThesisFriedrich2013,
    title = {Benefits of Sexual Reproduction in Evolutionary Computation},
    author = {Friedrich, Madeleine},
    year = {2013},
    month = {Juni},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    url = {https://www.coga.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/theses/ThesisFriedrich2013.pdf},
    }
  • The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders (, and )
    Math. Oper. Res., 37(2):379–398, .
    Extended abstract appeared in Proc. of APPROX 2009
    DOI Bibtex
    @article{CorreaSkutellaVerschae2012,
    author = {Correa, José R. and Skutella, Martin and Verschae, José},
    title = {The Power of Preemption on Unrelated Machines and Applications to
    Scheduling Orders},
    journal = {Math. Oper. Res.},
    volume = {37},
    number = {2},
    pages = {379--398},
    year = {2012},
    doi = {10.1287/moor.1110.0520},
    }
  • Universal Sequencing on an Unreliable Machine (, , , , , and )
    SIAM J. Comput., 41(3):565–586, .
    Extended abstract appeared in Proc. of IPCO 2010
    DOI Bibtex
    @article{EpsteinLevinMarchetti-Spaccamela+2012,
    author = {Epstein, Leah and Levin, Asaf and Marchetti{-}Spaccamela, Alberto and Megow, Nicole and Mestre, Juli{\'{a}}n and Skutella, Martin and Stougie, Leen},
    title = {Universal Sequencing on an Unreliable Machine},
    journal = {SIAM J. Comput.},
    volume = {41},
    number = {3},
    pages = {565--586},
    year = {2012},
    doi = {10.1137/110844210},
    }
  • The Power of Recourse for Online MST and TSP (, , and )
    ICALP 2012 – Proc. 39th International Colloquium on Automata, Languages and Programming, pp. 689–700.
    Full paper appeared in SIAM J. Comput. 2016
    DOI Bibtex
    @inproceedings{MegowSkutellaVerschae+2012,
    author = {Megow, Nicole and Skutella, Martin and Verschae, José and Wiese, Andreas},
    title = {The Power of Recourse for Online {MST} and {TSP}},
    booktitle = {ICALP 2012 – Proc. 39th International Colloquium on Automata, Languages and Programming},
    pages = {689--700},
    year = {2012},
    doi = {10.1007/978-3-642-31594-7\_58},
    }
  • Maximum Multicommodity Flows over Time without Intermediate Storage ( and )
    ESA 2012 – Proc. 20th European Symposium on Algorithms, pp. 539–550.
    DOI Bibtex
    @inproceedings{GrossSkutella2012,
    author = {Gro{\ss}, Martin and Skutella, Martin},
    title = {Maximum Multicommodity Flows over Time without Intermediate Storage},
    booktitle = {ESA 2012 – Proc. 20th European Symposium on Algorithms},
    pages = {539--550},
    year = {2012},
    doi = {10.1007/978-3-642-33090-2\_47},
    }
  • Flows over Time with Negative Transit Times and Arc Release Dates (, , , and )
    CTW 2012 – Proc. 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 30–33.
    Bibtex
    @inproceedings{BosioKappmeierMatuschke+2012,
    author = {Bosio, Sandro and
    Kappmeier, Jan{-}Philipp W. and
    Matuschke, Jannik and
    Peis, Britta and
    Skutella, Martin},
    title = {Flows over Time with Negative Transit Times and Arc Release Dates},
    booktitle = {CTW 2012 – Proc. 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization},
    pages = {30--33},
    year = {2012},
    }
  • Network Flow Problems Arising From Evacuation Planning ()
    PhD thesis, TU Berlin, .
    [pdf] Bibtex
    @phdthesis{ThesisDressler2012,
    title = {Network Flow Problems Arising From Evacuation Planning},
    author = {Dressler, Daniel},
    year = {2012},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    url = {https://www.coga.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/theses/ThesisDressler2012.pdf},
    }
  • Routing Games over Time ()
    PhD thesis, TU Berlin, .
    [pdf] Bibtex
    @phdthesis{ThesisKoch2012,
    title = {Routing Games over Time},
    author = {Koch, Ronald},
    year = {2012},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    url = {https://www.coga.tu-berlin.de/fileadmin/i26/download/AG_DiskAlg/FG_KombOptGraphAlg/theses/ThesisKoch2012.pdf},
    }
  • The Power of Recourse in Online Optimization ()
    PhD thesis, TU Berlin, .
    Bibtex
    @phdthesis{ThesisVerschae2012,
    title = {The Power of Recourse in Online Optimization},
    author = {Verschae, José},
    year = {2012},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    }
  • Computing Minimum Cuts by Randomized Search Heuristics (, and )
    Algorithmica, 59(3):323–342, .
    Extended abstract appeared in Proc. of GECCO 2008
    DOI Bibtex
    @article{NeumannReichelSkutella2011,
    author = {Neumann, Frank and Reichel, Joachim and Skutella, Martin},
    title = {Computing Minimum Cuts by Randomized Search Heuristics},
    journal = {Algorithmica},
    volume = {59},
    number = {3},
    pages = {323--342},
    year = {2011},
    doi = {10.1007/s00453-009-9370-8},
    }
  • Continuous and discrete flows over time - A general model based on measure theory (, and )
    Math. Methods Oper. Res., 73(3):301–337, .
    DOI Bibtex
    @article{KochNasrabadiSkutella2011,
    author = {Koch, Ronald and Nasrabadi, Ebrahim and Skutella, Martin},
    title = {Continuous and discrete flows over time - {A} general model based
    on measure theory},
    journal = {Math. Methods Oper. Res.},
    volume = {73},
    number = {3},
    pages = {301--337},
    year = {2011},
    doi = {10.1007/s00186-011-0357-2},
    }
  • A note on the generalized min-sum set cover problem ( and )
    Oper. Res. Lett., 39(6):433–436, .
    DOI Bibtex
    @article{SkutellaWilliamson2011,
    author = {Skutella, Martin and Williamson, David P.},
    title = {A note on the generalized min-sum set cover problem},
    journal = {Oper. Res. Lett.},
    volume = {39},
    number = {6},
    pages = {433--436},
    year = {2011},
    doi = {10.1016/j.orl.2011.08.002},
    }
  • Nash Equilibria and the Price of Anarchy for Flows over Time ( and )
    Theory Comput. Syst., 49(1):71–97, .
    Extended abstract appeared in Proc. of SAGT 2009
    DOI Bibtex
    @article{KochSkutella2011,
    author = {Koch, Ronald and Skutella, Martin},
    title = {Nash Equilibria and the Price of Anarchy for Flows over Time},
    journal = {Theory Comput. Syst.},
    volume = {49},
    number = {1},
    pages = {71--97},
    year = {2011},
    doi = {10.1007/s00224-010-9299-y},
    }
  • Real-time Avionics Optimization (, , , and )
    it – Inf. Technol., 53(6):274–279, .
    DOI Bibtex
    @article{EisenbrandNiemeierSkutella+2011,
    author = {Eisenbrand, Friedrich and Niemeier, Martin and Skutella, Martin and Verschae, Jos{\'{e}} and Wiese, Andreas},
    title = {Real-time Avionics Optimization},
    journal = {it -- Inf. Technol.},
    volume = {53},
    number = {6},
    pages = {274--279},
    year = {2011},
    doi = {10.1524/itit.2011.0653},
    }
  • Generalized Maximum Flows over Time ( and )
    WAOA 2011 – Proc. 9th Workshop on Approximation and Online Algorithms, pp. 247–260.
    DOI Bibtex
    @inproceedings{GrossSkutella2011,
    author = {Gro{\ss}, Martin and Skutella, Martin},
    title = {Generalized Maximum Flows over Time},
    booktitle = {WAOA 2011 – Proc. 9th Workshop on Approximation and Online Algorithms},
    pages = {247--260},
    year = {2011},
    doi = {10.1007/978-3-642-29116-6\_21},
    }
  • Minimum Spanning Trees – Sometimes Greed Pays Off ( and )
    Chapter in Algorithms Unplugged, .
    DOI Bibtex
    @incollection{SkutellaSkutella2011,
    author = {Skutella, Katharina and Skutella, Martin},
    title = {Minimum Spanning Trees -- Sometimes Greed Pays Off},
    booktitle = {Algorithms Unplugged},
    pages = {325--331},
    year = {2011},
    doi = {10.1007/978-3-642-15328-0\_33},
    }
  • Packet Routing and Scheduling ()
    PhD thesis, TU Berlin, .
    Bibtex
    @phdthesis{ThesisWiese2011,
    title = {Packet Routing and Scheduling},
    author = {Wiese, Andreas},
    year = {2011},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    }
  • On the dominant of the $s$-$t$-cut polytope: Vertices, facets, and adjacency ( and )
    Math. Program., 124(1-2):441–454, .
    DOI Bibtex
    @article{SkutellaWeber2010,
    author = {Skutella, Martin and Weber, Alexia},
    title = {On the dominant of the $s$-$t$-cut polytope: Vertices, facets,
    and adjacency},
    journal = {Math. Program.},
    volume = {124},
    number = {1-2},
    pages = {441--454},
    year = {2010},
    doi = {10.1007/s10107-010-0373-7},
    }
  • Length-bounded cuts and flows (, , , , , , and )
    ACM Trans. Algorithms, 7(1):4:1–4:27, .
    Extended abstract appeared in Proc. of ICALP 2006
    DOI Bibtex
    @article{BaierErlebachHall+2010,
    author = {Baier, Georg and Erlebach, Thomas and Hall, Alexander and K{\"{o}}hler, Ekkehard and Kolman, Petr and Pangr{\'{a}}c, Ondrej and Schilling, Heiko and Skutella, Martin},
    title = {Length-bounded cuts and flows},
    journal = {ACM Trans. Algorithms},
    volume = {7},
    number = {1},
    pages = {4:1--4:27},
    year = {2010},
    doi = {10.1145/1868237.1868241},
    }
  • Evolutionary Algorithms and Matroid Optimization Problems ( and )
    Algorithmica, 57(1):187–206, .
    Extended abstract appeared in Proc. of GECCO 2007
    DOI Bibtex
    @article{ReichelSkutella2010,
    author = {Reichel, Joachim and Skutella, Martin},
    title = {Evolutionary Algorithms and Matroid Optimization Problems},
    journal = {Algorithmica},
    volume = {57},
    number = {1},
    pages = {187--206},
    year = {2010},
    doi = {10.1007/s00453-008-9253-4},
    }
  • Earliest Arrival Flows in Networks with Multiple Sinks ( and )
    Electron. Notes Discret. Math., 36:607–614, .
    DOI Bibtex
    @article{SchmidtSkutella2010,
    author = {Schmidt, Melanie and Skutella, Martin},
    title = {Earliest Arrival Flows in Networks with Multiple Sinks},
    journal = {Electron. Notes Discret. Math.},
    volume = {36},
    pages = {607--614},
    year = {2010},
    doi = {10.1016/j.endm.2010.05.077},
    }
  • Universal Sequencing on a Single Machine (, , , , , and )
    IPCO 2010 – Proc. 14th Conference on Integer Programming and Combinatorial Optimization, pp. 230–243.
    Full paper appeared in SIAM J. Comput. 2012
    DOI Bibtex
    @inproceedings{EpsteinLevinMarchetti-Spaccamela+2010,
    author = {Epstein, Leah and Levin, Asaf and Marchetti{-}Spaccamela, Alberto and Megow, Nicole and Mestre, Juli{\'{a}}n and Skutella, Martin and Stougie, Leen},
    title = {Universal Sequencing on a Single Machine},
    booktitle = {IPCO 2010 – Proc. 14th Conference on Integer Programming and Combinatorial Optimization},
    pages = {230--243},
    year = {2010},
    doi = {10.1007/978-3-642-13036-6\_18},
    }
  • Scheduling Periodic Tasks in a Hard Real-Time Environment (, , , , and )
    ICALP 2010 – Proc. 37th International Colloquium on Automata, Languages and Programming, pp. 299–311.
    DOI Bibtex
    @inproceedings{EisenbrandHaehnleNiemeier+2010,
    author = {Eisenbrand, Friedrich and H{\"{a}}hnle, Nicolai and Niemeier, Martin and Skutella, Martin and Verschae, Jos{\'{e}} and Wiese, Andreas},
    title = {Scheduling Periodic Tasks in a Hard Real-Time Environment},
    booktitle = {ICALP 2010 – Proc. 37th International Colloquium on Automata, Languages and Programming},
    pages = {299--311},
    year = {2010},
    doi = {10.1007/978-3-642-14165-2\_26},
    }
  • A Robust PTAS for Machine Covering and Packing ( and )
    ESA 2010 – Proc. 18th European Symposium on Algorithms, pp. 36–47.
    DOI Bibtex
    @inproceedings{SkutellaVerschae2010,
    author = {Skutella, Martin and Verschae, José},
    title = {A Robust {PTAS} for Machine Covering and Packing},
    booktitle = {ESA 2010 – Proc. 18th European Symposium on Algorithms},
    pages = {36--47},
    year = {2010},
    doi = {10.1007/978-3-642-15775-2\_4},
    }
  • Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods (, , , , , , and )
    ESA 2010 – Proc. 18th European Symposium on Algorithms, pp. 11–22.
    DOI Bibtex
    @inproceedings{EisenbrandKesavanMattikalli+2010,
    author = {Eisenbrand, Friedrich and Kesavan, Karthikeyan and Mattikalli, Raju S. and Niemeier, Martin and Nordsieck, Arnold W. and Skutella, Martin and Verschae, Jos{\'{e}} and Wiese, Andreas},
    title = {Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods},
    booktitle = {ESA 2010 – Proc. 18th European Symposium on Algorithms},
    pages = {11--22},
    year = {2010},
    doi = {10.1007/978-3-642-15775-2\_2},
    }
  • Packet Routing on the Grid (, and )
    LATIN 2010 – Proc. 9th Latin American Symposium on Theoretical Informatics, pp. 120–130.
    DOI Bibtex
    @inproceedings{PeisSkutellaWiese2010,
    author = {Peis, Britta and Skutella, Martin and Wiese, Andreas},
    title = {Packet Routing on the Grid},
    booktitle = {LATIN 2010 – Proc. 9th Latin American Symposium on Theoretical Informatics},
    pages = {120--130},
    year = {2010},
    doi = {10.1007/978-3-642-12200-2\_12},
    }
  • An FPTAS for Flows over Time with Aggregate Arc Capacities ( and )
    WAOA 2010 – Proc. 8th Workshop on Approximation and Online Algorithms, pp. 106–117.
    DOI Bibtex
    @inproceedings{DresslerSkutella2010,
    author = {Dressler, Daniel and Skutella, Martin},
    title = {An {FPTAS} for Flows over Time with Aggregate Arc Capacities},
    booktitle = {WAOA 2010 – Proc. 8th Workshop on Approximation and Online Algorithms},
    pages = {106--117},
    year = {2010},
    doi = {10.1007/978-3-642-18318-8\_10},
    }
  • Route Planning for Robot Systems ( and )
    OR 2010 – Proc. International Conference of the German Operations Research Society, pp. 307–312.
    DOI Bibtex
    @inproceedings{SkutellaWelz2010,
    author = {Skutella, Martin and Welz, Wolfgang},
    title = {Route Planning for Robot Systems},
    booktitle = {OR 2010 – Proc. International Conference of the German Operations Research Society},
    pages = {307--312},
    year = {2010},
    doi = {10.1007/978-3-642-20009-0\_49},
    }
  • Optimal Evacuation Solutions for Large-Scale Scenarios (, , , and )
    OR 2010 – Proc. International Conference of the German Operations Research Society.
    DOI Bibtex
    @inproceedings{DresslerFloetteroedLaemmel+2010,
    author = {Dressler, Daniel and Fl{\"{o}}tter{\"{o}}d, Gunnar and L{\"{a}}mmel, Gregor and Nagel, Kai and Skutella, Martin},
    title = {Optimal Evacuation Solutions for Large-Scale Scenarios},
    booktitle = {OR 2010 – Proc. International Conference of the German Operations Research Society},
    year = {2010},
    doi = {10.1007/978-3-642-20009-0\_38},
    }
  • Online Scheduling with Bounded Migration (, and )
    Math. Oper. Res., 34(2):481–498, .
    Extended abstract appeared in Proc. of ICALP 2004
    DOI Bibtex
    @article{SandersSivadasanSkutella2009,
    author = {Sanders, Peter and Sivadasan, Naveen and Skutella, Martin},
    title = {Online Scheduling with Bounded Migration},
    journal = {Math. Oper. Res.},
    volume = {34},
    number = {2},
    pages = {481--498},
    year = {2009},
    doi = {10.1287/moor.1090.0381},
    }
  • Earliest Arrival Flows with Multiple Sources ( and )
    Math. Oper. Res., 34(2):499–512, .
    Extended abstract appeared in Proc. of FOCS 2006
    DOI Bibtex
    @article{BaumannSkutella2009,
    author = {Baumann, Nadine and Skutella, Martin},
    title = {Earliest Arrival Flows with Multiple Sources},
    journal = {Math. Oper. Res.},
    volume = {34},
    number = {2},
    pages = {499--512},
    year = {2009},
    doi = {10.1287/moor.1090.0382},
    }
  • Latency-constrained aggregation in sensor networks (, , , , and )
    ACM Trans. Algorithms, 6(1):13:1–13:20, .
    Extended abstract appeared in Proc. of ESA 2006
    DOI Bibtex
    @article{BecchettiMarchetti-SpaccamelaVitaletti+2009,
    author = {Becchetti, Luca and Marchetti{-}Spaccamela, Alberto and Vitaletti, Andrea and Korteweg, Peter and Skutella, Martin and Stougie, Leen},
    title = {Latency-constrained aggregation in sensor networks},
    journal = {ACM Trans. Algorithms},
    volume = {6},
    number = {1},
    pages = {13:1--13:20},
    year = {2009},
    doi = {10.1145/1644015.1644028},
    }
  • Multiline Addressing by Network Flow (, , and )
    Algorithmica, 53(4):583–596, .
    DOI Bibtex
    @article{EisenbrandKarrenbauerSkutella+2009,
    author = {Eisenbrand, Friedrich and Karrenbauer, Andreas and Skutella, Martin and Xu, Chihao},
    title = {Multiline Addressing by Network Flow},
    journal = {Algorithmica},
    volume = {53},
    number = {4},
    pages = {583--596},
    year = {2009},
    doi = {10.1007/s00453-008-9252-5},
    }
  • Flows with unit path capacities and related packing and covering problems ( and )
    J. Comb. Optim., 18(3):272–293, .
    Extended abstract appeared in Proc. of COCOA 2008
    DOI Bibtex
    @article{MartensSkutella2009,
    author = {Martens, Maren and Skutella, Martin},
    title = {Flows with unit path capacities and related packing and covering problems},
    journal = {J. Comb. Optim.},
    volume = {18},
    number = {3},
    pages = {272--293},
    year = {2009},
    doi = {10.1007/s10878-009-9225-x},
    }
  • Single-source $k$-splittable min-cost flows ( and )
    Oper. Res. Lett., 37(2):71–74, .
    DOI Bibtex
    @article{SalazarSkutella2009,
    author = {Salazar, Fernanda and Skutella, Martin},
    title = {Single-source $k$-splittable min-cost flows},
    journal = {Oper. Res. Lett.},
    volume = {37},
    number = {2},
    pages = {71--74},
    year = {2009},
    doi = {10.1016/j.orl.2008.12.004},
    }
  • The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders (, and )
    APPROX 2009 – Proc. 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 84–97.
    Full paper appeared in Math. Oper. Res. 2012
    DOI Bibtex
    @inproceedings{CorreaSkutellaVerschae2009,
    author = {Correa, José R. and Skutella, Martin and Verschae, José},
    title = {The Power of Preemption on Unrelated Machines and Applications to
    Scheduling Orders},
    booktitle = {APPROX 2009 – Proc. 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems},
    pages = {84--97},
    year = {2009},
    doi = {10.1007/978-3-642-03685-9\_7},
    }
  • Real-Time Message Routing and Scheduling (, , and )
    APPROX 2009 – Proc. 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 217–230.
    DOI Bibtex
    @inproceedings{KochPeisSkutella+2009,
    author = {Koch, Ronald and Peis, Britta and Skutella, Martin and Wiese, Andreas},
    title = {Real-Time Message Routing and Scheduling},
    booktitle = {APPROX 2009 – Proc. 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems},
    pages = {217--230},
    year = {2009},
    doi = {10.1007/978-3-642-03685-9\_17},
    }
  • Nash Equilibria and the Price of Anarchy for Flows over Time ( and )
    SAGT 2009 – Proc. 2nd International Symposium on Algorithmic Game Theory, pp. 323–334.
    Full paper appeared in Theory Comput. Syst. 2011
    DOI Bibtex
    @inproceedings{KochSkutella2009,
    author = {Koch, Ronald and Skutella, Martin},
    title = {Nash Equilibria and the Price of Anarchy for Flows over Time},
    booktitle = {SAGT 2009 – Proc. 2nd International Symposium on Algorithmic Game Theory},
    pages = {323--334},
    year = {2009},
    doi = {10.1007/978-3-642-04645-2\_29},
    }
  • Packet Routing: Complexity and Algorithms (, and )
    WAOA 2009 – Proc. 7th Workshop on Approximation and Online Algorithms, pp. 217–228.
    DOI Bibtex
    @inproceedings{PeisSkutellaWiese2009,
    author = {Peis, Britta and Skutella, Martin and Wiese, Andreas},
    title = {Packet Routing: Complexity and Algorithms},
    booktitle = {WAOA 2009 – Proc. 7th Workshop on Approximation and Online Algorithms},
    pages = {217--228},
    year = {2009},
    doi = {10.1007/978-3-642-12450-1\_20},
    }
  • On the size of weights in randomized search heuristics ( and )
    FOGA 2009 – Proc. 10th ACM SIGEVO International Workshop on Foundations of Genetic Algorithms, pp. 21–28.
    DOI Bibtex
    @inproceedings{ReichelSkutella2009,
    author = {Reichel, Joachim and Skutella, Martin},
    title = {On the size of weights in randomized search heuristics},
    booktitle = {FOGA 2009 – Proc. 10th ACM SIGEVO International Workshop on Foundations of Genetic Algorithms},
    pages = {21--28},
    year = {2009},
    doi = {10.1145/1527125.1527130},
    }
  • Traffic Networks and Flows over Time (, and )
    Chapter in Algorithmics of Large and Complex Networks – Design, Analysis, and Simulation, .
    DOI Bibtex
    @incollection{KoehlerMoehringSkutella2009,
    author = {K{\"{o}}hler, Ekkehard and M{\"{o}}hring, Rolf H. and Skutella, Martin},
    title = {Traffic Networks and Flows over Time},
    booktitle = {Algorithmics of Large and Complex Networks -- Design, Analysis, and
    Simulation},
    pages = {166--196},
    year = {2009},
    doi = {10.1007/978-3-642-02094-0\_9},
    }
  • An Introduction to Network Flows Over Time ()
    Chapter in Research Trends in Combinatorial Optimization (W. Cook, L. Lovász, J. Vygen, eds.), Springer, .
    DOI Bibtex
    @incollection{Skutella2009,
    author = {Skutella, Martin},
    booktitle = {Research Trends in Combinatorial Optimization},
    editor = {Cook, W. and Lov{\'a}sz, L. and Vygen, J.},
    pages = {451--482},
    publisher = {Springer},
    title = {An Introduction to Network Flows Over Time},
    year = {2009},
    doi = {10.1007/978-3-540-76796-1_21},
    }
  • Dynamic Flows in Time-Varying Networks ()
    PhD thesis, TU Berlin / Amirkabir University of Technology, .
    Bibtex
    @phdthesis{ThesisNasrabadi2009,
    title = {Dynamic Flows in Time-Varying Networks},
    author = {Nasrabadi, Ebrahim},
    year = {2009},
    type = {Doctoral Thesis},
    school = {TU Berlin / Amirkabir University of Technology},
    }
  • A short proof of the VPN Tree Routing Conjecture on ring networks (, , and )
    Oper. Res. Lett., 36(3):361–365, .
    DOI Bibtex
    @article{GrandoniKaibelOriolo+2008,
    author = {Grandoni, Fabrizio and Kaibel, Volker and Oriolo, Gianpaolo and Skutella, Martin},
    title = {A short proof of the {VPN} Tree Routing Conjecture on ring networks},
    journal = {Oper. Res. Lett.},
    volume = {36},
    number = {3},
    pages = {361--365},
    year = {2008},
    doi = {10.1016/j.orl.2007.10.008},
    }
  • Maximum $k$-Splittable $s,t$-Flows (, and )
    Theory Comput. Syst., 43(1):56–66, .
    Extended abstract appeared in Proc. of WAOA 2005
    DOI Bibtex
    @article{KochSkutellaSpenke2008,
    author = {Koch, Ronald and Skutella, Martin and Spenke, Ines},
    title = {Maximum $k$-Splittable $s,t$-Flows},
    journal = {Theory Comput. Syst.},
    volume = {43},
    number = {1},
    pages = {56--66},
    year = {2008},
    doi = {10.1007/s00224-007-9068-8},
    }
  • Computing minimum cuts by randomized search heuristics (, and )
    GECCO 2008 – Proc. Genetic and Evolutionary Computation Conference, pp. 779–786.
    Full paper appeared in Algorithmica 2011
    DOI Bibtex
    @inproceedings{NeumannReichelSkutella2008,
    author = {Neumann, Frank and Reichel, Joachim and Skutella, Martin},
    title = {Computing minimum cuts by randomized search heuristics},
    booktitle = {GECCO 2008 – Proc. Genetic and Evolutionary Computation Conference},
    pages = {779--786},
    year = {2008},
    doi = {10.1145/1389095.1389250},
    }
  • Flows with unit path capacities and related packing and covering problems ( and )
    COCOA 2008 – Proc. 2nd International Conference on Combinatorial Optimization and Applications, pp. 180–189.
    Full paper appeared in J. Comb. Optim. 2009
    DOI Bibtex
    @inproceedings{MartensSkutella2008,
    author = {Martens, Maren and Skutella, Martin},
    title = {Flows with unit path capacities and related packing and covering problems},
    booktitle = {COCOA 2008 – Proc. 2nd International Conference on Combinatorial Optimization and Applications},
    pages = {180--189},
    year = {2008},
    doi = {10.1007/978-3-540-85097-7\_17},
    }
  • Minimale aufspannende Bäume – Wenn das Naheliegende das Beste ist... ( and )
    Chapter in Taschenbuch der Algorithmen, .
    DOI Bibtex
    @incollection{SkutellaSkutella2008,
    author = {Skutella, Katharina and Skutella, Martin},
    title = {Minimale aufspannende B{\"{a}}ume -- Wenn das Naheliegende das
    Beste ist...},
    booktitle = {Taschenbuch der Algorithmen},
    pages = {353--360},
    year = {2008},
    doi = {10.1007/978-3-540-76394-9\_35},
    }
  • An Introduction to Network Flows over Time ()
    Chapter in Research Trends in Combinatorial Optimization, Bonn Workshop on Combinatorial Optimization, November 3-7, 2008, Bonn, Germany, .
    DOI Bibtex
    @incollection{Skutella2008,
    author = {Skutella, Martin},
    title = {An Introduction to Network Flows over Time},
    booktitle = {Research Trends in Combinatorial Optimization, Bonn Workshop on Combinatorial
    Optimization, November 3-7, 2008, Bonn, Germany},
    pages = {451--482},
    year = {2008},
    doi = {10.1007/978-3-540-76796-1\_21},
    }
  • WAOA 2008 – Proc. 6th Workshop on Approximation and Online Algorithms (Evripidis Bampis, Martin Skutella, eds.), .
    DOI Bibtex
    @proceedings{BampisSkutella2008,
    editor = {Bampis, Evripidis and Skutella, Martin},
    title = {WAOA 2008 – Proc. 6th Workshop on Approximation and Online Algorithms},
    year = {2008},
    doi = {10.1007/978-3-540-93980-1},
    isbn = {978-3-540-93979-5},
    }
  • New Approaches for Virtual Private Network Design (, , and )
    SIAM J. Comput., 37(3):706–721, .
    Extended abstract appeared in Proc. of ICALP 2005
    DOI Bibtex
    @article{EisenbrandGrandoniOriolo+2007,
    author = {Eisenbrand, Friedrich and Grandoni, Fabrizio and Oriolo, Gianpaolo and Skutella, Martin},
    title = {New Approaches for Virtual Private Network Design},
    journal = {SIAM J. Comput.},
    volume = {37},
    number = {3},
    pages = {706--721},
    year = {2007},
    doi = {10.1137/060654827},
    }
  • Quickest Flows Over Time ( and )
    SIAM J. Comput., 36(6):1600–1630, .
    Extended abstracts of different parts appeared in Proc. of IPCO 2002 and SODA 2003
    DOI Bibtex
    @article{FleischerSkutella2007,
    author = {Fleischer, Lisa and Skutella, Martin},
    title = {Quickest Flows Over Time},
    journal = {SIAM J. Comput.},
    volume = {36},
    number = {6},
    pages = {1600--1630},
    year = {2007},
    doi = {10.1137/S0097539703427215},
    }
  • An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times (, and )
    Algorithmica, 47(3):299–321, .
    Extended abstract appeared in Proc. of APPROX 2003
    DOI Bibtex
    @article{HallLangkauSkutella2007,
    author = {Hall, Alexander and Langkau, Katharina and Skutella, Martin},
    title = {An {FPTAS} for Quickest Multicommodity Flows with Inflow-Dependent
    Transit Times},
    journal = {Algorithmica},
    volume = {47},
    number = {3},
    pages = {299--321},
    year = {2007},
    doi = {10.1007/s00453-006-0196-3},
    }
  • Multicommodity flows over time: Efficient algorithms and complexity (, and )
    Theor. Comput. Sci., 379(3):387–404, .
    Extended abstract appeared in Proc. of ICALP 2003
    DOI Bibtex
    @article{HallHipplerSkutella2007,
    author = {Hall, Alexander and Hippler, Steffen and Skutella, Martin},
    title = {Multicommodity flows over time: Efficient algorithms and complexity},
    journal = {Theor. Comput. Sci.},
    volume = {379},
    number = {3},
    pages = {387--404},
    year = {2007},
    doi = {10.1016/j.tcs.2007.02.046},
    }
  • Convex Combinations of Single Source Unsplittable Flows (, and )
    ESA 2007 – Proc. 15th European Symposium on Algorithms, pp. 395–406.
    DOI Bibtex
    @inproceedings{MartensSalazarSkutella2007,
    author = {Martens, Maren and Salazar, Fernanda and Skutella, Martin},
    title = {Convex Combinations of Single Source Unsplittable Flows},
    booktitle = {ESA 2007 – Proc. 15th European Symposium on Algorithms},
    pages = {395--406},
    year = {2007},
    doi = {10.1007/978-3-540-75520-3\_36},
    }
  • WAOA 2007 – Proc. 5th Workshop on Approximation and Online Algorithms (Christos Kaklamanis, Martin Skutella, eds.), .
    DOI Bibtex
    @proceedings{KaklamanisSkutella2011,
    editor = {Kaklamanis, Christos and Skutella, Martin},
    series = {Lecture Notes in Computer Science},
    title = {WAOA 2007 – Proc. 5th Workshop on Approximation and Online Algorithms},
    doi = {10.1007/978-3-540-77918-6},
    year = {2007},
    }
  • Path-Constrained Network Flows ()
    PhD thesis, Universität Dortmund, .
    Bibtex
    @phdthesis{ThesisMartens07,
    author = {Martens, Maren},
    school = {Universität Dortmund},
    title = {Path-Constrained Network Flows},
    type = {Doctoral Thesis},
    year = {2007},
    }
  • Evacuation by Earliest Arrival Flows ()
    PhD thesis, Universität Dortmund, .
    Bibtex
    @phdthesis{ThesisBaumann07,
    author = {Baumann, Nadine},
    school = {Universität Dortmund},
    title = {Evacuation by Earliest Arrival Flows},
    type = {Doctoral Thesis},
    year = {2007},
    }
  • The Freeze-Tag Problem: How to Wake Up a Swarm of Robots (, , , and )
    Algorithmica, 46(2):193–221, .
    Extended abstract appeared in Proc. of SODA 2002
    DOI Bibtex
    @article{ArkinBenderFekete+2006,
    author = {Arkin, Esther M. and Bender, Michael A. and Fekete, S{\'{a}}ndor P. and Mitchell, Joseph S. B. and Skutella, Martin},
    title = {The Freeze-Tag Problem: How to Wake Up a Swarm of Robots},
    journal = {Algorithmica},
    volume = {46},
    number = {2},
    pages = {193--221},
    year = {2006},
    doi = {10.1007/s00453-006-1206-1},
    }
  • Flows on few paths: Algorithms and lower bounds ( and )
    Networks, 48(2):68–76, .
    Extended abstract appeared in Proc. of ESA 2004
    DOI Bibtex
    @article{MartensSkutella2006,
    author = {Martens, Maren and Skutella, Martin},
    title = {Flows on few paths: Algorithms and lower bounds},
    journal = {Networks},
    volume = {48},
    number = {2},
    pages = {68--76},
    year = {2006},
    doi = {10.1002/net.20121},
    }
  • Solving Evacuation Problems Efficiently–Earliest Arrival Flows with Multiple Sources ( and )
    FOCS 2006 – Proc. 47th Symposium on Foundations of Computer Science, pp. 399–410.
    Full paper appeared in Math. Oper. Res. 2009
    DOI Bibtex
    @inproceedings{BaumannSkutella2006,
    author = {Baumann, Nadine and Skutella, Martin},
    title = {Solving Evacuation Problems Efficiently--Earliest Arrival Flows with
    Multiple Sources},
    booktitle = {FOCS 2006 – Proc. 47th Symposium on Foundations of Computer Science},
    pages = {399--410},
    year = {2006},
    doi = {10.1109/FOCS.2006.70},
    }
  • Length-Bounded Cuts and Flows (, , , , , , and )
    ICALP 2006 – Proc. 33rd International Colloquium on Automata, Languages and Programming, pp. 679–690.
    Full paper appeared in ACM Trans. Algorithms 2010
    DOI Bibtex
    @inproceedings{BaierErlebachHall+2006,
    author = {Baier, Georg and Erlebach, Thomas and Hall, Alexander and K{\"{o}}hler, Ekkehard and Kolman, Petr and Pangr{\'{a}}c, Ondrej and Schilling, Heiko and Skutella, Martin},
    title = {Length-Bounded Cuts and Flows},
    booktitle = {ICALP 2006 – Proc. 33rd International Colloquium on Automata, Languages and Programming},
    pages = {679--690},
    year = {2006},
    doi = {10.1007/11786986\_59},
    }
  • Multiline Addressing by Network Flow (, , and )
    ESA 2006 – Proc. 14th European Symposium on Algorithms, pp. 744–755.
    Full paper appeared in Algorithmica 2009
    DOI Bibtex
    @inproceedings{EisenbrandKarrenbauerSkutella+2006,
    author = {Eisenbrand, Friedrich and Karrenbauer, Andreas and Skutella, Martin and Xu, Chihao},
    title = {Multiline Addressing by Network Flow},
    booktitle = {ESA 2006 – Proc. 14th European Symposium on Algorithms},
    pages = {744--755},
    year = {2006},
    doi = {10.1007/11841036\_66},
    }
  • Latency Constrained Aggregation in Sensor Networks (, , , , and )
    ESA 2006 – Proc. 14th European Symposium on Algorithms, pp. 88–99.
    Full paper appeared in ACM Trans. Algorithms 2009
    DOI Bibtex
    @inproceedings{BecchettiMarchetti-SpaccamelaVitaletti+2006,
    author = {Becchetti, Luca and Marchetti{-}Spaccamela, Alberto and Vitaletti, Andrea and Korteweg, Peter and Skutella, Martin and Stougie, Leen},
    title = {Latency Constrained Aggregation in Sensor Networks},
    booktitle = {ESA 2006 – Proc. 14th European Symposium on Algorithms},
    pages = {88--99},
    year = {2006},
    doi = {10.1007/11841036\_11},
    }
  • List Scheduling in Order of \(\alpha\)-Points on a Single Machine ()
    Chapter in Efficient Approximation and Online Algorithms – Recent Progress on Classical Combinatorial Optimization Problems and New Applications, .
    DOI Bibtex
    @incollection{Skutella2006,
    author = {Skutella, Martin},
    title = {List Scheduling in Order of {\(\alpha\)}-Points on a Single Machine},
    booktitle = {Efficient Approximation and Online Algorithms -- Recent Progress on
    Classical Combinatorial Optimization Problems and New Applications},
    pages = {250--291},
    year = {2006},
    doi = {10.1007/11671541\_9},
    }
  • Stochastic Machine Scheduling with Precedence Constraints ( and )
    SIAM J. Comput., 34(4):788–802, .
    Extended abstract appeared in Proc. of SODA 2001
    DOI Bibtex
    @article{SkutellaUetz2005,
    author = {Skutella, Martin and Uetz, Marc},
    title = {Stochastic Machine Scheduling with Precedence Constraints},
    journal = {SIAM J. Comput.},
    volume = {34},
    number = {4},
    pages = {788--802},
    year = {2005},
    doi = {10.1137/S0097539702415007},
    }
  • Flows over Time with Load-Dependent Transit Times ( and )
    SIAM J. Optim., 15(4):1185–1202, .
    Extended abstract appeared in Proc. of SODA 2002
    DOI Bibtex
    @article{KoehlerSkutella2005,
    author = {K{\"{o}}hler, Ekkehard and Skutella, Martin},
    title = {Flows over Time with Load-Dependent Transit Times},
    journal = {SIAM J. Optim.},
    volume = {15},
    number = {4},
    pages = {1185--1202},
    year = {2005},
    doi = {10.1137/S1052623403432645},
    }
  • The $k$-Splittable Flow Problem (, and )
    Algorithmica, 42(3-4):231–248, .
    Extended abstract appeared in Proc. of ESA 2002
    DOI Bibtex
    @article{BaierKoehlerSkutella2005,
    author = {Baier, Georg and K{\"{o}}hler, Ekkehard and Skutella, Martin},
    title = {The $k$-Splittable Flow Problem},
    journal = {Algorithmica},
    volume = {42},
    number = {3-4},
    pages = {231--248},
    year = {2005},
    doi = {10.1007/s00453-005-1167-9},
    }
  • Approximating $k$-hop minimum-spanning trees (, , , , and )
    Oper. Res. Lett., 33(2):115–120, .
    DOI Bibtex
    @article{AlthausFunkeHar-Peled+2005,
    author = {Althaus, Ernst and Funke, Stefan and {Har-Peled}, Sariel and Könemann, Jochen and Ramos, Edgar A. and Skutella, Martin},
    title = {Approximating $k$-hop minimum-spanning trees},
    journal = {Oper. Res. Lett.},
    volume = {33},
    number = {2},
    pages = {115--120},
    year = {2005},
    doi = {10.1016/j.orl.2004.05.005},
    }
  • New Approaches for Virtual Private Network Design (, , and )
    ICALP 2005 – Proc. 32nd International Colloquium on Automata, Languages and Programming, pp. 1151–1162.
    Full paper appeared in SIAM J. Comput. 2007
    DOI Bibtex
    @inproceedings{EisenbrandGrandoniOriolo+2005,
    author = {Eisenbrand, Friedrich and Grandoni, Fabrizio and Oriolo, Gianpaolo and Skutella, Martin},
    title = {New Approaches for Virtual Private Network Design},
    booktitle = {ICALP 2005 – Proc. 32nd International Colloquium on Automata, Languages and Programming},
    pages = {1151--1162},
    year = {2005},
    doi = {10.1007/11523468\_93},
    }
  • Approximation and Complexity of $k$-Splittable Flows (, and )
    WAOA 2005 – Proc. 3rd Workshop on Approximation and Online Algorithms, pp. 244–257.
    Full paper appeared in Theory Comput. Syst. 2008
    DOI Bibtex
    @inproceedings{KochSkutellaSpenke2005,
    author = {Koch, Ronald and Skutella, Martin and Spenke, Ines},
    title = {Approximation and Complexity of $k$-Splittable Flows},
    booktitle = {WAOA 2005 – Proc. 3rd Workshop on Approximation and Online Algorithms},
    pages = {244--257},
    year = {2005},
    doi = {10.1007/11671411\_19},
    }
  • Length-Bounded and Dynamic $k$-Splittable Flows ( and )
    OR 2005 – Proc. International Conference of the German Operations Research Society, pp. 297–302.
    DOI Bibtex
    @inproceedings{MartensSkutella2005,
    author = {Martens, Maren and Skutella, Martin},
    title = {Length-Bounded and Dynamic $k$-Splittable Flows},
    booktitle = {OR 2005 – Proc. International Conference of the German Operations Research Society},
    pages = {297--302},
    year = {2005},
    doi = {10.1007/3-540-32539-5\_47},
    }
  • Scheduling with AND/OR Precedence Constraints (, and )
    SIAM J. Comput., 33(2):393–415, .
    Extended abstract appeared in Proc. of SODA 2000
    DOI Bibtex
    @article{MoehringSkutellaStork2004,
    author = {M{\"{o}}hring, Rolf H. and Skutella, Martin and Stork, Frederik},
    title = {Scheduling with {AND/OR} Precedence Constraints},
    journal = {SIAM J. Comput.},
    volume = {33},
    number = {2},
    pages = {393--415},
    year = {2004},
    doi = {10.1137/S009753970037727X},
    }
  • Cooperative facility location games ( and )
    J. Algorithms, 50(2):194–214, .
    Extended abstract appeared in Proc. of SODA 2000
    DOI Bibtex
    @article{GoemansSkutella2004,
    author = {Goemans, Michel X. and Skutella, Martin},
    title = {Cooperative facility location games},
    journal = {J. Algorithms},
    volume = {50},
    number = {2},
    pages = {194--214},
    year = {2004},
    doi = {10.1016/S0196-6774(03)00098-1},
    }
  • Online Scheduling with Bounded Migration (, and )
    ICALP 2004 – Proc. 31st International Colloquium on Automata, Languages and Programming, pp. 1111–1122.
    Full paper appeared in Math. Oper. Res. 2009
    DOI Bibtex
    @inproceedings{SandersSivadasanSkutella2004,
    author = {Sanders, Peter and Sivadasan, Naveen and Skutella, Martin},
    title = {Online Scheduling with Bounded Migration},
    booktitle = {ICALP 2004 – Proc. 31st International Colloquium on Automata, Languages and Programming},
    pages = {1111--1122},
    year = {2004},
    doi = {10.1007/978-3-540-27836-8\_92},
    }
  • Flows on Few Paths: Algorithms and Lower Bounds ( and )
    ESA 2004 – Proc. 12th European Symposium on Algorithms, pp. 520–531.
    Full paper appeared in Networks 2006
    DOI Bibtex
    @inproceedings{MartensSkutella2004,
    author = {Martens, Maren and Skutella, Martin},
    title = {Flows on Few Paths: Algorithms and Lower Bounds},
    booktitle = {ESA 2004 – Proc. 12th European Symposium on Algorithms},
    pages = {520--531},
    year = {2004},
    doi = {10.1007/978-3-540-30140-0\_47},
    }
  • Preemptive scheduling with rejection (, and )
    Math. Program., 94(2-3):361–374, .
    Extended abstract appeared in Proc. of ESA 2000
    DOI Bibtex
    @article{HoogeveenSkutellaWoeginger2003,
    author = {Hoogeveen, Han and Skutella, Martin and Woeginger, Gerhard J.},
    title = {Preemptive scheduling with rejection},
    journal = {Math. Program.},
    volume = {94},
    number = {2-3},
    pages = {361--374},
    year = {2003},
    doi = {10.1007/s10107-002-0324-z},
    }
  • The complexity of economic equilibria for house allocation markets (, and )
    Inf. Process. Lett., 88(5):219–223, .
    DOI Bibtex
    @article{FeketeSkutellaWoeginger2003,
    author = {Fekete, S{\'{a}}ndor P. and Skutella, Martin and Woeginger, Gerhard J.},
    title = {The complexity of economic equilibria for house allocation markets},
    journal = {Inf. Process. Lett.},
    volume = {88},
    number = {5},
    pages = {219--223},
    year = {2003},
    doi = {10.1016/j.ipl.2003.08.008},
    }
  • Minimum cost flows over time without intermediate storage ( and )
    SODA 2003 – Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, pp. 66–75.
    Full paper appeared in SIAM J. Comput. 2007
    [url] Bibtex
    @inproceedings{FleischerSkutella2003,
    author = {Fleischer, Lisa and Skutella, Martin},
    title = {Minimum cost flows over time without intermediate storage},
    booktitle = {SODA 2003 – Proc. 14th ACM-SIAM Symposium on Discrete Algorithms},
    pages = {66--75},
    year = {2003},
    url = {http://dl.acm.org/citation.cfm?id=644108.644118},
    }
  • Multicommodity Flows over Time: Efficient Algorithms and Complexity (, and )
    ICALP 2003 – Proc. 30th International Colloquium on Automata, Languages and Programming, pp. 397–409.
    Full paper appeared in Theor. Comput. Sci. 2007
    DOI Bibtex
    @inproceedings{HallHipplerSkutella2003,
    author = {Hall, Alexander and Hippler, Steffen and Skutella, Martin},
    title = {Multicommodity Flows over Time: Efficient Algorithms and Complexity},
    booktitle = {ICALP 2003 – Proc. 30th International Colloquium on Automata, Languages and Programming},
    pages = {397--409},
    year = {2003},
    doi = {10.1007/3-540-45061-0\_33},
    }
  • An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times (, and )
    APPROX 2003 – Proc. 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 71–82.
    Full paper appeared in Algorithmica 2007
    DOI Bibtex
    @inproceedings{HallLangkauSkutella2003,
    author = {Hall, Alexander and Langkau, Katharina and Skutella, Martin},
    title = {An {FPTAS} for Quickest Multicommodity Flows with Inflow-Dependent
    Transit Times},
    booktitle = {APPROX 2003 – Proc. 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems},
    pages = {71--82},
    year = {2003},
    doi = {10.1007/978-3-540-45198-3\_7},
    }
  • Approximating the single source unsplittable min-cost flow problem ()
    Math. Program., 91(3):493–514, .
    Extended abstract appeared in Proc. of FOCS 2000
    DOI Bibtex
    @article{Skutella2002,
    author = {Skutella, Martin},
    title = {Approximating the single source unsplittable min-cost flow problem},
    journal = {Math. Program.},
    volume = {91},
    number = {3},
    pages = {493--514},
    year = {2002},
    doi = {10.1007/s101070100260},
    }
  • The Power of $\alpha$-Points in Preemptive Single Machine Scheduling ( and )
    J. Sched., 5:121–133, .
    DOI Bibtex
    @article{SchulzSkutella2002a,
    author = {Schulz, Andreas S. and Skutella, Martin},
    journal = {J. Sched.},
    pages = {121--133},
    title = {The Power of $\alpha$-Points in Preemptive Single Machine Scheduling},
    volume = {5},
    year = {2002},
    doi = {10.1002/jos.93},
    }
  • Single Machine Scheduling with Release Dates (, , , and )
    SIAM J. Discret. Math., 15(2):165–192, .
    DOI Bibtex
    @article{GoemansQueyranneSchulz+2002,
    author = {Goemans, Michel X. and Queyranne, Maurice and Schulz, Andreas S. and Skutella, Martin and Wang, Yaoguang},
    title = {Single Machine Scheduling with Release Dates},
    journal = {SIAM J. Discret. Math.},
    volume = {15},
    number = {2},
    pages = {165--192},
    year = {2002},
    doi = {10.1137/S089548019936223X},
    }
  • Scheduling Unrelated Machines by Randomized Rounding ( and )
    SIAM J. Discret. Math., 15(4):450–469, .
    Extended abstract appeared in Proc. of ESA 1997
    DOI Bibtex
    @article{SchulzSkutella2002,
    author = {Schulz, Andreas S. and Skutella, Martin},
    title = {Scheduling Unrelated Machines by Randomized Rounding},
    journal = {SIAM J. Discret. Math.},
    volume = {15},
    number = {4},
    pages = {450--469},
    year = {2002},
    doi = {10.1137/S0895480199357078},
    }
  • Flows over time with load-dependent transit times ( and )
    SODA 2002 – Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 174–183.
    Full paper appeared in SIAM J. Optim. 2005
    [url] Bibtex
    @inproceedings{KoehlerSkutella2002,
    author = {K{\"{o}}hler, Ekkehard and Skutella, Martin},
    title = {Flows over time with load-dependent transit times},
    booktitle = {SODA 2002 – Proc. 13th ACM-SIAM Symposium on Discrete Algorithms},
    pages = {174--183},
    year = {2002},
    url = {http://dl.acm.org/citation.cfm?id=545381.545403},
    }
  • The freeze-tag problem: how to wake up a swarm of robots (, , , and )
    SODA 2002 – Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 568–577.
    Full paper appeared in Algorithmica 2006
    [url] Bibtex
    @inproceedings{ArkinBenderFekete2002,
    author = {Arkin, Esther M. and Bender, Michael A. and Fekete, S{\'{a}}ndor P. and Mitchell, Joseph S. B. and Skutella, Martin},
    title = {The freeze-tag problem: how to wake up a swarm of robots},
    booktitle = {SODA 2002 – Proc. 13th ACM-SIAM Symposium on Discrete Algorithms},
    pages = {568--577},
    year = {2002},
    url = {http://dl.acm.org/citation.cfm?id=545381.545457},
    }
  • The Quickest Multicommodity Flow Problem ( and )
    IPCO 2002 – Proc. 9th Conference on Integer Programming and Combinatorial Optimization, pp. 36–53.
    Full paper appeared in SIAM J. Comput. 2007
    DOI Bibtex
    @inproceedings{FleischerSkutella2002,
    author = {Fleischer, Lisa and Skutella, Martin},
    title = {The Quickest Multicommodity Flow Problem},
    booktitle = {IPCO 2002 – Proc. 9th Conference on Integer Programming and Combinatorial Optimization},
    pages = {36--53},
    year = {2002},
    doi = {10.1007/3-540-47867-1\_4},
    }
  • On the $k$-Splittable Flow Problem (, and )
    ESA 2002 – Proc. 10th European Symposium on Algorithms, pp. 101–113.
    Full paper appeared in Algorithmica 2005
    DOI Bibtex
    @inproceedings{BaierKoehlerSkutella2002,
    author = {Baier, Georg and K{\"{o}}hler, Ekkehard and Skutella, Martin},
    title = {On the $k$-Splittable Flow Problem},
    booktitle = {ESA 2002 – Proc. 10th European Symposium on Algorithms},
    pages = {101--113},
    year = {2002},
    doi = {10.1007/3-540-45749-6\_13},
    }
  • Time-Expanded Graphs for Flow-Dependent Transit Times (, and )
    ESA 2002 – Proc. 10th European Symposium on Algorithms, pp. 599–611.
    DOI Bibtex
    @inproceedings{KoehlerLangkauSkutella2002,
    author = {K{\"{o}}hler, Ekkehard and Langkau, Katharina and Skutella, Martin},
    title = {Time-Expanded Graphs for Flow-Dependent Transit Times},
    booktitle = {ESA 2002 – Proc. 10th European Symposium on Algorithms},
    pages = {599--611},
    year = {2002},
    doi = {10.1007/3-540-45749-6\_53},
    }
  • Convex quadratic and semidefinite programming relaxations in scheduling ()
    J. ACM, 48(2):206–242, .
    Extended abstracts of different parts appeared in Proc. of FOCS 1998 and ESA 1999
    DOI Bibtex
    @article{Skutella2001,
    author = {Skutella, Martin},
    title = {Convex quadratic and semidefinite programming relaxations in scheduling},
    journal = {J. ACM},
    volume = {48},
    number = {2},
    pages = {206--242},
    year = {2001},
    doi = {10.1145/375827.375840},
    }
  • Scheduling precedence-constrained jobs with stochastic processing times on parallel machines ( and )
    SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 589–590.
    Full paper appeared in SIAM J. Comput. 2005
    [url] Bibtex
    @inproceedings{SkutellaUetz2001,
    author = {Skutella, Martin and Uetz, Marc},
    title = {Scheduling precedence-constrained jobs with stochastic processing
    times on parallel machines},
    booktitle = {SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms},
    pages = {589--590},
    year = {2001},
    url = {http://dl.acm.org/citation.cfm?id=365411.365543},
    }
  • A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines ( and )
    Math. Oper. Res., 25(1):63–75, .
    Extended abstract appeared in Proc. of STOC 1999
    DOI Bibtex
    @article{SkutellaWoeginger2000,
    author = {Skutella, Martin and Woeginger, Gerhard J.},
    title = {A {PTAS} for Minimizing the Total Weighted Completion Time on Identical
    Parallel Machines},
    journal = {Math. Oper. Res.},
    volume = {25},
    number = {1},
    pages = {63--75},
    year = {2000},
    doi = {10.1287/moor.25.1.63.15212},
    }
  • Approximating the single source unsplittable min-cost flow problem ()
    FOCS 2000 – Proc. 41st Symposium on Foundations of Computer Science, pp. 136–145.
    Full paper appeared in Math. Program. 2002
    DOI Bibtex
    @inproceedings{Skutella2000,
    author = {Skutella, Martin},
    title = {Approximating the single source unsplittable min-cost flow problem},
    booktitle = {FOCS 2000 – Proc. 41st Symposium on Foundations of Computer Science},
    pages = {136--145},
    year = {2000},
    doi = {10.1109/SFCS.2000.892073},
    }
  • Forcing relations for AND/OR precedence constraints (, and )
    SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 235–236.
    Full paper appeared in SIAM J. Comput. 2004
    [url] Bibtex
    @inproceedings{MoehringSkutellaStork2000,
    author = {M{\"{o}}hring, Rolf H. and Skutella, Martin and Stork, Frederik},
    title = {Forcing relations for {AND/OR} precedence constraints},
    booktitle = {SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms},
    pages = {235--236},
    year = {2000},
    url = {http://dl.acm.org/citation.cfm?id=338219.338257},
    }
  • Cooperative facility location games ( and )
    SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 76–85.
    Full paper appeared in J. Algorithms 2004
    [url] Bibtex
    @inproceedings{GoemansSkutella2000,
    author = {Goemans, Michel X. and Skutella, Martin},
    title = {Cooperative facility location games},
    booktitle = {SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms},
    pages = {76--85},
    year = {2000},
    url = {http://dl.acm.org/citation.cfm?id=338219.338238},
    }
  • Preemptive Scheduling with Rejection (, and )
    ESA 2000 – Proc. 8th European Symposium on Algorithms, pp. 268–277.
    Full paper appeared in Math. Program. 2003
    DOI Bibtex
    @inproceedings{HoogeveenSkutellaWoeginger2000,
    author = {Hoogeveen, Han and Skutella, Martin and Woeginger, Gerhard J.},
    title = {Preemptive Scheduling with Rejection},
    booktitle = {ESA 2000 – Proc. 8th European Symposium on Algorithms},
    pages = {268--277},
    year = {2000},
    doi = {10.1007/3-540-45253-2\_25},
    }
  • Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (, , , , , , , , , and )
    FOCS 1999 – Proc. 40th Symposium on Foundations of Computer Science, pp. 32–44.
    DOI Bibtex
    @inproceedings{AfratiBampisChekuri+1999,
    author = {Afrati, Foto N. and
    Bampis, Evripidis and
    Chekuri, Chandra and
    Karger, David R. and
    Kenyon, Claire and
    Khanna, Sanjeev and
    Milis, Ioannis and
    Queyranne, Maurice and
    Skutella, Martin and
    Stein, Clifford and
    Sviridenko, Maxim},
    title = {Approximation Schemes for Minimizing Average Weighted Completion Time
    with Release Dates},
    booktitle = {FOCS 1999 – Proc. 40th Symposium on Foundations of Computer Science},
    pages = {32--44},
    year = {1999},
    doi = {10.1109/SFFCS.1999.814574},
    }
  • A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines ( and )
    STOC 1999 – Proc. 31st Symposium on Theory of Computing, pp. 400–407.
    Full paper appeared in Math. Oper. Res. 2000
    DOI Bibtex
    @inproceedings{SkutellaWoeginger1999,
    author = {Skutella, Martin and Woeginger, Gerhard J.},
    title = {A {PTAS} for Minimizing the Weighted Sum of Job Completion Times on
    Parallel Machines},
    booktitle = {STOC 1999 – Proc. 31st Symposium on Theory of Computing},
    pages = {400--407},
    year = {1999},
    doi = {10.1145/301250.301356},
    }
  • Convex Quadratic Programming Relaxations for Network Scheduling Problems ()
    ESA 1999 – Proc. 7th European Symposium on Algorithms, pp. 127–138.
    Full paper appeared in J. ACM 2001
    DOI Bibtex
    @inproceedings{Skutella1999a,
    author = {Skutella, Martin},
    title = {Convex Quadratic Programming Relaxations for Network Scheduling Problems},
    booktitle = {ESA 1999 – Proc. 7th European Symposium on Algorithms},
    pages = {127--138},
    year = {1999},
    doi = {10.1007/3-540-48481-7\_12},
    }
  • Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem ()
    Math. Oper. Res., 23(4):909–929, .
    Extended abstract appeared in Proc. of SODA 1997
    DOI Bibtex
    @article{Skutella1998,
    author = {Skutella, Martin},
    title = {Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem},
    journal = {Math. Oper. Res.},
    volume = {23},
    number = {4},
    pages = {909--929},
    year = {1998},
    doi = {10.1287/moor.23.4.909},
    }
  • Semidefinite Relaxations for Parallel Machine Scheduling ()
    FOCS 1998 – Proc. 39th Symposium on Foundations of Computer Science, pp. 472–481.
    Full paper appeared in J. ACM 2001
    DOI Bibtex
    @inproceedings{Skutella1998a,
    author = {Skutella, Martin},
    title = {Semidefinite Relaxations for Parallel Machine Scheduling},
    booktitle = {FOCS 1998 – Proc. 39th Symposium on Foundations of Computer Science},
    pages = {472--481},
    year = {1998},
    doi = {10.1109/SFCS.1998.743498},
    }
  • Approximation and Randomization in Scheduling ()
    PhD thesis, TU Berlin, .
    [pdf] Bibtex
    @phdthesis{ThesisSkutella1998,
    title = {Approximation and Randomization in Scheduling},
    author = {Skutella, Martin},
    year = {1998},
    type = {Doctoral Thesis},
    school = {TU Berlin},
    url = {ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/dissertation-skutella.pdf},
    }
  • Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem ()
    SODA 1997 – Proc. 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 501–508.
    Full paper appeared in Math. Oper. Res. 2000
    [url] Bibtex
    @inproceedings{Skutella1997,
    author = {Skutella, Martin},
    title = {Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem},
    booktitle = {SODA 1997 – Proc. 8th ACM-SIAM Symposium on Discrete Algorithms},
    pages = {501--508},
    year = {1997},
    url = {https://dl.acm.org/doi/10.5555/314161.314375},
    }
  • Scheduling-LPs Bear Probabilities: Randomized Approximations for Min-Sum Criteria ( and )
    ESA 1997 – Proc. 5th European Symposium on Algorithms, pp. 416–429.
    Full paper appeared in SIAM J. Discret. Math. 2002
    DOI Bibtex
    @inproceedings{SchulzSkutella1997,
    author = {Schulz, Andreas S. and Skutella, Martin},
    title = {Scheduling-LPs Bear Probabilities: Randomized Approximations for Min-Sum
    Criteria},
    booktitle = {ESA 1997 – Proc. 5th European Symposium on Algorithms},
    pages = {416--429},
    year = {1997},
    doi = {10.1007/3-540-63397-9\_32},
    }
  • Random-Based Scheduling: New Approximations and LP Lower Bounds ( and )
    RANDOM 1997 – Proc. 1st International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 119–133.
    Full paper appeared in J. Sched. 2002
    DOI Bibtex
    @inproceedings{SchulzSkutella1997a,
    author = {Schulz, Andreas S. and Skutella, Martin},
    title = {Random-Based Scheduling: New Approximations and {LP} Lower Bounds},
    booktitle = {RANDOM 1997 – Proc. 1st International Workshop on Randomization and Approximation Techniques in Computer Science},
    pages = {119--133},
    year = {1997},
    doi = {10.1007/3-540-63248-4\_11},
    }
  • Parallel Repetition of MIP(2, 1) Systems ( and )
    Chapter in Lectures on Proof Verification and Approximation Algorithms, .
    DOI Bibtex
    @incollection{GroeplSkutella1997,
    author = {Gr{\"{o}}pl, Clemens and Skutella, Martin},
    title = {Parallel Repetition of MIP(2, 1) Systems},
    booktitle = {Lectures on Proof Verification and Approximation Algorithms},
    pages = {161--178},
    year = {1997},
    doi = {10.1007/BFb0053016},
    }