Algorithmics and Computational Complexity
Curriculum Vitae
| March 2022 | Rolf Niedermeier unexpectedly passed away |
|---|---|
| 2010 - March 2022 | Chair Algorithmics and Computational Complexity, TU Berlin |
| 2004-2010 | Chair Theoretical Computer Science I, Friedrich-Schiller-Universität Jena |
| 2002-2004 | Head of Emmy Noether research group Eberhard-Karls-Universität Tübinge |
| 1999-2002 | Eberhard-Karls-Universität Tübingen (Prof. Lange) |
| 1998 | Charles University Prague (Prof. Nešetříl) |
| 1994-1997 | Eberhard-Karls-Universität Tübingen (Prof. Lange) |
| 1991-1994 | TU München (Prof. Brauer, Prof. Lange) |
Research projects
| started November 2021 | COMSOC-MPMS: Computational Social Choice: Multiple Preference Profiles and Multiple Solutions |
| started March 2021 | DiPa: The Art of Difference Parameterization in Multivariate Algorithmics |
| started April 2018 | MaMu: Matching under Preferences: Multimodal Views and Domain Restrictions |
| 2018 - 2022 | TORE: Trade-offs in Parameterized Data Reduction |
| 2018 - 2022 | MATE: Multivariate Algorithmics for Temporal Graph Problems |
| started December 2017 | FPTinP: More Efficient Algorithms for Polynomial-Time Solvable Graph Problems |
| started October 2016 | AFFA: Algorithms for Fair Allocations |
| 2012 - | DAMM: Data Reduction in Parameterized Algorithmics - New Models and Methods |
| 2012 - | DAPA: Data Driven Parameterized Algorithmics for Graph Modification Problems |
| 2010 - 2014 | DARE: Data Reduction and Problem Kernels |
| 2009 - 2017 | PAWS: Parameterized Algorithmics for Voting Systems |
| 2008 - 2013 | AREG: Algorithms for Generating Quasi-Regular Structures in Graphs |
| 2007 - 2014 | PABI: Parameterized Algorithmics for Bioinformatics |
Publications
2023
Boehmer,
Niclas;
Koana,
Tomohiro;
Niedermeier,
Rolf
A Refined Complexity Analysis of Fair Districting over Graphs
Autonomous Agents and Multi-Agent Systems, 37 (1) :13
2023
A Refined Complexity Analysis of Fair Districting over Graphs
Autonomous Agents and Multi-Agent Systems, 37 (1) :13
2023
Koana,
Tomohiro;
Froese,
Vincent;
Niedermeier,
Rolf
The Complexity of Binary Matrix Completion Under Diameter Constraints
Journal of Computer and System Sciences, 132 :45–67
2023
The Complexity of Binary Matrix Completion Under Diameter Constraints
Journal of Computer and System Sciences, 132 :45–67
2023
Bentert,
Matthias;
Bevern,
René;
Fluschnik,
Till;
Nichterlein,
André;
Niedermeier,
Rolf
Polynomial-time data reduction for weighted problems beyond additive goal functions
Discrete Applied Mathematics, 328 :117–133
2023
Polynomial-time data reduction for weighted problems beyond additive goal functions
Discrete Applied Mathematics, 328 :117–133
2023
2022
Bredereck,
Robert;
Kaczmarczyk,
Andrzej;
Luo,
Junjie;
Niedermeier,
Rolf;
Sachse,
Florian
On Improving Resource Allocations by Sharing
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22)
2022
On Improving Resource Allocations by Sharing
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22)
2022
Boehmer,
Niclas;
Faliszewski,
Piotr;
Niedermeier,
Rolf;
Szufa,
Stanisław;
Wąs,
Tomasz
Understanding Distance Measures Among Elections
Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI '22), Page 102–108
Publisher: ijcai.org
2022
Understanding Distance Measures Among Elections
Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI '22), Page 102–108
Publisher: ijcai.org
2022
Figiel,
Aleksander;
Froese,
Vincent;
Nichterlein,
André;
Niedermeier,
Rolf
There and Back Again: On Applying Data Reduction Rules by Undoing Others
, Proceedings of the 30th Annual European Symposium on Algorithms (ESA '22)Volume244fromLeibniz International Proceedings in Informatics (LIPIcs), Page 53:1–53:15
Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2022
There and Back Again: On Applying Data Reduction Rules by Undoing Others
, Proceedings of the 30th Annual European Symposium on Algorithms (ESA '22)Volume244fromLeibniz International Proceedings in Informatics (LIPIcs), Page 53:1–53:15
Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2022
Boehmer,
Niclas;
Heeger,
Klaus;
Niedermeier,
Rolf
Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), Page 4851–4858
2022
Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), Page 4851–4858
2022
Bredereck,
Robert;
Heeger,
Klaus;
Knop,
Dušan;
Niedermeier,
Rolf
Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
Information and Computation :104943
2022
ISSN: 0890-5401
Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
Information and Computation :104943
2022
ISSN: 0890-5401
Bentert,
Matthias;
Bevern,
René;
Nichterlein,
André;
Niedermeier,
Rolf;
Smirnov,
Pavel V.
Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
Informs Journal on Computing, 34 (1) :55--75
2022
Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
Informs Journal on Computing, 34 (1) :55--75
2022
Froese,
Vincent;
Hertrich,
Christoph;
Niedermeier,
Rolf
The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
Journal of Artificial Intelligence Research, 74 :1775–1790
2022
The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
Journal of Artificial Intelligence Research, 74 :1775–1790
2022
Fluschnik,
Till;
Kunz,
Pascal;
Niedermeier,
Rolf;
Renken,
Malte
Most Classic Problems Remain NP-hard on Relative Neighborhood Graphs and their Relatives
Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '22)
2022
Most Classic Problems Remain NP-hard on Relative Neighborhood Graphs and their Relatives
Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '22)
2022
Heeger,
Klaus;
Hermelin,
Danny;
Mertzios,
George B.;
Molter,
Hendrik;
Niedermeier,
Rolf;
Shabtay,
Dvir
Equitable Scheduling on a Single Machine
Journal of Scheduling
2022
Publisher: Springer
Equitable Scheduling on a Single Machine
Journal of Scheduling
2022
Publisher: Springer
Kreisel,
Luca;
Boehmer,
Niclas;
Froese,
Vincent;
Niedermeier,
Rolf
Equilibria in Schelling Games: Computational Hardness and Robustness
Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS '22), Page 761–769
Publisher: IFAAMAS
2022
Equilibria in Schelling Games: Computational Hardness and Robustness
Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS '22), Page 761–769
Publisher: IFAAMAS
2022
Boehmer,
Niclas;
Heeger,
Klaus;
Niedermeier,
Rolf
Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
, Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS '22)Volume241fromLIPIcs, Page 21:1–21:15
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2022
Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
, Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS '22)Volume241fromLIPIcs, Page 21:1–21:15
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2022
Schulz,
Hjalmar;
Nichterlein,
André;
Niedermeier,
Rolf;
Weyand,
Christopher
Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time
, Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC 22)Volume249fromLeibniz International Proceedings in Informatics (LIPIcs), Page 25:1–25:14
Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2022
Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time
, Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC 22)Volume249fromLeibniz International Proceedings in Informatics (LIPIcs), Page 25:1–25:14
Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2022
Boehmer,
Niclas;
Koana,
Tomohiro;
Niedermeier,
Rolf
A Refined Complexity Analysis of Fair Districting over Graphs
Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS '22), Page 1548–1550
Publisher: IFAAMAS
2022
A Refined Complexity Analysis of Fair Districting over Graphs
Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS '22), Page 1548–1550
Publisher: IFAAMAS
2022
Boehmer,
Niclas;
Bredereck,
Robert;
Faliszewski,
Piotr;
Niedermeier,
Rolf
A Quantitative and Qualitative Analysis of the Robustness of (Real-World) Election Winners
Proceedings of the Second Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO '22), Page 7:1–7:10
Publisher: ACM
2022
A Quantitative and Qualitative Analysis of the Robustness of (Real-World) Election Winners
Proceedings of the Second Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO '22), Page 7:1–7:10
Publisher: ACM
2022
Froese,
Vincent;
Kellerhals,
Leon;
Niedermeier,
Rolf
Modification-Fair Cluster Editing
, Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22)Volume36, Page 6631–6638
2022
Modification-Fair Cluster Editing
, Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22)Volume36, Page 6631–6638
2022
2021
Bredereck,
Robert;
Faliszewski,
Piotr;
Kaczmarczyk,
Andrzej;
Niedermeier,
Rolf;
Skowron,
Piotr;
Talmon,
Nimrod
Robustness among multiwinner voting rules
Artificial Intelligence, 290 :103403
2021
Robustness among multiwinner voting rules
Artificial Intelligence, 290 :103403
2021
Figiel,
Aleksander;
Kellerhals,
Leon;
Niedermeier,
Rolf;
Rost,
Matthias;
Schmid,
Stefan;
Zschoche,
Philipp
Optimal Virtual Network Embeddings for Tree Topologies
Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architechtures
Publisher: ACM
2021
Optimal Virtual Network Embeddings for Tree Topologies
Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architechtures
Publisher: ACM
2021
Luo,
Junjie;
Molter,
Hendrik;
Nichterlein,
André;
Niedermeier,
Rolf
Parameterized Dynamic Cluster Editing
Algorithmica, 83 (1) :1–44
2021
Publisher: Springer
Parameterized Dynamic Cluster Editing
Algorithmica, 83 (1) :1–44
2021
Publisher: Springer
Boehmer,
Niclas;
Bredereck,
Robert;
Faliszewski,
Piotr;
Niedermeier,
Rolf;
Szufa,
Stanislaw
Putting a Compass on the Map of Elections
Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI '21), Page 59–65
Publisher: ijcai.org
2021
Putting a Compass on the Map of Elections
Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI '21), Page 59–65
Publisher: ijcai.org
2021
Boehmer,
Niclas;
Bredereck,
Robert;
Faliszewski,
Piotr;
Niedermeier,
Rolf
Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments
Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI '21), Page 52–58
Publisher: ijcai.org
2021
Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments
Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI '21), Page 52–58
Publisher: ijcai.org
2021
Bentert,
Matthias;
Koana,
Tomohiro;
Niedermeier,
Rolf
The Complexity of Gerrymandering over Graphs: Paths and Trees
Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science, Page 195–206
2021
The Complexity of Gerrymandering over Graphs: Paths and Trees
Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science, Page 195–206
2021
Rymar,
Maciej;
Molter,
Hendrik;
Nichterlein,
André;
Niedermeier,
Rolf
Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality
, Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '21)Volume12911fromLecture Notes in Computer Science, Page 219–231
Publisher: Springer
2021
Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality
, Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '21)Volume12911fromLecture Notes in Computer Science, Page 219–231
Publisher: Springer
2021