Thomas Rothvoss
Thomas Rothvoss
University of Washington
Verified email at
Cited by
Cited by
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
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
The matching polytope has exponential extension complexity
T Rothvo▀
Journal of the ACM (JACM) 64 (6), 1-19, 2017
Some 0/1 polytopes need exponential size extended formulations
T Rothvo▀
Mathematical Programming 142 (1-2), 255-268, 2013
Static-priority real-time scheduling: Response time computation is NP-hard
F Eisenbrand, T Rothvo▀
2008 Real-Time Systems Symposium, 397-406, 2008
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
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
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
Constructive discrepancy minimization for convex sets
T Rothvoss
SIAM Journal on Computing 46 (1), 224-234, 2017
A logarithmic additive integrality gap for bin packing
R Hoberg, T Rothvoss
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discreteá…, 2017
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
Extended formulations for polygons
S Fiorini, T Rothvo▀, HR Tiwary
Discrete & computational geometry 48 (3), 658-668, 2012
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
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
Deterministic discrepancy minimization via the multiplicative weight update method
A Levy, H Ramadas, T Rothvoss
International Conference on Integer Programming and Combinatorialá…, 2017
The Lasserre hierarchy in approximation algorithms
T Rothvo▀
Lecture Notes for the MAPSP, 1-25, 2013
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
Diameter of polyhedra: limits of abstraction
F Eisenbrand, N Hńhnle, T Rothvo▀
Proceedings of the twenty-fifth annual symposium on Computational geometryá…, 2009
Directed steiner tree and the lasserre hierarchy
T Rothvo▀
arXiv preprint arXiv:1111.5473, 2011
Pricing on paths: A ptas for the highway problem
F Grandoni, T Rothvo▀
SIAM Journal on Computing 45 (2), 216-231, 2016
The system can't perform the operation now. Try again later.
Articles 1–20