Publications

Reduction of Potential-Based Flow Networks (Max Klimm, Marc Pfetsch, Rico Raber and Martin Skutella)
Math. Oper. Res., to appear.
DOI Bibtex
@article{KlimmPfetschRaber+2023a,
author = {Max Klimm and Marc Pfetsch and Rico Raber and Martin Skutella},
title = {Reduction of Potential-Based Flow Networks},
journal = {Math. Oper. Res.},
year = {to appear},
doi = {10.1287/moor.2022.1338},
}
Combinatorial generation via permutation languages. III. Rectangulations (Arturo Merino and Torsten Mütze)
Discret. Comput. Geom., to appear.
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},
}
Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size (Christoph Hertrich and Martin Skutella)
INFORMS J. Comput..
Extended abstract appeared in Proc. of AAAI 2021
DOI Bibtex
@article{HertrichSkutella2023,
author = {Hertrich, Christoph and Skutella, Martin},
doi = {10.1287/ijoc.2021.0225},
journal = {INFORMS J. Comput.},
title = {Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size},
}
The Submodular Santa Claus Problem (Etienne Bamas, Sarah Morell and Lars Rohwedder)
arXiv preprint arXiv:2407.04824, to appear.
Bibtex
@article{bamas2024submodular,
title = {The Submodular Santa Claus Problem},
author = {Bamas, Etienne and Morell, Sarah and Rohwedder, Lars},
journal = {arXiv preprint arXiv:2407.04824},
year = {to appear},
}
Topological Expressivity of ReLU Neural Networks (Ekin Ergen and Moritz Grillo)
COLT 2024 – Proc. 37th Conference on Learning Theory.
Bibtex
@inproceedings{ErgenGrillo2024,
author = {Ergen, Ekin and Grillo, Moritz},
title = {Topological Expressivity of ReLU Neural Networks},
booktitle = {COLT 2024 – Proc. 37th Conference on Learning Theory},
year = {to appear},
}
Insertion Heuristics for (1,2)-TSP (Ekin Ergen)
OR 2023 – Proc. International Conference of the German Operations Research Society.
Bibtex
@inproceedings{Ergen2024,
author = {Ergen, Ekin},
title = {Insertion Heuristics for {(1,2)}-{TSP}},
booktitle = {OR 2023 – Proc. International Conference of the German Operations Research Society},
year = {to appear},
}

