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 war Packard Fellow (2016) und Sloan Research Fellow.
Schriften (Auswahl)
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
Einzelnachweise und Anmerkungen
↑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