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

Bin Packing via Discrepancy of Permutations

F. Eisenbrand; D. Palvoelgyi; T. Rothvoss 

Acm Transactions On Algorithms. 2013. Vol. 9, num. 3. DOI : 10.1145/2483699.2483704.

Steiner Tree Approximation via Iterative Randomized Rounding

J. Byrka; F. Grandoni; T. Rothvoss; L. Sanità 

Journal of the ACM. 2013. Vol. 60, num. 1, p. 6. DOI : 10.1145/2432622.2432628.

From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk

F. Grandoni; T. Rothvoss; L. Sanita 

Mathematics Of Operations Research. 2011. Vol. 36, p. 185-204. DOI : 10.1287/moor.1110.0490.

A PTAS for the Highway Problem

F. Grandoni; T. Rothvoss 

2011. Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 22-25, 2011.

Bin Packing via Discrepancy of Permutations

F. Eisenbrand; D. Palvoelgyi; T. Rothvoss 

2011. Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 22-25, 2011.

Optimal Selection of Customers for a Last-Minute Offer

R. Cominetti; J. R. Correa; T. Rothvoss; J. San Martin 

Operations Research. 2010. Vol. 58, p. 878-888. DOI : 10.1287/opre.1090.0787.

Connected facility location via random facility sampling and core detouring

F. Eisenbrand; F. Grandoni; T. Rothvoss; G. Schafer 

Journal Of Computer And System Sciences. 2010. Vol. 76, p. 709-726. DOI : 10.1016/j.jcss.2010.02.001.

Diameter of Polyhedra: Limits of Abstraction

F. Eisenbrand; N. Hähnle; A. Razborov; T. Rothvoss 

Mathematics of Operations Research. 2010. Vol. 35, num. 4, p. 786-794. DOI : 10.1287/moor.1100.0470.

A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks

A. Karrenbauer; T. Rothvoss 

2010. Approximation and Online Algorithms, 8th International Workshop (WAOA 2010), Liverpool, UK, September 9-10, 2010.

Network Design via Core Detouring for Problems Without a Core

F. Grandoni; T. Rothvoss 

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.

An Improved LP-based Approximation for Steiner Tree

J. Byrka; F. Grandoni; T. Rothvoß; L. Sanità 

2010. 42th ACM Symposium on Theory of Computing (STOC 2010), Cambridge, Massachusetts, USA, June 6-8, 2010.

EDF-schedulability of synchronous periodic task systems is coNP-hard

F. Eisenbrand; T. Rothvoß 

2010. ACM-SIAM Symposium on Discrete Algorithms (SODA10), Austin, Texas, January 17-19, 2010.

Optimal selection of customers for a last-minute offer

R. Cominetti; J. R. Correa; T. Rothvoß; J. San Martín 

2010

Exact quantification of the sub-optimality of uniprocessor fixed-priority pre- emptive scheduling

R. Davis; T. Rothvoß; S. Baruah; A. Burns 

Real-Time Systems. 2009. Vol. 43, num. 3, p. 211--258. DOI : 10.1007/s11241-009-9079-4.

On the computational complexity of periodic scheduling

T. Rothvoss / F. Eisenbrand (Dir.)  

Lausanne: EPFL, 2009. DOI : 10.5075/epfl-thesis-4513.

On the Complexity of the Asymmetric VPN Problem

T. Rothvoß; L. Sanità 

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.

New Hardness Results for Diophantine Approximation

F. Eisenbrand; T. Rothvoß 

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.

An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling

A. Karrenbauer; T. Rothvoß 

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.

Diameter of Polyhedra: Limits of Abstraction

F. Eisenbrand; N. Hähnle; T. Rothvoß 

2009. 25th Annual ACM Symposium on Computational Geometry (SoCG'09), Aarhus, Denmark, June 8-10, 2009. p. 386-392. DOI : 10.1145/1542362.1542428.

Convexly independent subsets of the Minkowski sum of planar point sets

F. Eisenbrand; J. Pach; T. Rothvoß; N. B. Sopher 

Electronic Journal of Combinatorics. 2008. Vol. 15, num. 1, p. Note 8, 4.

Static-priority Real-time Scheduling: Response Time Computation is NP-hard

F. Eisenbrand; T. Rothvoß 

2008. IEEE Real-Time Systems Symposium (RTSS), Barcelona, Nov. 30-3 Dec., 2008. p. 397-406. DOI : 10.1109/RTSS.2008.25.

A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation

F. Eisenbrand; T. Rothvoß 

2008. Automata, Languages and Programming, 35th International Colloquium (ICALP 2008), Reykjavik, Iceland, July 7-11, 2008.

Approximating connected facility location problems via Random facility sampling and core detouring

F. Eisenbrand; F. Grandoni; T. Rothvoß; G. Schäfer 

2008. ACM-SIAM Symposium on Discrete Algorithms (SODA '08), San Francisco, California, 20-22.01.2008. p. 1174-1183.

Algorithms for Virtual Private Networks

T. Rothvoß 

2006.

Algorithmen für Virtuelle Private Netzwerke

T. Rothvoß 

2006.