On the Robustness of Potential-Based Flow Networks (Max Klimm, Marc E. Pfetsch, Rico Raber and Martin Skutella)
Math. Program., 197(1):337–374, 2023.
DOI Bibtex
@article{KlimmPfetschRaber+2023,
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 = {2023},
volume = {197},
number = {1},
pages = {337--374},
doi = {10.1007/s10107-021-01760-w},
}
Convergence of a Packet Routing Model to Flows Over Time (Leon Sering, Laura Vargas Koch and Theresa Ziemke)
Math. Oper. Res., 48(3):1741-1766, 2023.
DOI Bibtex
@article{SeringEtAl2022ConvergenceFlowOverTimesJournalExtension,
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},
journal = {Math. Oper. Res.},
volume = {48},
number = {3},
pages = {1741-1766},
year = {2023},
doi = {10.1287/moor.2022.1318},
}
Spatiotemporal reconstruction of ancient road networks through sequential cost–benefit analysis (Maximilian J. Stahlberg, Guillaume Sagnol, Benjamin Ducke and Max Klimm)
PNAS Nexus, 2(2):pgac313, 2023.
DOI Bibtex
@article{StahlbergSagnolDuckeKlimm2023,
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 = {2023},
doi = {10.1093/pnasnexus/pgac313},
volume = {2},
number = {2},
pages = {pgac313},
}
A Note on the Quickest Minimum Cost Transshipment Problem (Martin Skutella)
Oper. Res. Lett., 51(3):255–258, 2023.
DOI Bibtex
@article{Skutella2023,
author = {Skutella, Martin},
journal = {Oper. Res. Lett.},
title = {A Note on the Quickest Minimum Cost Transshipment Problem},
year = {2023},
volume = {51},
number = {3},
pages = {255--258},
doi = {10.1016/j.orl.2023.03.005},
}
Fast Screening Rules for Optimal Design via Quadratic Lasso Reformulation (Guillaume Sagnol and Luc Pronzato)
Journal of Machine Learning Research, 24(307):1–32, 2023.
PDF arxiv Bibtex
@article{SagnolPronzato2023,
author = {Guillaume Sagnol and Luc Pronzato},
title = {Fast Screening Rules for Optimal Design via Quadratic Lasso Reformulation},
journal = {Journal of Machine Learning Research},
year = {2023},
volume = {24},
number = {307},
pages = {1--32},
url = {http://jmlr.org/papers/v24/22-1305.html},
arxiv = {2310.08939},
}
Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling (Sven Jäger, Guillaume Sagnol, Daniel Schmidt genannt Waldschmidt and Philipp Warode)
IPCO 2023 – Proc. 24th Conference on Integer Programming and Combinatorial Optimization, pp. 246–260.
PDF DOI 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},
pages = {246--260},
doi = {10.1007/978-3-031-32726-1_18},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {13904},
}
Improved Analysis of Two Algorithms for Min-Weighted Sum Bin Packing (Guillaume Sagnol)
IWOCA 2023 – Proc. 34th, pp. 343–355.
PDF DOI arxiv Bibtex
@inproceedings{Sagnol2023,
author = {Guillaume Sagnol},
title = {Improved Analysis of Two Algorithms for Min-Weighted Sum Bin Packing},
booktitle = {IWOCA 2023 – Proc. 34th},
series = {Lecture Notes in Computer Science (LNCS)},
volume = {13889},
year = {2023},
pages = {343--355},
doi = {10.1007/978-3-031-34347-6_29},
arxiv = {2304.02498},
}
Spillback Changes the Long-Term Behavior of Dynamic Equilibria in Fluid Queuing Networks (Theresa Ziemke, Leon Sering and Kai Nagel)
ATMOS 2023 – Proc. 23rd Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, pp. 11:1–11:14.
DOI Bibtex
@inproceedings{ZiemkeEtAl2023NoSteadyStateWithSpillback,
author = {Ziemke, Theresa and Sering, Leon and Nagel, Kai},
title = {{Spillback Changes the Long-Term Behavior of Dynamic Equilibria in Fluid Queuing Networks}},
booktitle = {ATMOS 2023 – Proc. 23rd Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
year = {2023},
volume = {115},
pages = {11:1--11:14},
doi = {10.4230/OASIcs.ATMOS.2023.11},
}
Total Completion Time Scheduling Under Scenarios (Thomas Bosman, Martijn van Ee, Ekin Ergen, Csanád Imreh, Alberto Marchetti-Spaccamela, Martin Skutella and Leen Stougie)
WAOA 2023 – Proc. 21st Workshop on Approximation and Online Algorithms, pp. 104–118.
Bibtex
@inproceedings{BosmanEtAl2023,
title = {Total Completion Time Scheduling Under Scenarios},
author = {Bosman, Thomas and van Ee, Martijn and Ergen, Ekin and Imreh, Csan{\'a}d and Marchetti-Spaccamela, Alberto and Skutella, Martin and Stougie, Leen},
booktitle = {WAOA 2023 – Proc. 21st Workshop on Approximation and Online Algorithms},
pages = {104--118},
year = {2023},
}
Surgery Scheduling in Flexible Operating Rooms by using a Convex Surrogate Model of Second-Stage Costs (Mohammed Majthoub Almoghrabi and Guillaume Sagnol)
Preprint, 2023.
PDF arxiv Bibtex Abstract
@techreport{almoghrabi2023surgery,
title = {Surgery Scheduling in Flexible Operating Rooms by using a Convex Surrogate Model of Second-Stage Costs},
author = {Majthoub Almoghrabi, Mohammed and Sagnol, Guillaume},
year = {2023},
arxiv = {2304.13670},
}

We study the elective surgery planning problem in a hospital with operation rooms shared by elective and emergency patients. This problem can be split in two distinct phases. First, a subset of patients to be operated in the next planning period has to be selected, and the selected patients have to be assigned to a block and a tentative starting time. Then, in the online phase of the problem, a policy decides how to insert the emergency patients in the schedule and may cancel planned surgeries. The overall goal is to minimize the expectation of a cost function representing the assignment of patient to blocks, case cancellations, overtime, waiting time and idle time. We model the offline problem by a two-stage stochastic program, and show that the second-stage costs can be replaced by a convex piecewise linear surrogate model that can be computed in a preprocessing step. This results in a mixed integer program which can be solved in a short amount of time, even for very large instances of the problem. We also describe a greedy policy for the online phase of the problem, and analyze the performance of our approach by comparing it to either heuristic methods or approaches relying on sampling average approximation (SAA) on a large set of benchmarking instances. Our simulations indicate that our approach can reduce the expected costs by as much as 20% compared to heuristic methods and is able to solve problems with 1000 patients in about one minute, while SAA-approaches fail to obtain near-optimal solutions within 30 minutes, already for 100 patients.

Single source unsplittable flows with arc-wise lower and upper bounds (Sarah Morell and Martin Skutella)
Math. Program., 192(1):477–496, 2022.
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},
}
Packing Under Convex Quadratic Constraints (Max Klimm, Marc E. Pfetsch, Rico Raber and Martin Skutella)
Math. Program., 192(1):361–386, 2022.
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},
}
On a Combinatorial Generation Problem of Knuth (Arturo Merino, Ondřej Mička and Torsten Mütze)
SIAM J. Comput., 51(3):379-423, 2022.
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},
}
An Improved Upper Bound for the Ring Loading Problem (Karl Däubel)
SIAM J. Discret. Math., 36(2):867–887, 2022.
DOI Bibtex
@article{Daeubel2022,
author = {Däubel, Karl},
title = {An Improved Upper Bound for the Ring Loading Problem},
journal = {SIAM J. Discret. Math.},
volume = {36},
number = {2},
pages = {867--887},
year = {2022},
doi = {10.1137/20m1319395},
}
PICOS: A Python interface to conic optimization solvers (Guillaume Sagnol and Maximilian Stahlberg)
J. Open Source Softw., 7(70):3915, 2022.
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},
}
The Effect of Speed Limits and Traffic Signal Control on Emissions (Jonathan Rhode, Peter Wagner and Theresa Ziemke)
Procedia Computer Science, 201:568–573, 2022.
[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},
}
Using reinforcement learning to control traffic signals in a real-world scenario: An approach based on linear function approximation (Lucas N. Alegre, Theresa Ziemke and Ana L. C. Bazzan)
IEEE Transactions on Intelligent Transportation Systems, 23(7):9126–9135, 2022.
[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},
}
Competitive Algorithms for Symmetric Rendezvous on the Line (Max Klimm, Guillaume Sagnol, Martin Skutella and Khai Van Tran)
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 (Miriam Schlöter, Martin Skutella and Khai Van Tran)
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},
}
Efficient generation of elimination trees and graph associahedra (Jean Cardinal, Arturo Merino and Torsten Mütze)
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},
}
Star Transposition Gray Codes for Multiset Permutations (Petr Gregor, Arturo Merino and Torsten Mütze)
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},
}
The Hamilton compression of highly symmetric graphs (Petr Gregor, Arturo Merino and Torsten Mütze)
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},
}
All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges (Arturo Merino, Torsten Mütze and Aaron Williams)
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 (Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt)
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 (Luc Pronzato and Guillaume Sagnol)
J. Stat. Plan. Inference, 213:233–252, 2021.
[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 (Joseph Cheriyan, R. Ravi and Martin Skutella)
Oper. Res. Lett., 49(6):842–843, 2021.
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 (Theresa Ziemke, Leon Sering, Laura Vargas Koch, Max Zimmer, Kai Nagel and Martin Skutella)
Transportation Research Procedia, 52:123–130, 2021.
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 (Theresa Ziemke, Lucas N. Alegre and Ana L. C. Bazzan)
AI Communications, 34(1):89–103, 2021.
[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 (Theresa Ziemke and Söhnke Braun)
Procedia Computer Science, 184:745–752, 2021.
[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 (Chistoph Hertrich, Amitabh Basu, Marco Di Summa and Martin Skutella)
NeurIPS 2021 – Proc. 35th Conference on Neural Information Processing Systems, pp. 3336–3348.
[pdf] 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},
url = {https://proceedings.neurips.cc/paper/2021/file/1b9812b99fe2672af746cefda86be5f9-Paper.pdf},
}
Minimum-cost integer circulations in given homology classes (Sarah Morell, Ina Seidel and Stefan Weltge)
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},
}
On a Combinatorial Generation Problem of Knuth (Arturo Merino, Ondřej Mička and Torsten Mütze)
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},
}
Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size (Christoph Hertrich and Martin Skutella)
AAAI 2021 – Proc. 35th AAAI Conference on Artificial Intelligence, pp. 7685–7693.
Full paper to appear in INFORMS J. Comput.
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},
}
Efficient Generation of Rectangulations via Permutation Languages (Arturo Merino and Torsten Mütze)
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},
}
Restricted Adaptivity in Stochastic Scheduling (Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt)
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},
}
Convergence of a Packet Routing Model to Flows Over Time (Leon Sering, Laura Vargas Koch and Theresa Ziemke)
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 (Sven J. Jäger)
PhD thesis, TU Berlin, 2021.
[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 (Belmiro P.M. Duarte and Guillaume Sagnol)
Stat. Pap., 61:2737–2767, 2020.
[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 (Max Klimm, Marc E. Pfetsch, Rico Raber and Martin Skutella)
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 (Sarah Morell and Martin Skutella)
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 (Arturo Merino and Andreas Wiese)
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 (Alberto Marchetti-Spaccamela, Nicole Megow, Jens Schlöter, Martin Skutella and Leen Stougie)
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 (Theresa Ziemke, Lucas N. Alegre and Ana L. C. Bazzan)
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},
}
Some Aspects of Graph Sparsification in Theory and Practice (Karl Däubel)
PhD thesis, TU Berlin, 2020.
[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},
}
Nash Flows Over Time (Leon Sering)
PhD thesis, TU Berlin, 2020.
[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},
}

