Thomas Rothvoß

Publication Activity (10 Years)

Years Active: 2008-2021
Publications (10 Years): 6

Top Topics

Exponential Size

Precedence Constraints

Top Venues

Publications

Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jirí Sgall, Pavel Veselý
Improved Analysis of Online Balanced Clustering. WAOA (2021)
Elaine Levey, Thomas Rothvoß
A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies. SIAM J. Comput. 50 (3) (2021)
Marcin Bienkowski, Martin Böhm, Martin Koutecký, Thomas Rothvoß, Jirí Sgall, Pavel Veselý
Improved Analysis of Online Balanced Clustering. CoRR (2021)
Thomas Rothvoß, Laura Sanità
0/1 Polytopes with Quadratic Chvátal Rank. Oper. Res. 65 (1) (2017)
Fabrizio Grandoni, Thomas Rothvoß
Pricing on Paths: A PTAS for the Highway Problem. SIAM J. Comput. 45 (2) (2016)
Robert I. Davis, Alan Burns, Sanjoy K. Baruah, Thomas Rothvoß, Laurent George, Oliver Gettings
Exact comparison of fixed priority and EDF scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms. Real Time Syst. 51 (5) (2015)
Michel X. Goemans, Thomas Rothvoß
Polynomiality for Bin Packing with a Constant Number of Item Types. SODA (2014)
Thomas Rothvoß
Constructive discrepancy minimization for convex sets. CoRR (2014)
Thomas Rothvoß
A direct proof for Lovett's bound on the communication complexity of low rank matrices. CoRR (2014)
Thomas Rothvoß
The matching polytope has exponential extension complexity. STOC (2014)
Thomas Rothvoß
Constructive Discrepancy Minimization for Convex Sets. FOCS (2014)
Thomas Rothvoß
The matching polytope has exponential extension complexity. CoRR (2013)
Thomas Rothvoß
Approximating Bin Packing within O(log OPT * Log Log OPT) Bins. FOCS (2013)
Thomas Rothvoß, Laura Sanità
0/1 Polytopes with Quadratic Chvátal Rank. IPCO (2013)
Béla Bollobás, David Pritchard, Thomas Rothvoß, Alex D. Scott
Cover-Decomposition and Polychromatic Numbers. SIAM J. Discret. Math. 27 (1) (2013)
Michel X. Goemans, Thomas Rothvoß
Polynomiality for Bin Packing with a Constant Number of Item Types. CoRR (2013)
Thomas Rothvoß
Approximating Bin Packing within O(log OPT * log log OPT) bins CoRR (2013)
Thomas Rothvoß
A Simpler Proof for $O(\textrm{Congestion} + \textrm{Dilation})$ Packet Routing. IPCO (2013)
Thomas Rothvoß
Some 0/1 polytopes need exponential size extended formulations. Math. Program. 142 (1-2) (2013)
Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß
Bin Packing via Discrepancy of Permutations. ACM Trans. Algorithms 9 (3) (2013)
Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità
Steiner Tree Approximation via Iterative Randomized Rounding. J. ACM 60 (1) (2013)
Thomas Rothvoß
The entropy rounding method in approximation algorithms. SODA (2012)
Samuel Fiorini, Thomas Rothvoß, Hans Raj Tiwary
Extended Formulations for Polygons. Discret. Comput. Geom. 48 (3) (2012)
Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen
Matroids and integrality gaps for hypergraphic steiner tree relaxations. STOC (2012)
Thomas Rothvoß
A simpler proof for O(congestion + dilation) packet routing CoRR (2012)
Thomas Rothvoß, Laura Sanità
0/1 Polytopes with Quadratic Chvatal Rank CoRR (2012)
Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß
Bin Packing via Discrepancy of Permutations. SODA (2011)
Thomas Rothvoß
Directed Steiner Tree and the Lasserre Hierarchy CoRR (2011)
Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen
Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations CoRR (2011)
Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità
From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk. Math. Oper. Res. 36 (2) (2011)
Friedrich Eisenbrand, Naonori Kakimura, Thomas Rothvoß, Laura Sanità
Set Covering with Ordered Replacement: Additive and Multiplicative Gaps. IPCO (2011)
Fabrizio Grandoni, Thomas Rothvoß
Pricing on Paths: A PTAS for the Highway Problem. SODA (2011)
Samuel Fiorini, Thomas Rothvoß, Hans Raj Tiwary
Extended formulations for polygons CoRR (2011)
Fabrizio Grandoni, Thomas Rothvoß
Approximation Algorithms for Single and Multi-Commodity Connected Facility Location. IPCO (2011)
Thomas Rothvoß
The Entropy Rounding Method in Approximation Algorithms CoRR (2011)
Béla Bollobás, David Pritchard, Thomas Rothvoß, Alex D. Scott
Cover-Decomposition and Polychromatic Numbers. ESA (2011)
Thomas Rothvoß
Some 0/1 polytopes need exponential size extended formulations CoRR (2011)
Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß
Bin Packing via Discrepancy of Permutations CoRR (2010)
Friedrich Eisenbrand, Thomas Rothvoß
EDF-schedulability of Synchronous Periodic Task Systems is coNP-hard. SODA (2010)
Roberto Cominetti, José R. Correa, Thomas Rothvoß, Jaime San Martín
Optimal Selection of Customers for a Last-Minute Offer. Oper. Res. 58 (4-Part-1) (2010)
David Pritchard, Thomas Rothvoß
Edge-Colouring Hypergraphs Properly (Covering with Matchings) or Polychromatically (Packing Covers) CoRR (2010)
Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß
Diameter of Polyhedra: Limits of Abstraction. Flexible Network Design (2010)
Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß
Diameter of Polyhedra: Limits of Abstraction. Math. Oper. Res. 35 (4) (2010)
Friedrich Eisenbrand, Thomas Rothvoß
Recent Hardness Results for Periodic Uni-processor Scheduling. Scheduling (2010)
Friedrich Eisenbrand, Fabrizio Grandoni, Thomas Rothvoß, Guido Schäfer
Connected facility location via random facility sampling and core detouring. J. Comput. Syst. Sci. 76 (8) (2010)
Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità
An improved LP-based approximation for steiner tree. STOC (2010)
Fabrizio Grandoni, Thomas Rothvoß
Network Design via Core Detouring for Problems without a Core. ICALP (1) (2010)
Friedrich Eisenbrand, Naonori Kakimura, Thomas Rothvoß, Laura Sanità
Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps CoRR (2010)
Fabrizio Grandoni, Thomas Rothvoß
Prizing on Paths: A PTAS for the Highway Problem CoRR (2010)
Andreas Karrenbauer, Thomas Rothvoß
A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks. WAOA (2010)
Andreas Karrenbauer, Thomas Rothvoß
An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling. ESA (2009)
Friedrich Eisenbrand, Nicolai Hähnle, Thomas Rothvoß
Diameter of polyhedra: limits of abstraction. SCG (2009)
Thomas Rothvoß, Laura Sanità
On the Complexity of the Asymmetric VPN Problem. APPROX-RANDOM (2009)
Friedrich Eisenbrand, Thomas Rothvoß
New Hardness Results for Diophantine Approximation. APPROX-RANDOM (2009)
Robert I. Davis, Thomas Rothvoß, Sanjoy K. Baruah, Alan Burns
Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling. Real Time Syst. 43 (3) (2009)
Friedrich Eisenbrand, János Pach, Thomas Rothvoß, Nir B. Sopher
Convexly Independent Subsets of the Minkowski Sum of Planar Point Sets. Electron. J. Comb. 15 (1) (2008)
Friedrich Eisenbrand, Thomas Rothvoß
Static-Priority Real-Time Scheduling: Response Time Computation Is NP-Hard. RTSS (2008)
Friedrich Eisenbrand, Thomas Rothvoß
A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation. ICALP (1) (2008)
Friedrich Eisenbrand, Fabrizio Grandoni, Thomas Rothvoß, Guido Schäfer
Approximating connected facility location problems via random facility sampling and core detouring. SODA (2008)