Thomas Rothvoß

59 papers A* 11A 3B 6Journal 32Unranked 7

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