The Simplex Algorithm is NP-Mighty (Yann Disser and Martin Skutella)
ACM Trans. Algorithms, 15(1):5:1–5:19, 2019.
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 (Ágnes Cseh and Martin Skutella)
Int. J. Game Theory, 48(3):835–862, 2019.
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},
}
Maximizing the storage capacity of gas networks: a global MINLP approach (Robert Burlacu, Herbert Egger, Martin Groß, Alexander Martin, Marc E. Pfetsch, Lars Schewe, Mathias Sirvent and Martin Skutella)
Optim. Eng., 20:543–573, 2019.
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},
}
Algorithmic results for potential-based flows: Easy and hard cases (Martin Groß, Marc E. Pfetsch, Lars Schewe, Martin Schmidt and Martin Skutella)
Networks, 73(3):306–324, 2019.
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 (Guillaume Sagnol and Edouard Pauwels)
Stat. Pap., 60(2):215–234, 2019.
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},
}
Optimization and simulation of fixed-time traffic signal control in real-world applications (Theresa Thunig, Robert Scheffler, Martin Strehler and Kai Nagel)
Procedia Computer Science, Elsevier BV, 151:826–833, 2019.
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 (Theresa Thunig, Nico Kühnel and Kai Nagel)
Transportation Research Procedia, Elsevier BV, 37:481–488, 2019.
[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 (Arturo Merino and José A. Soto)
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 (Theresa Thunig and Kai Nagel)
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 (Sebastian Schenker)
PhD thesis, TU Berlin, 2019.
[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 (Jannik Matuschke, Martin Skutella and José A. Soto)
Math. Oper. Res., 43(2):675–692, 2018.
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 (Belmiro P.M. Duarte, Guillaume Sagnol and Weng Kee Wong)
Comput. Stat. Data Anal., 119:99–117, 2018.
[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},
}
On the complexity of instationary gas flows (Martin Groß, Marc E. Pfetsch and Martin Skutella)
Oper. Res. Lett., 46(3):286–290, 2018.
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},
}
The Cone of Flow Matrices: Approximation Hierarchies and Applications (Guillaume Sagnol, Marco Blanco and Thibault Sauvage)
Networks, 72(1):128–150, 2018.
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 (Guillaume Sagnol, Christoph Barner, Ralf Borndörfer, Mickaël Grima, Matthes Seeling, Claudia Spies and Klaus Wernecke)
Eur. J. Oper. Res., 271(2):420–435, 2018.
[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},
}
Implementing an adaptive traffic signal control algorithm in an agent-based transport simulation (Nico Kühnel, Theresa Thunig and Kai Nagel)
Procedia Computer Science, Elsevier BV, 130:894–899, 2018.
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 (Sven Jäger and Martin Skutella)
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 (Leon Sering and Martin Skutella)
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 (Alfonso Cevallos, Friedrich Eisenbrand and Sarah Morell)
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 (Frank Neumann, Frank Polyakovskiy, Martin Skutella, Leen Stougie and Junhua Wu)
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 (Guillaume Sagnol, Marco Blanco and Thibault Sauvage)
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 (Guillaume Sagnol, Daniel Schmidt genannt Waldschmidt and Alexander Tesch)
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},
}
Flows Over Time and Submodular Function Minimization (Miriam Schlöter)
PhD thesis, TU Berlin, 2018.
[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},
}
Uncertainty Exploration : Algorithms, Competitive Analysis, and Computational Experiments (Julie Meißner)
PhD thesis, TU Berlin, 2018.
[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},
}

