Research at the interface of Discrete Mathematics, Theoretical Computer Science, and Operations Research,
with emphasis on:
- Unsplittable Transshipments (Srinwanti Debgupta, Sarah Morell, and Martin Skutella)
ICALP 2026 – Proc. 53rd International Colloquium on Automata, Languages and Programming.
@inproceedings{DebguptaMorellSkutella26,
author = {Debgupta, Srinwanti and Morell, Sarah and Skutella, Martin},
booktitle = {ICALP 2026 – Proc. 53rd International Colloquium on Automata, Languages and Programming},
title = {Unsplittable Transshipments},
year = {2026},
}
- Integer and Unsplittable Multiflows in Series-Parallel Digraphs (Mohammed Majthoub Almoghrabi, Martin Skutella, and Philipp Warode)
IPCO 2025 – Proc. 26th Conference on Integer Programming and Combinatorial Optimization, Springer, pp. 427–441.
@inproceedings{MajthoubSkutellaWarode2025,
author = {Almoghrabi, Mohammed Majthoub and Skutella, Martin and Warode, Philipp},
editor = {Nicole Megow and
Amitabh Basu},
title = {Integer and Unsplittable Multiflows in Series-Parallel Digraphs},
booktitle = {IPCO 2025 – Proc. 26th Conference on Integer Programming and Combinatorial Optimization},
pages = {427--441},
year = {2025},
doi = {10.1007/978-3-031-93112-3_31},
publisher = {Springer},
}
- Complexity of Injectivity and Verification of ReLU Neural Networks (Vincent Froese, Moritz Grillo, and Martin Skutella)
COLT 2025 – Proc. 38th Conference on Learning Theory, PMLR, pp. 2188–2189.
@inproceedings{FroeseGrilloSkutella2025,
author = {Froese, Vincent and
Grillo, Moritz and
Skutella, Martin},
editor = {Haghtalab, Nika and
Moitra, Ankur},
title = {Complexity of Injectivity and Verification of ReLU Neural Networks},
booktitle = {COLT 2025 – Proc. 38th Conference on Learning Theory},
series = {Proceedings of Machine Learning Research},
volume = {291},
pages = {2188--2189},
publisher = {{PMLR}},
year = {2025},
url = {https://proceedings.mlr.press/v291/froese25a.html},
}
- Towards Lower Bounds on the Depth of ReLU Neural Networks (Chistoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella)
SIAM J. Discret. Math., 37(2):997–1029, 2023.
Extended abstract appeared in Proc. of NeurIPS 2021
@article{HertrichBasuDiSumma+2023,
author = {Hertrich, Chistoph and Basu, Amitabh and Di Summa, Marco and Skutella, Martin},
title = {Towards Lower Bounds on the Depth of ReLU Neural Networks},
journal = {SIAM J. Discret. Math.},
volume = {37},
number = {2},
pages = {997--1029},
year = {2023},
doi = {10.1137/22M1489332},
}
- 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.
@inproceedings{SchloeterSkutTran2022,
author = {Schl\"oter, Miriam and Skutella, Martin and Tran, Khai Van},
booktitle = {SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms},
pages = {90--102},
doi = {10.1137/1.9781611977073.5},
title = {A Faster Algorithm for Quickest Transshipments via an Extended Discrete {N}ewton Method},
year = {2022},
}
- The 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
@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},
}
- 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
@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},
}
- 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
@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},
}
- 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
@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},
}
- 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
@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},
}
0000-0002-9814-1703
Bibliografie auf dblp
Google Scholar