Forschungsbericht 2020

Algorithmen und Komplexität E-11

Leitung: Matthias Mnich

Institut auf TORE
Institutswebsite

Publikationen

• On the complexity of solving a decision problem with flow-depending costs: The case of the IJsselmeer dikes - Article
  Abiad, Aida; Gribling, Sander; Lahaye, Domenico; Mnich, Matthias; Regts, Guus; Vena, Luis; Verweij, Gerard; Zwaneveld, Peter
  Discrete Optimization (2020)
  Publisher DOI
  
  
• Scheduling with non-renewable resources: Minimizing the sum of completion times - inProceedings
  Bérczi, Kristóf; Király, Tamás; Omlor, Simon
  6th International Symposium on Combinatorial Optimization (ISCO 2020)
  Publisher DOI
  
  
• Stable matchings with covering constraints: a complete computational trichotomy - Article
  Mnich, Matthias; Schlotter, Ildikó
  Algorithmica (2020)
  Open Access Publisher DOI
  
  
• Recent advances in practical data reduction - inBook
  Abu-Khzam, Faisal; Lamm, Sebastian; Mnich, Matthias; Noe, Alexander; Schulz, Christian; Strash, Darren
  arXiv:2012.12594
  
  
• Engineering kernelization for maximum cut - inProceedings
  Ferizovic, Damir; Hespe, Damian; Lamm, Sebastian; Mnich, Matthias; Schulz, Christian; Strash, Darren
  22nd Symposium on Algorithm Engineering and Experiments (ALENEX 2020)
  Publisher DOI
  
  
• Dense Steiner problems: approximation algorithms and inapproximability - Preprint
  Karpinski, Marek; Lewandowski, Mateusz; Meesum, Syed Mohammad; Mnich, Matthias
  arXiv:2004.14102 (2020)
  
  
• Dynamic parameterized problems and algorithms - Article
  Alman, Josh; Mnich, Matthias; Vassilevska Williams, Virginia
  ACM transactions on algorithms (2020)
  Publisher DOI
  
  
• Voting and bribing in single-exponential time - Article
  Knop, Dušan; Koutecký, Martin; Mnich, Matthias
  ACM Transactions on Economics and Computation (2020)
  Publisher DOI
  
  
• Solving packing problems with few small items using rainbow matchings - inProceedings
  Bannach, Max; Berndt, Sebastian; Maack, Marten; Mnich, Matthias; Lassota, Alexandra; Rau, Malin; Skambath, Malte
  45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
  Open Access Publisher DOI
  
  
• Time- and space-optimal algorithm for the many-visits TSP - Article
  Berger, André; Kozma, László; Mnich, Matthias; Vincze, Roland
  ACM transactions on algorithms (2020)
  Publisher DOI
  
  
• A 3/2-approximation for the metric many-visits path TSP - Preprint
  Bérczi, Kristóf; Mnich, Matthias; Vincze, Roland
  arXiv:2007.11389 (2020)
  
  
• Odd Multiway Cut in Directed Acyclic Graphs - Article
  Chandrasekaran, Karthekeyan; Mnich, Matthias; Mozaffari, Sahand
  SIAM journal on discrete mathematics (2020)
  Publisher DOI
  
  
• Hitting long directed cycles is fixed-parameter tractable - inProceedings
  Göke, Alexander; Marx, Dániel; Mnich, Matthias
  International Colloquium on Automata, Languages, and Programming (ICALP 2020)
  Open Access Publisher DOI
  
  

Projekte

• Kernelisierung für große Datenmengen
  Deutsche Forschungsgemeinschaft (DFG); Laufzeit 2019 - 2021
  Projektleitung: Mnich, Matthias
  
  
• Multivariate Algorithmen für Scheduling mit hoher Multiplizität
  Deutsche Forschungsgemeinschaft (DFG); Laufzeit 2019 - 2021
  Projektleitung: Mnich, Matthias
  
  
• Probleme der Strukturellen und Chromatischen Graphentheorie
  Deutscher Akademischer Austauschdienst; Laufzeit 2019 - 2020
  Projektleitung: Schmidt, Jens M.
  
  
• Broadcasting Spannbäume - Ausfallsicheres Broadcasting durch Unabhängige Spannbäume
  Deutsche Forschungsgemeinschaft (DFG); Laufzeit 2018 - 2021
  Projektleitung: Schmidt, Jens M.