Randomization Helps Computing a Minimum Spanning Tree under Uncertainty (Nicole Megow, Julie Meißner and Martin Skutella)
SIAM J. Comput., 46(4):1217–1240, 2017.
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},
}
Protection of flows under targeted attacks (Jannik Matuschke, S. Thomas McCormick, Gianpaolo Oriolo, Britta Peis and Martin Skutella)
Oper. Res. Lett., 45(1):53–59, 2017.
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},
}
Optimal duty rostering for toll enforcement inspectors (Ralf Borndörfer, Guillaume Sagnol, Thomas Schlechte and Elmar Swarat)
Ann. Oper. Res., 252(2):383–406, 2017.
[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},
}
The structure of user equilibria: Dynamic coevolutionary simulations vs. cyclically expanded networks (Theresa Thunig and Kai Nagel)
Procedia Computer Science, 109:648–655, 2017.
[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 (Miriam Schlöter and Martin Skutella)
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 (Theresa Thunig and Kai Nagel)
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 (Martin Skutella, Maxim Sviridenko and Marc Uetz)
Math. Oper. Res., 41(3):851–864, 2016.
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 (Martin Skutella and José Verschae)
Math. Oper. Res., 41(3):991–1021, 2016.
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 (Nicole Megow, Martin Skutella, José Verschae and Andreas Wiese)
SIAM J. Comput., 45(3):859–880, 2016.
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 (Martin Skutella)
SIAM J. Discret. Math., 30(1):327–342, 2016.
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 (Martin Skutella)
Oper. Res. Lett., 44(5):676–679, 2016.
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 (Theresa Thunig and Kai Nagel)
Procedia Computer Science, 83:946–951, 2016.
[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 (Ralf Borndörfer, Sebastian Schenker, Martin Skutella and Timo Strunk)
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.), 2016.
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 (Ágnes Cseh)
PhD thesis, TU Berlin, 2016.
[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},
}

