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 | 392 | 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 | 313 | 2013 |
The matching polytope has exponential extension complexity T Rothvoß Journal of the ACM (JACM) 64 (6), 1-19, 2017 | 264 | 2017 |
Static-priority real-time scheduling: Response time computation is NP-hard F Eisenbrand, T Rothvoß 2008 Real-Time Systems Symposium, 397-406, 2008 | 108 | 2008 |
Some 0/1 polytopes need exponential size extended formulations T Rothvoß Mathematical Programming 142 (1), 255-268, 2013 | 106 | 2013 |
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 | 102 | 2020 |
Constructive discrepancy minimization for convex sets T Rothvoss SIAM Journal on Computing 46 (1), 224-234, 2017 | 99 | 2017 |
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 | 95 | 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 | 90 | 2013 |
A logarithmic additive integrality gap for bin packing R Hoberg, T Rothvoss Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete …, 2017 | 89 | 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 | 75 | 2012 |
Extended formulations for polygons S Fiorini, T Rothvoß, HR Tiwary Discrete & computational geometry 48 (3), 658-668, 2012 | 70 | 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 | 70 | 2008 |
Deterministic discrepancy minimization via the multiplicative weight update method A Levy, H Ramadas, T Rothvoss International Conference on Integer Programming and Combinatorial …, 2017 | 67 | 2017 |
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 | 59 | 2010 |
The Lasserre hierarchy in approximation algorithms T Rothvoß Lecture Notes for the MAPSP, 1-25, 2013 | 55 | 2013 |
Directed steiner tree and the lasserre hierarchy T Rothvoß arXiv preprint arXiv:1111.5473, 2011 | 54 | 2011 |
Diameter of polyhedra: limits of abstraction F Eisenbrand, N Hähnle, T Rothvoß Proceedings of the twenty-fifth annual symposium on Computational geometry …, 2009 | 51 | 2009 |
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 | 50 | 2009 |
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 | 49 | 2016 |