Thomas Rothvoß

PostDoc

EPFL SB IMA
MA C1 553
Station 8
CH-1015 Lausanne
Phone: +41 21 693 2568
Fax: +41 21 693 5840
Email: firstname.rothvoss [at] epfl.ch

New homepage

Publications

2013

[25]
F. Eisenbrand; D. Palvoelgyi; T. Rothvoss : Bin Packing via Discrepancy of Permutations; Acm Transactions On Algorithms. 2013. DOI : 10.1145/2483699.2483704.
[24]
J. Byrka; F. Grandoni; T. Rothvoss; L. Sanità : Steiner Tree Approximation via Iterative Randomized Rounding; Journal of the ACM. 2013. DOI : 10.1145/2432622.2432628.

2011

[23]
F. Grandoni; T. Rothvoss; L. Sanita : From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk; Mathematics Of Operations Research. 2011. DOI : 10.1287/moor.1110.0490.
[22]
F. Grandoni; T. Rothvoss : A PTAS for the Highway Problem. 2011. Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 22-25, 2011.
[21]
F. Eisenbrand; D. Palvoelgyi; T. Rothvoss : Bin Packing via Discrepancy of Permutations. 2011. Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 22-25, 2011.

2010

[20]
R. Cominetti; J. R. Correa; T. Rothvoss; J. San Martin : Optimal Selection of Customers for a Last-Minute Offer; Operations Research. 2010. DOI : 10.1287/opre.1090.0787.
[19]
F. Eisenbrand; F. Grandoni; T. Rothvoss; G. Schafer : Connected facility location via random facility sampling and core detouring; Journal Of Computer And System Sciences. 2010. DOI : 10.1016/j.jcss.2010.02.001.
[18]
F. Eisenbrand; N. Hähnle; A. Razborov; T. Rothvoss : Diameter of Polyhedra: Limits of Abstraction; Mathematics of Operations Research. 2010. DOI : 10.1287/moor.1100.0470.
[17]
A. Karrenbauer; T. Rothvoss : A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks. 2010. Approximation and Online Algorithms, 8th International Workshop (WAOA 2010), Liverpool, UK, September 9-10, 2010.
[16]
F. Grandoni; T. Rothvoss : Network Design via Core Detouring for Problems Without a Core. 2010. 37th International Colloquium on Automata, Languages and Programming (ICALP'10), Bordeaux, France, July 5-10, 2010. p. 490-502. DOI : 10.1007/978-3-642-14165-2_42.
[15]
J. Byrka; F. Grandoni; T. Rothvoß; L. Sanità : An Improved LP-based Approximation for Steiner Tree. 2010. 42th ACM Symposium on Theory of Computing (STOC 2010), Cambridge, Massachusetts, USA, June 6-8, 2010.
[14]
F. Eisenbrand; T. Rothvoß : EDF-schedulability of synchronous periodic task systems is coNP-hard. 2010. ACM-SIAM Symposium on Discrete Algorithms (SODA10), Austin, Texas, January 17-19, 2010.
[13]
R. Cominetti; J. R. Correa; T. Rothvoß; J. San Martín : Optimal selection of customers for a last-minute offer. 2010.

2009

[12]
R. Davis; T. Rothvoß; S. Baruah; A. Burns : Exact quantification of the sub-optimality of uniprocessor fixed-priority pre- emptive scheduling; Real-Time Systems. 2009. DOI : 10.1007/s11241-009-9079-4.
[11]
T. Rothvoss / F. Eisenbrand (Dir.) : On the computational complexity of periodic scheduling. Lausanne, EPFL, 2009. DOI : 10.5075/epfl-thesis-4513.
[10]
T. Rothvoß; L. Sanità : On the Complexity of the Asymmetric VPN Problem. 2009. 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09), UC Berkeley, USA, August 21-23, 2009. p. 326-338. DOI : 10.1007/978-3-642-03685-9_25.
[9]
F. Eisenbrand; T. Rothvoß : New Hardness Results for Diophantine Approximation. 2009. 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09), UC Berkeley, USA, August 21-23, 2009. p. 98--110. DOI : 10.1007/978-3-642-03685-9.
[8]
A. Karrenbauer; T. Rothvoß : An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling. 2009. 17th Annual European Symposium on Algorithms (ESA'09), Copenhagen, September 7–9, 2009. p. 432-443. DOI : 10.1007/978-3-642-04128-0_39.
[7]
F. Eisenbrand; N. Hähnle; T. Rothvoß : Diameter of Polyhedra: Limits of Abstraction. 2009. 25th Annual ACM Symposium on Computational Geometry (SoCG'09), Aarhus, Denmark, June 8-10, 2009. p. 386-392. DOI : 10.1145/1542362.1542428.

2008

[6]
F. Eisenbrand; J. Pach; T. Rothvoß; N. B. Sopher : Convexly independent subsets of the Minkowski sum of planar point sets; Electronic Journal of Combinatorics. 2008.
[5]
F. Eisenbrand; T. Rothvoß : Static-priority Real-time Scheduling: Response Time Computation is NP-hard. 2008. IEEE Real-Time Systems Symposium (RTSS), Barcelona, Nov. 30-3 Dec., 2008. p. 397-406. DOI : 10.1109/RTSS.2008.25.
[4]
F. Eisenbrand; T. Rothvoß : A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation. 2008. Automata, Languages and Programming, 35th International Colloquium (ICALP 2008), Reykjavik, Iceland, July 7-11, 2008.
[3]
F. Eisenbrand; F. Grandoni; T. Rothvoß; G. Schäfer : Approximating connected facility location problems via Random facility sampling and core detouring. 2008. ACM-SIAM Symposium on Discrete Algorithms (SODA '08), San Francisco, California, 20-22.01.2008. p. 1174-1183.

2006

[2]
T. Rothvoß : Algorithms for Virtual Private Networks ; 2006.
[1]
T. Rothvoß : Algorithmen für Virtuelle Private Netzwerke ; 2006.