[ publications ]
2015
2014
2013
2012
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. F. Grandoni and T. Rothvoß. Symposium on Discrete
Algorithms (SODA 2011), San Francisco, USA, January
2225, 2011. Slides.
 Bin
Packing via Discrepancy of Permutations. F. Eisenbrand, D. Palvoelgyi
and T. Rothvoß. 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. F. Eisenbrand, N. Hähnle, A.
Razborov and T. Rothvoss. 2010. Journal version of
the SOCG'09 paper.
 An
Improved LPbased Approximation for Steiner Tree.
J. Byrka, F. Grandoni, T.
Rothvoß and L. Sanità. 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.
A. Karrenbauer and T.
Rothvoss. 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.
F. Grandoni and T.
Rothvoss. Automata,
Languages and Programming, 37th International
Colloquium, ICALP 2010, Bordeaux, France, July 610,
2010. Slides.
 EDFschedulability
of
synchronous
periodic
task
systems
is
coNPhard. F.
Eisenbrand
and T. Rothvoß. ACMSIAM Symposium on
Discrete Algorithms (SODA10), Austin, Texas,
January 1719, 2010. Slides.
 Optimal
selection
of customers for a lastminute offer. R. Cominetti, J. R. Correa, T.
Rothvoß and J. San Martín. Operations Research.
2010.
2009
 Exact
quantification
of the suboptimality of uniprocessor fixedpriority
pre emptive scheduling. R. Davis, T. Rothvoß, S.
Baruah and A. Burns. Realtime Systems. 2009.
 On
the Complexity of the Asymmetric VPN Problem.
T. Rothvoß and L. Sanità.
12th Intl. Workshop
on Approximation Algorithms for Combinat, UC
Berkeley, USA, August 2123, 2009. Slides.
 New
Hardness Results for Diophantine Approximation.
F. Eisenbrand and T.
Rothvoß. 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. A. Karrenbauer and T. Rothvoß. 17th Annual European
Symposium on Algorithms (ESA'09), Copenhagen,
September 7–9, 2009. Slides.
 F. Eisenbrand, N. Hähnle
and T. Rothvoß. 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.
F. Eisenbrand, J. Pach, T.
Rothvoß and N. B. Sopher. Electronic Journal of
Combinatorics, Vol 15, 2008.
 Staticpriority
Realtime
Scheduling: Response Time Computation is NPhard.
F. Eisenbrand and T.
Rothvoß. RealTime
Systems Symposium, Barcelona, Nov. 303 Dec., 2008.
 A
PTAS for Static Priority RealTime Scheduling with
Resource Augmentation. F. Eisenbrand and T. Rothvoß.
Automata, Languages
and Programming (ICALP'08), Reykjavik, Iceland,
July 711, 2008. Slides.
 Approximating
connected
facility location problems via Random facility sampling
and core detouring. F. Eisenbrand, F. Grandoni, T.
Rothvoß and G. Schäfer. Proceeding of
Nineteenth annual ACMSIAM Symposium (SODA '08),
San Francisco, California, 2022.01.2008. Slides.
Theses