Thomas Rothvoß

Thomas Rothvoß, auch Rothvoss, (* 1981) ist ein deutscher Informatiker und Mathematiker.

Rothvoß studierte von 2002 bis 2006 Informatik an der TU Dortmund (Diplom bei Friedrich Eisenbrand: Algorithms for virtual private networks), setzte sein Studium in Paderborn und an der EPFL in Lausanne fort, an der er 2009 bei Eisenbrand promoviert wurde (On the computational complexity of periodic scheduling). Ab 2011 war er als Post-Doktorand bei Michel X. Goemans am Massachusetts Institute of Technology (als Feodor Lynen Stipendiat), an dem er 2013 Instructor wurde. 2014 wurde er Assistant Professor an der University of Washington in Seattle, sowohl in der Fakultät für Mathematik als auch der für Informatik.

Er befasst sich mit linearer und ganzzahliger Programmierung, Kombinatorik (zum Beispiel Scheduling), theoretischer Informatik (Komplexitätstheorie), Netzwerk-Entwurf, Näherungsalgorithmen (zum Beispiel beim Steinerbaumproblem) und diskreter Optimierung. 2014 löste er ein schwieriges Problem über die Erweiterungskomplexität^[1] der konvexen Hülle aller Matchings eines Graphen mit n Knoten. Er zeigte, dass diese nicht polynomial in n ist, sondern exponentiell.

2018 erhielt er den Fulkerson-Preis, 2023 den Gödel-Preis.

Er war Packard Fellow (2016) und Sloan Research Fellow.

• mit Eisenbrand, Grandoni, Guido Schäfer: Approximating connected facility location problems via random facility sampling and core detouring, SODA 2008
• mit F. Eisenbrand: Static-priority real-time scheduling: Response time computation is NP-hard, Real-Time Systems Symposium, 2008, S. 397–406
• mit F. Eisenbrand: EDF-schedulability of synchronous periodic task systems is coNP-hard, SODA 2010, S. 1029–1034
• mit J. Byrka, F. Grandoni, L. Sanità: An Improved LP-based Approximation for Steiner Tree, STOC 2010, S. 583–592 (STOC 2010 Best Paper Award)
• mit S. Fiorini, H. Tiwary: Extended formulations for polygons, Discrete & Computational Geometry, Band 48, Nr. 3, 2012, S. 658–668, Arxiv
• mit Goemans, Olver, Zenklusen: Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations, STOC 2012, S. 1161–1176
• mit J. Byrka, F. Grandoni, L. Sanità: Steiner tree approximation via iterative randomized rounding, Journal of the ACM (JACM), Band 60, Heft 1, 2013, S. 6
• The matching polytope has exponential extension complexity, ACM Symposium on the Theory of Computing (STOC) 2014 (STOC 2014 Best Paper Prize), Arxiv, veröffentlicht auch in J. Journal of the ACM (JACM), Band 64, 2017, Heft 6, S. 41
• mit Goemans: Polynomiality for Bin Packing with a Constant Number of Item Types, Symposium on Discrete Algorithms (SODA) 2014, (SODA Best Paper Award 2014), Arxiv
• Constructive discrepancy minimization for convex sets, Foundations of Computer Science (FOCS) 2014, Arxiv
• mit Rebecca Hoberg: An Improved Deterministic Rescaling for Linear Programming Algorithms, IPCO 2017, Arxiv 2016

• Homepage an der University of Washington

1. ↑ Die Erweiterung eines Polytops P ist ein Polytop Q zusammen mit affinen oder projektiven Abbildungen von Q auf P und die Komplexität der Erweiterung ist die minimale Anzahl der Seiten von Q