A tight bound on the speed-up through storage for quickest multi-commodity flows (Martin Groß and Martin Skutella)
Oper. Res. Lett., 43(1):93–95, 2015.
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 (Ashwin Arulselvan, Martin Groß and Martin Skutella)
Networks, 66(3):196–209, 2015.
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},
}
An incremental algorithm for the uncapacitated facility location problem (Ashwin Arulselvan, Olaf Maurer and Martin Skutella)
Networks, 65(4):306–311, 2015.
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},
}
Robust randomized matchings (Jannik Matuschke, Martin Skutella and José A. Soto)
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},
}
The Simplex Algorithm is NP-Mighty (Yann Disser and Martin Skutella)
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},
}
A note on the ring loading problem (Martin Skutella)
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},
}
Randomization Helps Computing a Minimum Spanning Tree under Uncertainty (Nicole Megow, Julie Meißner and Martin Skutella)
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},
}
Node-Balancing by Edge-Increments (Friedrich Eisenbrand, Shay Moran, Rom Pinchasi and Martin Skutella)
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},
}
Convex Quadratic Programming in Scheduling (Martin Skutella)
Chapter in Gems of Combinatorial Optimization and Graph Algorithms, 2015.
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.), 2015.
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.), 2015.
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 (Mohsen Rezapour)
PhD thesis, TU Berlin, 2015.
[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 (Jan-Philipp Kappmeier)
PhD thesis, TU Berlin, 2015.
[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 (Melanie Schmidt and Martin Skutella)
Discret. Appl. Math., 164:320–327, 2014.
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 (Martin Skutella, Maxim Sviridenko and Marc Uetz)
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 (Ágnes Cseh and Martin Skutella)
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 (Ashwin Arulselvan, Martin Groß and Martin Skutella)
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 (Martin Groß)
PhD thesis, TU Berlin, 2014.
[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 (Wolfgang Welz)
PhD thesis, TU Berlin, 2014.
[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 (Ágnes Cseh, Jannik Matuschke and Martin Skutella)
Algorithms, 6(3):532–545, 2013.
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},
}
Algorithms and Linear Programming Relaxations for Scheduling Unrelated Parallel Machines (Martin Skutella)
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},
}
Task assignment, sequencing and path-planning in robotic welding cells (Chantal Landry, René Henrion, Dietmar Hömberg, Martin Skutella and Wolfgang Welz)
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},
}
Benefits of Sexual Reproduction in Evolutionary Computation (Madeleine Friedrich)
PhD thesis, TU Berlin, 2013.
[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},
}
Network Flows and Network Design in Theory and Practice (Jannik Matuschke)
PhD thesis, TU Berlin, 2013.
[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},
}

