[ publications ]
2017
 An improved deterministic rescaling for linear programming algorithms. R. Hoberg and T. Rothvoss. IPCO 2017 (Arxiv).

Deterministic discrepancy minimization
via the multiplicative weight update method
A. Levy, H. Ramadas, T. Rothvoss. IPCO 2017 (Arxiv)

Number Balancing is as hard as
Minkowski’s Theorem and Shortest Vector
R. Hoberg, H. Ramadas, T. Rothvoss, X. Yang. IPCO 2017 (Arxiv)
2016
 A (1+ epsilon)approximation for makespan
scheduling with precedence constraints using LP
hierarchies
E. Levey and T. Rothvoss. STOC'16 (Arxiv, slides).
2015
 A Logarithmic
Additive Integrality Gap for Bin Packing.
R. Hoberg and T. Rothvoss. Arxiv ID 1503.08796. Slides.
2014
 Constructive
discrepancy minimization for convex sets.
T. Rothvoss. FOCS 2014. Invited to the SICOMP Special Issue for FOCS'14. See also ArXiv ID 1404.0339. Slides. Video.
 The matching
polytope has exponential extension complexity
T. Rothvoß. STOC 2014. Winner of the STOC 2014 Best Paper Prize. See also ArXiv ID 1311.2369. Slides. Video.
 Polynomiality for
Bin Packing with a Constant Number of Item Types. M.X.
Goemans and T. Rothvoß.
SODA 2014 (Cowinner of Best Paper Award; invited to the Journal of the ACM, see also ArXiv ID 1307.5108. 2013). Slides. Video (talk given by my coauthor). 
A direct proof for
Lovett's bound on the communication complexity of low rank
matrices.
T. Rothvoss. Arxiv ID 1409.6366. Slides.
2013
 Approximating Bin
Packing within O(log OPT log log OPT) bins.
T. Rothvoß.
FOCS 2013. Invited to the SICOMP Special Issue for FOCS'13 (see also ArXiv ID 1301.4010. 2013). Slides. Video.
 Steiner
Tree Approximation via Iterative Randomized Rounding.
.
Invited submission to the Journal
of the ACM. Journal version of the STOC'10 paper.
Slides (short). Slides (long).  Bin Packing via Discrepancy of
Permutations. .
Invited submission to TALG SODA'11 special issue.
Remark: This is the journal version of the SODA'11 paper. Since the conjecture of Beck has been disproven few months after SODA'11 by Newman and Nikolov, I recommend to read this journal version instead of the original SODA paper.  A simpler proof
for O(congestion + dilation) packet routing.
T. Rothvoß. IPCO 2013. Slides.
 0/1 Polytopes with
Quadratic Chvátal Rank.
T. Rothvoß and L. Sani Slides.
2012
 Matroids and
Integrality Gaps for Hypergraphic Steiner Tree Relaxations.
M. X. Goemans, N. Olver, T. Rothvoss, R. Zenklusen. STOC'12.  The
Entropy
Rounding Method in Approximation Algorithms.
T. Rothvoss. Symposium on Discrete Algorithms (SODA 2012), Kyoto, Japan, January 1719, 2011. Slides (short). Slides (long).  Extended
formulations for polygons.
S. Fiorini, T. Rothvoß, H. Raj Tiwary. Discrete & Computational Geometry. 2012.  Some 0/1
polytopes need exponential size extended formulations.
T. Rothvoss. Mathematical Programming. 2012. Slides.
2011
 CoverDecomposition
and Polychromatic Numbers
B. Bollobás, D. Pritchard, T. Rothvoß, A. Scott
19th Annual European Symposium on Algorithms (ESA 2011), Saarbrücken, Germany, 5.9. September, 2011.  A PTAS for the Highway Problem. . Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 2225, 2011. Slides.
 Bin Packing via Discrepancy of Permutations. . Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 2225, 2011. Slides.
 From
Uncertainty to Nonlinearity: Solving Virtual Private
Network via SingleSink BuyatBulk. F. Grandoni, T.
Rothvoß and L. Sanit.
Math. Oper. Res. 36(2): 185204 (2011).
Combined journal version of the APPROX'09 and ICALP'10 paper.  Set Covering with Ordered Replacement: Additive and Multiplicative Gaps. F. Eisenbrand, N. Kakimura, T. Rothvoß, L. Sanit. IPCO 2011.
 Approximation Algorithms for Single and MultiCommodity Connected Facility Location. F. Grandoni and Thomas Rothvoß. IPCO 2011. Slides.
 Directed Steiner Tree and the Lasserre Hierarchy. T. Rothvoss. ArXiv ID 1111.5473. Slides.
2010
 Diameter
of Polyhedra: Limits of Abstraction. . 2010. Journal version of
the SOCG'09 paper.
 An
Improved LPbased Approximation for Steiner Tree.
. 42th ACM Symposium on
Theory of Computing (STOC 2010, Best Paper Award),
Cambridge, Massachusetts, USA, June 68, 2010. Slides.
 A
3/2Approximation Algorithm for RateMonotonic
Multiprocessor Scheduling of ImplicitDeadline Tasks.
. Approximation
and Online Algorithms, 8th International Workshop (WAOA
2010), Liverpool, UK, September 910, 2010. Slides.
 Network Design via Core Detouring for Problems Without a Core. Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 610, 2010.
 EDFschedulability of synchronous periodic task systems is coNPhard. . ACMSIAM Symposium on Discrete Algorithms (SODA10), Austin, Texas, January 1719, 2010. Slides.
 Optimal selection of customers for a lastminute offer. . Operations Research. 2010.
2009
 Exact quantification of the suboptimality of uniprocessor fixedpriority pre emptive scheduling. . Realtime Systems. 2009.
 On
the Complexity of the Asymmetric VPN Problem.
.
12th Intl. Workshop
on Approximation Algorithms for Combinat, UC
Berkeley, USA, August 2123, 2009. Slides.
 New
Hardness Results for Diophantine Approximation.
. 12th
Intl. Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX '09),
UC Berkeley, USA, August 2123, 2009. Slides.
 An
AverageCase Analysis for RateMonotonic Multiprocessor
Realtime Scheduling. . 17th Annual European
Symposium on Algorithms (ESA'09), Copenhagen,
September 7–9, 2009. Slides.
 Diameter of Polyhedra: Limits of Abstraction. 25th Annual ACM Symposium on Computational Geometry (SoCG'09), Aarhus, Denmark, June 810, 2009 .
2008
 Convexly independent subsets of the Minkowski sum of planar point sets. . Electronic Journal of Combinatorics, Vol 15, 2008.
 Staticpriority
Realtime
Scheduling: Response Time Computation is NPhard.
. RealTime
Systems Symposium, Barcelona, Nov. 303 Dec., 2008.
 A
PTAS for Static Priority RealTime Scheduling with
Resource Augmentation. .
Automata, Languages
and Programming (ICALP'08), Reykjavik, Iceland,
July 711, 2008. Slides.
 Approximating
connected
facility location problems via Random facility sampling
and core detouring. . Proceeding of
Nineteenth annual ACMSIAM Symposium (SODA '08),
San Francisco, California, 2022.01.2008. Slides.
Theses
 On the computational
complexity of periodic scheduling. . EPFL, Lausanne, Switzerland. 2009. Slides.
 Algorithms for Virtual Private Networks. . Master's thesis. TU Dortmund, Germany. 2006.