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 SanitÓ
Proceedings of the forty-second ACM symposium on Theory of computing, 583-592, 2010
3012010
The matching polytope has exponential extension complexity
T Rothvo▀
Journal of the ACM (JACM) 64 (6), 1-19, 2017
1892017
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
1762013
Some 0/1 polytopes need exponential size extended formulations
T Rothvo▀
Mathematical Programming 142 (1-2), 255-268, 2013
872013
Static-priority real-time scheduling: Response time computation is np-hard
F Eisenbrand, T Rothvo▀
2008 Real-Time Systems Symposium, 397-406, 2008
732008
Polynomiality for bin packing with a constant number of item types
MX Goemans, T Rothvo▀
Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discreteá…, 2014
652014
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
632010
Primal dual gives almost optimal energy-efficient online algorithms
NR Devanur, Z Huang
ACM Transactions on Algorithms (TALG) 14 (1), 1-30, 2017
602017
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
592008
Extended formulations for polygons
S Fiorini, T Rothvo▀, HR Tiwary
Discrete & computational geometry 48 (3), 658-668, 2012
582012
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
572013
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
502010
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 (3), 211-258, 2009
462009
The Lasserre hierarchy in approximation algorithms
T Rothvo▀
Lecture Notes for the MAPSP, 1-25, 2013
442013
Diameter of polyhedra: limits of abstraction
F Eisenbrand, N Hńhnle, T Rothvo▀
Proceedings of the twenty-fifth annual symposium on Computational geometryá…, 2009
422009
Constructive discrepancy minimization for convex sets
T Rothvoss
SIAM Journal on Computing 46 (1), 224-234, 2017
412017
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
382012
Directed Steiner tree and the Lasserre hierarchy
T Rothvo▀
arXiv preprint arXiv:1111.5473, 2011
352011
A logarithmic additive integrality gap for bin packing
R Hoberg, T Rothvoss
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discreteá…, 2017
312017
Pricing on paths: A ptas for the highway problem
F Grandoni, T Rothvo▀
SIAM Journal on Computing 45 (2), 216-231, 2016
312016
The system can't perform the operation now. Try again later.
Articles 1–20