Universal Sequencing on an Unreliable Machine (Leah Epstein, Asaf Levin, Alberto Marchetti-Spaccamela, Nicole Megow, Julián Mestre, Martin Skutella and Leen Stougie)
SIAM J. Comput., 41(3):565–586, 2012.
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 Preemption on Unrelated Machines and Applications to Scheduling Orders (José R. Correa, Martin Skutella and José Verschae)
Math. Oper. Res., 37(2):379–398, 2012.
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},
}
The Power of Recourse for Online MST and TSP (Nicole Megow, Martin Skutella, José Verschae and Andreas Wiese)
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 (Martin Groß and Martin Skutella)
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 (Sandro Bosio, Jan-Philipp W. Kappmeier, Jannik Matuschke, Britta Peis and Martin Skutella)
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},
}
Routing Games over Time (Ronald Koch)
PhD thesis, TU Berlin, 2012.
[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 (José Verschae)
PhD thesis, TU Berlin, 2012.
Bibtex
@phdthesis{ThesisVerschae2012,
title = {The Power of Recourse in Online Optimization},
author = {Verschae, José},
year = {2012},
type = {Doctoral Thesis},
school = {TU Berlin},
}
Network Flow Problems Arising From Evacuation Planning (Daniel Dressler)
PhD thesis, TU Berlin, 2012.
[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},
}

Computing Minimum Cuts by Randomized Search Heuristics (Frank Neumann, Joachim Reichel and Martin Skutella)
Algorithmica, 59(3):323–342, 2011.
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 (Ronald Koch, Ebrahim Nasrabadi and Martin Skutella)
Math. Methods Oper. Res., 73(3):301–337, 2011.
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 (Martin Skutella and David P. Williamson)
Oper. Res. Lett., 39(6):433–436, 2011.
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 (Ronald Koch and Martin Skutella)
Theory Comput. Syst., 49(1):71–97, 2011.
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 (Friedrich Eisenbrand, Martin Niemeier, Martin Skutella, José Verschae and Andreas Wiese)
it – Inf. Technol., 53(6):274–279, 2011.
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 (Martin Groß and Martin Skutella)
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 (Katharina Skutella and Martin Skutella)
Chapter in Algorithms Unplugged, 2011.
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 (Andreas Wiese)
PhD thesis, TU Berlin, 2011.
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 (Martin Skutella and Alexia Weber)
Math. Program., 124(1-2):441–454, 2010.
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 (Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondrej Pangrác, Heiko Schilling and Martin Skutella)
ACM Trans. Algorithms, 7(1):4:1–4:27, 2010.
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 (Joachim Reichel and Martin Skutella)
Algorithmica, 57(1):187–206, 2010.
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 (Melanie Schmidt and Martin Skutella)
Electron. Notes Discret. Math., 36:607–614, 2010.
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},
}
Scheduling Periodic Tasks in a Hard Real-Time Environment (Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, José Verschae and Andreas Wiese)
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},
}
Universal Sequencing on a Single Machine (Leah Epstein, Asaf Levin, Alberto Marchetti-Spaccamela, Nicole Megow, Julián Mestre, Martin Skutella and Leen Stougie)
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},
}
Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods (Friedrich Eisenbrand, Karthikeyan Kesavan, Raju S. Mattikalli, Martin Niemeier, Arnold W. Nordsieck, Martin Skutella, José Verschae and Andreas Wiese)
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},
}
A Robust PTAS for Machine Covering and Packing (Martin Skutella and José Verschae)
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},
}
Packet Routing on the Grid (Britta Peis, Martin Skutella and Andreas Wiese)
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 (Daniel Dressler and Martin Skutella)
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},
}
Optimal Evacuation Solutions for Large-Scale Scenarios (Daniel Dressler, Gunnar Flötteröd, Gregor Lämmel, Kai Nagel and Martin Skutella)
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},
}
Route Planning for Robot Systems (Martin Skutella and Wolfgang Welz)
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},
}

