Algorithmik und Komplexitätstheorie

Konferenzen

2023

K. Heeger, A. Nichterlein and R. Niedermeier, "Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions" in Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS 23), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. pp. 35:1–35:19.
V. Froese and C. Hertrich, "Training Neural Networks is NP-Hard in Fixed Dimension" in 37th Conference on Neural Information Processing Systems (NeurIPS '23), 2023.

2022

V. Froese, L. Kellerhals and R. Niedermeier, "Modification-Fair Cluster Editing" in Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), 2022. pp. 6631–6638.
L. Kellerhals, T. Koana and P. Kunz, "Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees" in Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC 22), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. pp. 19:1–19:14.
N. Boehmer, P. Faliszewski, R. Niedermeier, S. Szufa and T. Wąs, "Understanding Distance Measures Among Elections" in Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI '22), ijcai.org, 2022. pp. 102–108.
A. Figiel, V. Froese, A. Nichterlein and R. Niedermeier, "There and Back Again: On Applying Data Reduction Rules by Undoing Others" in Proceedings of the 30th Annual European Symposium on Algorithms (ESA '22), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. pp. 53:1–53:15.
N. Boehmer, K. Heeger and R. Niedermeier, "Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets" in Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), 2022. pp. 4851–4858.
N. Boehmer and T. Koana, "The Complexity of Finding Fair Many-to-One Matchings" in Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP '22), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. pp. 27:1–27:18.
M. Bentert, N. Boehmer, K. Heeger and T. Koana, "Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences" in Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT '22), Springer, 2022. pp. 436–453.
N. Boehmer, M. Brill and U. Schmidt-Kraepelin, "Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous Preferences" in Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS '22), IFAAMAS, 2022. pp. 136–144.
N. Boehmer, R. Bredereck, K. Heeger, D. Knop and J. Luo, "Multivariate Algorithmics for Eliminating Envy by Donating Goods" in Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS '22), IFAAMAS, 2022. pp. 127–135.
T. Fluschnik, P. Kunz, R. Niedermeier and M. Renken, "Most Classic Problems Remain NP-hard on Relative Neighborhood Graphs and their Relatives" in Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '22), 2022.
R. Bredereck, A. Kaczmarczyk, J. Luo, R. Niedermeier and F. Sachse, "On Improving Resource Allocations by Sharing" in Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), 2022.
N. Boehmer, R. Bredereck, E. Elkind, P. Faliszewski and S. Szufa, "Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning" in Proceedings of the Thirty-sixth Conference on Neural Information Processing Systems (NeurIPS '22), 2022.
T. Fluschnik and P. Kunz, "Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring" in Proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND '22), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. pp. 16:1–16:18.
N. Boehmer, K. Heeger and S. Szufa, "A Map of Diverse Synthetic Stable Roommates Instances" in Proceedings of the 6th International Workshop on Matching Under Preferences (MATCH-UP '22), 2022.
N. Boehmer, R. Bredereck, P. Faliszewski and R. Niedermeier, "A Quantitative and Qualitative Analysis of the Robustness of (Real-World) Election Winners" in Proceedings of the Second Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO '22), ACM, 2022. pp. 7:1–7:10.
L. Kreisel, N. Boehmer, V. Froese and R. Niedermeier, "Equilibria in Schelling Games: Computational Hardness and Robustness" in Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS '22), IFAAMAS, 2022. pp. 761–769.
H. Schulz, A. Nichterlein, R. Niedermeier and C. Weyand, "Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time" in Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC 22), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. pp. 25:1–25:14.
N. Boehmer, T. Koana and R. Niedermeier, "A Refined Complexity Analysis of Fair Districting over Graphs" in Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS '22), IFAAMAS, 2022. pp. 1548–1550.
N. Boehmer and N. Schaar, "Collecting, Classifying, Analyzing, and Utilizing Real-World Elections" in 3rd Games, Agents, and Incentives Workshop (GAIW '22), 2022.
N. Boehmer, R. Bredereck and A. Nichterlein, "Combating Collusion Rings is Hard but Possible" in Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), 2022. pp. 4843–4850.
T. Koana, C. Komusiewicz, A. Nichterlein and F. Sommer, "Covering Many (Or Few) Edges with k Vertices in Sparse Graphs" in Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 22), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. pp. 42:1–42:18.
N. Boehmer, K. Heeger and R. Niedermeier, "Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems" in Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS '22), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. pp. 21:1–21:15.
V. Froese, P. Kunz and P. Zschoche, "Disentangling the Computational Complexity of Network Untangling" in Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI '22), International Joint Conferences on Artificial Intelligence Organization, 2022. pp. 2037–2043.