Follow
Thomas Rothvoss
Thomas Rothvoss
University of Washington
Verified email at math.mit.edu
Title
Cited by
Cited by
Year
An improved LP-based approximation for Steiner tree
J Byrka, F Grandoni, T Rothvoß, L Sanita
Proceedings of the forty-second ACM symposium on Theory of computing, 583-592, 2010
3922010
Steiner tree approximation via iterative randomized rounding
J Byrka, F Grandoni, T Rothvoß, L Sanità
Journal of the ACM (JACM) 60 (1), 1-33, 2013
3132013
The matching polytope has exponential extension complexity
T Rothvoß
Journal of the ACM (JACM) 64 (6), 1-19, 2017
2642017
Static-priority real-time scheduling: Response time computation is NP-hard
F Eisenbrand, T Rothvoß
2008 Real-Time Systems Symposium, 397-406, 2008
1082008
Some 0/1 polytopes need exponential size extended formulations
T Rothvoß
Mathematical Programming 142 (1), 255-268, 2013
1062013
Polynomiality for bin packing with a constant number of item types
MX Goemans, T Rothvoß
Journal of the ACM (JACM) 67 (6), 1-21, 2020
1032020
Constructive discrepancy minimization for convex sets
T Rothvoss
SIAM Journal on Computing 46 (1), 224-234, 2017
992017
EDF-schedulability of synchronous periodic task systems is coNP-hard
F Eisenbrand, T Rothvoß
Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete …, 2010
972010
Approximating bin packing within O (log OPT· log log OPT) bins
T Rothvoß
2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 20-29, 2013
902013
A logarithmic additive integrality gap for bin packing
R Hoberg, T Rothvoss
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete …, 2017
892017
Matroids and integrality gaps for hypergraphic steiner tree relaxations
MX Goemans, N Olver, T Rothvoß, R Zenklusen
Proceedings of the forty-fourth annual ACM symposium on Theory of computing …, 2012
752012
Extended formulations for polygons
S Fiorini, T Rothvoß, HR Tiwary
Discrete & computational geometry 48 (3), 658-668, 2012
702012
Approximating connected facility location problems via random facility sampling and core detouring
F Eisenbrand, F Grandoni, T Rothvoß, G Schäfer
Proceeding of Nineteenth annual ACM-SIAM Symposium (SODA'08), 1174-1183, 2008
702008
Deterministic discrepancy minimization via the multiplicative weight update method
A Levy, H Ramadas, T Rothvoss
International Conference on Integer Programming and Combinatorial …, 2017
672017
Connected facility location via random facility sampling and core detouring
F Eisenbrand, F Grandoni, T Rothvoß, G Schäfer
Journal of Computer and System Sciences 76 (8), 709-726, 2010
592010
The Lasserre hierarchy in approximation algorithms
T Rothvoß
Lecture Notes for the MAPSP, 1-25, 2013
552013
Directed steiner tree and the lasserre hierarchy
T Rothvoß
arXiv preprint arXiv:1111.5473, 2011
542011
Diameter of polyhedra: limits of abstraction
F Eisenbrand, N Hähnle, T Rothvoß
Proceedings of the twenty-fifth annual symposium on Computational geometry …, 2009
512009
Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling
RI Davis, T Rothvoß, SK Baruah, A Burns
Real-Time Systems 43, 211-258, 2009
502009
A (1+ epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
E Levey, T Rothvoss
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016
492016
The system can't perform the operation now. Try again later.
Articles 1–20