Online Scheduling with Bounded Migration (Peter Sanders, Naveen Sivadasan and Martin Skutella)
Math. Oper. Res., 34(2):481–498, 2009.
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 (Nadine Baumann and Martin Skutella)
Math. Oper. Res., 34(2):499–512, 2009.
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 (Luca Becchetti, Alberto Marchetti-Spaccamela, Andrea Vitaletti, Peter Korteweg, Martin Skutella and Leen Stougie)
ACM Trans. Algorithms, 6(1):13:1–13:20, 2009.
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 (Friedrich Eisenbrand, Andreas Karrenbauer, Martin Skutella and Chihao Xu)
Algorithmica, 53(4):583–596, 2009.
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 (Maren Martens and Martin Skutella)
J. Comb. Optim., 18(3):272–293, 2009.
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 (Fernanda Salazar and Martin Skutella)
Oper. Res. Lett., 37(2):71–74, 2009.
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 (José R. Correa, Martin Skutella and José Verschae)
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 (Ronald Koch, Britta Peis, Martin Skutella and Andreas Wiese)
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 (Ronald Koch and Martin Skutella)
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 (Britta Peis, Martin Skutella and Andreas Wiese)
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 (Joachim Reichel and Martin Skutella)
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 (Ekkehard Köhler, Rolf H. Möhring and Martin Skutella)
Chapter in Algorithmics of Large and Complex Networks – Design, Analysis, and Simulation, 2009.
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 (Martin Skutella)
Chapter in Research Trends in Combinatorial Optimization (W. Cook, L. Lovász, J. Vygen, eds.), Springer, 2009.
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 (Ebrahim Nasrabadi)
PhD thesis, TU Berlin / Amirkabir University of Technology, 2009.
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 (Fabrizio Grandoni, Volker Kaibel, Gianpaolo Oriolo and Martin Skutella)
Oper. Res. Lett., 36(3):361–365, 2008.
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 (Ronald Koch, Martin Skutella and Ines Spenke)
Theory Comput. Syst., 43(1):56–66, 2008.
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},
}
Flows with unit path capacities and related packing and covering problems (Maren Martens and Martin Skutella)
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},
}
Computing minimum cuts by randomized search heuristics (Frank Neumann, Joachim Reichel and Martin Skutella)
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},
}
An Introduction to Network Flows over Time (Martin Skutella)
Chapter in Research Trends in Combinatorial Optimization, Bonn Workshop on Combinatorial Optimization, November 3-7, 2008, Bonn, Germany, 2008.
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},
}
Minimale aufspannende Bäume – Wenn das Naheliegende das Beste ist... (Katharina Skutella and Martin Skutella)
Chapter in Taschenbuch der Algorithmen, 2008.
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},
}
WAOA 2008 – Proc. 6th Workshop on Approximation and Online Algorithms (Evripidis Bampis, Martin Skutella, eds.), 2008.
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},
}

Quickest Flows Over Time (Lisa Fleischer and Martin Skutella)
SIAM J. Comput., 36(6):1600–1630, 2007.
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},
}
New Approaches for Virtual Private Network Design (Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo and Martin Skutella)
SIAM J. Comput., 37(3):706–721, 2007.
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},
}
An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times (Alexander Hall, Katharina Langkau and Martin Skutella)
Algorithmica, 47(3):299–321, 2007.
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 (Alexander Hall, Steffen Hippler and Martin Skutella)
Theor. Comput. Sci., 379(3):387–404, 2007.
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 (Maren Martens, Fernanda Salazar and Martin Skutella)
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.), 2007.
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},
}
Evacuation by Earliest Arrival Flows (Nadine Baumann)
PhD thesis, Universität Dortmund, 2007.
Bibtex
@phdthesis{ThesisBaumann07,
author = {Baumann, Nadine},
school = {Universität Dortmund},
title = {Evacuation by Earliest Arrival Flows},
type = {Doctoral Thesis},
year = {2007},
}
Path-Constrained Network Flows (Maren Martens)
PhD thesis, Universität Dortmund, 2007.
Bibtex
@phdthesis{ThesisMartens07,
author = {Martens, Maren},
school = {Universität Dortmund},
title = {Path-Constrained Network Flows},
type = {Doctoral Thesis},
year = {2007},
}

The Freeze-Tag Problem: How to Wake Up a Swarm of Robots (Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell and Martin Skutella)
Algorithmica, 46(2):193–221, 2006.
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 (Maren Martens and Martin Skutella)
Networks, 48(2):68–76, 2006.
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 (Nadine Baumann and Martin Skutella)
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 (Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondrej Pangrác, Heiko Schilling and Martin Skutella)
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},
}
Latency Constrained Aggregation in Sensor Networks (Luca Becchetti, Alberto Marchetti-Spaccamela, Andrea Vitaletti, Peter Korteweg, Martin Skutella and Leen Stougie)
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},
}
Multiline Addressing by Network Flow (Friedrich Eisenbrand, Andreas Karrenbauer, Martin Skutella and Chihao Xu)
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},
}
List Scheduling in Order of $\alpha$-Points on a Single Machine (Martin Skutella)
Chapter in Efficient Approximation and Online Algorithms – Recent Progress on Classical Combinatorial Optimization Problems and New Applications, 2006.
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 (Martin Skutella and Marc Uetz)
SIAM J. Comput., 34(4):788–802, 2005.
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 (Ekkehard Köhler and Martin Skutella)
SIAM J. Optim., 15(4):1185–1202, 2005.
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 (Georg Baier, Ekkehard Köhler and Martin Skutella)
Algorithmica, 42(3-4):231–248, 2005.
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 (Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos and Martin Skutella)
Oper. Res. Lett., 33(2):115–120, 2005.
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 (Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo and Martin Skutella)
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 (Ronald Koch, Martin Skutella and Ines Spenke)
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 (Maren Martens and Martin Skutella)
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 (Rolf H. Möhring, Martin Skutella and Frederik Stork)
SIAM J. Comput., 33(2):393–415, 2004.
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 (Michel X. Goemans and Martin Skutella)
J. Algorithms, 50(2):194–214, 2004.
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 (Peter Sanders, Naveen Sivadasan and Martin Skutella)
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 (Maren Martens and Martin Skutella)
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 (Han Hoogeveen, Martin Skutella and Gerhard J. Woeginger)
Math. Program., 94(2-3):361–374, 2003.
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 (Sándor P. Fekete, Martin Skutella and Gerhard J. Woeginger)
Inf. Process. Lett., 88(5):219–223, 2003.
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 (Lisa Fleischer and Martin Skutella)
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 (Alexander Hall, Steffen Hippler and Martin Skutella)
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 (Alexander Hall, Katharina Langkau and Martin Skutella)
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 (Martin Skutella)
Math. Program., 91(3):493–514, 2002.
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 (Andreas S. Schulz and Martin Skutella)
J. Sched., 5:121–133, 2002.
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 (Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella and Yaoguang Wang)
SIAM J. Discret. Math., 15(2):165–192, 2002.
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 (Andreas S. Schulz and Martin Skutella)
SIAM J. Discret. Math., 15(4):450–469, 2002.
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 (Ekkehard Köhler and Martin Skutella)
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 (Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell and Martin Skutella)
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 (Lisa Fleischer and Martin Skutella)
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 (Georg Baier, Ekkehard Köhler and Martin Skutella)
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 (Ekkehard Köhler, Katharina Langkau and Martin Skutella)
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 (Martin Skutella)
J. ACM, 48(2):206–242, 2001.
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 (Martin Skutella and Marc Uetz)
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 (Martin Skutella and Gerhard J. Woeginger)
Math. Oper. Res., 25(1):63–75, 2000.
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 (Martin Skutella)
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},
}
Cooperative facility location games (Michel X. Goemans and Martin Skutella)
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},
}
Forcing relations for AND/OR precedence constraints (Rolf H. Möhring, Martin Skutella and Frederik Stork)
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},
}
Preemptive Scheduling with Rejection (Han Hoogeveen, Martin Skutella and Gerhard J. Woeginger)
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 (Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein and Maxim Sviridenko)
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 (Martin Skutella and Gerhard J. Woeginger)
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 (Martin Skutella)
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 (Martin Skutella)
Math. Oper. Res., 23(4):909–929, 1998.
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 (Martin Skutella)
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 (Martin Skutella)
PhD thesis, TU Berlin, 1998.
[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 (Martin Skutella)
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 (Andreas S. Schulz and Martin Skutella)
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 (Andreas S. Schulz and Martin Skutella)
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 (Clemens Gröpl and Martin Skutella)
Chapter in Lectures on Proof Verification and Approximation Algorithms, 1997.
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},
}

Search

Filter by type

Filter by author

Filter by year

to appear

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

2000

1999

1998

1997