×

zbMATH — the first resource for mathematics

Rothvoß, Thomas

Compute Distance To:
Author ID: rothvoss.thomas Recent zbMATH articles by "Rothvoß, Thomas"
Published as: Rothvoß, Thomas; Rothvoss, Thomas
Documents Indexed: 46 Publications since 2008

Publications by Year

Citations contained in zbMATH Open

38 Publications have been cited 409 times in 325 Documents Cited by Year
The matching polytope has exponential extension complexity. Zbl 1315.90038
Rothvoss, Thomas
60
2014
An improved LP-based approximation for Steiner tree. Zbl 1293.05039
Byrka, Jaroslaw; Grandoni, Fabrizio; Rothvoß, Thomas; Sanità, Laura
51
2010
Steiner tree approximation via iterative randomized rounding. Zbl 1281.68234
Byrka, Jarosław; Grandoni, Fabrizio; Rothvoss, Thomas; Sanità, Laura
50
2013
Some \(0/1\) polytopes need exponential size extended formulations. Zbl 1282.90245
Rothvoß, Thomas
26
2013
Extended formulations for polygons. Zbl 1290.68122
Fiorini, Samuel; Rothvoß, Thomas; Tiwary, Hans Raj
24
2012
Diameter of polyhedra: limits of abstraction. Zbl 1226.52004
Eisenbrand, Friedrich; Hähnle, Nicolai; Razborov, Alexander; Rothvoß, Thomas
18
2010
Connected facility location via random facility sampling and core detouring. Zbl 1208.68236
Eisenbrand, Friedrich; Grandoni, Fabrizio; Rothvoß, Thomas; Schäfer, Guido
17
2010
The matching polytope has exponential extension complexity. Zbl 1426.90255
Rothvoss, Thomas
15
2017
Matroids and integrality gaps for hypergraphic Steiner tree relaxations. Zbl 1286.05024
Goemans, Michel X.; Olver, Neil; Rothvoß, Thomas; Zenklusen, Rico
13
2012
Approximating connected facility location problems via random facility sampling and core detouring. Zbl 1192.90103
Eisenbrand, Friedrich; Grandoni, Fabrizio; Rothvoß, Thomas; Schäfer, Guido
12
2008
EDF-schedulability of synchronous periodic task systems is coNP-hard. Zbl 1288.68114
Eisenbrand, Friedrich; Rothvoß, Thomas
12
2010
Polynomiality for bin packing with a constant number of item types. Zbl 1421.68080
Goemans, Michel X.; Rothvoß, Thomas
11
2014
Bin packing via discrepancy of permutations. Zbl 1301.68196
Eisenbrand, Friedrich; Pálvölgyi, Dömötör; Rothvoß, Thomas
10
2013
A logarithmic additive integrality gap for bin packing. Zbl 1423.90225
Hoberg, Rebecca; Rothvoss, Thomas
9
2017
Cover-decomposition and polychromatic numbers. Zbl 1268.05061
Bollobás, Béla; Pritchard, David; Rothvoss, Thomas; Scott, Alex
7
2013
Network design via core detouring for problems without a core. Zbl 1288.68013
Grandoni, Fabrizio; Rothvoß, Thomas
7
2010
Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling. Zbl 1184.68121
Davis, Robert I.; Rothvoß, Thomas; Baruah, Sanjoy K.; Burns, Alan
7
2009
Convexly independent subsets of the Minkowski sum of planar point sets. Zbl 1160.52013
Eisenbrand, Friedrich; Pach, János; Rothvoß, Thomas; Sopher, Nir B.
6
2008
From uncertainty to nonlinearity: solving virtual private network via single-sink buy-at-bulk. Zbl 1238.68188
Grandoni, Fabrizio; Rothvoß, Thomas; Sanità, Laura
6
2011
Approximation algorithms for single and multi-commodity connected facility location. Zbl 1341.90081
Grandoni, Fabrizio; Rothvoß, Thomas
6
2011
0/1 polytopes with quadratic Chvátal rank. Zbl 1377.90112
Rothvoß, Thomas; Sanitá, Laura
6
2013
New hardness results for Diophantine approximation. Zbl 1254.68349
Eisenbrand, Friedrich; Rothvoß, Thomas
4
2009
Pricing on paths: a PTAS for the highway problem. Zbl 1377.90100
Grandoni, Fabrizio; Rothvoß, Thomas
4
2011
A PTAS for static priority real-time scheduling with resource augmentation. Zbl 1152.90438
Eisenbrand, Friedrich; Rothvoß, Thomas
3
2008
On the complexity of the asymmetric VPN problem. Zbl 1255.68311
Rothvoß, Thomas; Sanità, Laura
3
2009
Constructive discrepancy minimization for convex sets. Zbl 1359.52009
Rothvoss, Thomas
3
2017
Better bin packing approximations via discrepancy theory. Zbl 1344.68099
Rothvoss, Thomas
3
2016
An improved deterministic rescaling for linear programming algorithms. Zbl 1418.90152
Hoberg, Rebecca; Rothvoss, Thomas
3
2017
Exact comparison of fixed priority and EDF scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms. Zbl 1337.68047
Davis, Robert I.; Burns, Alan; Baruah, Sanjoy; Rothvoß, Thomas; George, Laurent; Gettings, Oliver
2
2015
A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. Zbl 1373.68454
Levey, Elaine; Rothvoss, Thomas
2
2016
Bin packing via discrepancy of permutations. Zbl 1376.90048
Eisenbrand, Friedrich; Pálvölgyi, Dömötör; Rothvoß, Thomas
2
2011
The entropy rounding method in approximation algorithms. Zbl 1422.68313
Rothvoß, Thomas
1
2012
An average-case analysis for rate-monotonic multiprocessor real-time scheduling. Zbl 1256.68021
Karrenbauer, Andreas; Rothvoß, Thomas
1
2009
Set covering with ordered replacement: additive and multiplicative gaps. Zbl 1341.90108
Eisenbrand, Friedrich; Kakimura, Naonori; Rothvoß, Thomas; Sanità, Laura
1
2011
Optimal selection of customers for a last-minute offer. Zbl 1228.90063
Cominetti, Roberto; Correa, José R.; Rothvoß, Thomas; San Martín, Jaime
1
2010
\(0/1\) polytopes with quadratic Chvátal rank. Zbl 1364.90223
Rothvoß, Thomas; Sanità, Laura
1
2017
Number balancing is as hard as Minkowski’s theorem and shortest vector. Zbl 1418.90228
Hoberg, Rebecca; Ramadas, Harishchandra; Rothvoss, Thomas; Yang, Xin
1
2017
Deterministic discrepancy minimization via the multiplicative weight update method. Zbl 1418.05127
Levy, Avi; Ramadas, Harishchandra; Rothvoss, Thomas
1
2017
The matching polytope has exponential extension complexity. Zbl 1426.90255
Rothvoss, Thomas
15
2017
A logarithmic additive integrality gap for bin packing. Zbl 1423.90225
Hoberg, Rebecca; Rothvoss, Thomas
9
2017
Constructive discrepancy minimization for convex sets. Zbl 1359.52009
Rothvoss, Thomas
3
2017
An improved deterministic rescaling for linear programming algorithms. Zbl 1418.90152
Hoberg, Rebecca; Rothvoss, Thomas
3
2017
\(0/1\) polytopes with quadratic Chvátal rank. Zbl 1364.90223
Rothvoß, Thomas; Sanità, Laura
1
2017
Number balancing is as hard as Minkowski’s theorem and shortest vector. Zbl 1418.90228
Hoberg, Rebecca; Ramadas, Harishchandra; Rothvoss, Thomas; Yang, Xin
1
2017
Deterministic discrepancy minimization via the multiplicative weight update method. Zbl 1418.05127
Levy, Avi; Ramadas, Harishchandra; Rothvoss, Thomas
1
2017
Better bin packing approximations via discrepancy theory. Zbl 1344.68099
Rothvoss, Thomas
3
2016
A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. Zbl 1373.68454
Levey, Elaine; Rothvoss, Thomas
2
2016
Exact comparison of fixed priority and EDF scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms. Zbl 1337.68047
Davis, Robert I.; Burns, Alan; Baruah, Sanjoy; Rothvoß, Thomas; George, Laurent; Gettings, Oliver
2
2015
The matching polytope has exponential extension complexity. Zbl 1315.90038
Rothvoss, Thomas
60
2014
Polynomiality for bin packing with a constant number of item types. Zbl 1421.68080
Goemans, Michel X.; Rothvoß, Thomas
11
2014
Steiner tree approximation via iterative randomized rounding. Zbl 1281.68234
Byrka, Jarosław; Grandoni, Fabrizio; Rothvoss, Thomas; Sanità, Laura
50
2013
Some \(0/1\) polytopes need exponential size extended formulations. Zbl 1282.90245
Rothvoß, Thomas
26
2013
Bin packing via discrepancy of permutations. Zbl 1301.68196
Eisenbrand, Friedrich; Pálvölgyi, Dömötör; Rothvoß, Thomas
10
2013
Cover-decomposition and polychromatic numbers. Zbl 1268.05061
Bollobás, Béla; Pritchard, David; Rothvoss, Thomas; Scott, Alex
7
2013
0/1 polytopes with quadratic Chvátal rank. Zbl 1377.90112
Rothvoß, Thomas; Sanitá, Laura
6
2013
Extended formulations for polygons. Zbl 1290.68122
Fiorini, Samuel; Rothvoß, Thomas; Tiwary, Hans Raj
24
2012
Matroids and integrality gaps for hypergraphic Steiner tree relaxations. Zbl 1286.05024
Goemans, Michel X.; Olver, Neil; Rothvoß, Thomas; Zenklusen, Rico
13
2012
The entropy rounding method in approximation algorithms. Zbl 1422.68313
Rothvoß, Thomas
1
2012
From uncertainty to nonlinearity: solving virtual private network via single-sink buy-at-bulk. Zbl 1238.68188
Grandoni, Fabrizio; Rothvoß, Thomas; Sanità, Laura
6
2011
Approximation algorithms for single and multi-commodity connected facility location. Zbl 1341.90081
Grandoni, Fabrizio; Rothvoß, Thomas
6
2011
Pricing on paths: a PTAS for the highway problem. Zbl 1377.90100
Grandoni, Fabrizio; Rothvoß, Thomas
4
2011
Bin packing via discrepancy of permutations. Zbl 1376.90048
Eisenbrand, Friedrich; Pálvölgyi, Dömötör; Rothvoß, Thomas
2
2011
Set covering with ordered replacement: additive and multiplicative gaps. Zbl 1341.90108
Eisenbrand, Friedrich; Kakimura, Naonori; Rothvoß, Thomas; Sanità, Laura
1
2011
An improved LP-based approximation for Steiner tree. Zbl 1293.05039
Byrka, Jaroslaw; Grandoni, Fabrizio; Rothvoß, Thomas; Sanità, Laura
51
2010
Diameter of polyhedra: limits of abstraction. Zbl 1226.52004
Eisenbrand, Friedrich; Hähnle, Nicolai; Razborov, Alexander; Rothvoß, Thomas
18
2010
Connected facility location via random facility sampling and core detouring. Zbl 1208.68236
Eisenbrand, Friedrich; Grandoni, Fabrizio; Rothvoß, Thomas; Schäfer, Guido
17
2010
EDF-schedulability of synchronous periodic task systems is coNP-hard. Zbl 1288.68114
Eisenbrand, Friedrich; Rothvoß, Thomas
12
2010
Network design via core detouring for problems without a core. Zbl 1288.68013
Grandoni, Fabrizio; Rothvoß, Thomas
7
2010
Optimal selection of customers for a last-minute offer. Zbl 1228.90063
Cominetti, Roberto; Correa, José R.; Rothvoß, Thomas; San Martín, Jaime
1
2010
Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling. Zbl 1184.68121
Davis, Robert I.; Rothvoß, Thomas; Baruah, Sanjoy K.; Burns, Alan
7
2009
New hardness results for Diophantine approximation. Zbl 1254.68349
Eisenbrand, Friedrich; Rothvoß, Thomas
4
2009
On the complexity of the asymmetric VPN problem. Zbl 1255.68311
Rothvoß, Thomas; Sanità, Laura
3
2009
An average-case analysis for rate-monotonic multiprocessor real-time scheduling. Zbl 1256.68021
Karrenbauer, Andreas; Rothvoß, Thomas
1
2009
Approximating connected facility location problems via random facility sampling and core detouring. Zbl 1192.90103
Eisenbrand, Friedrich; Grandoni, Fabrizio; Rothvoß, Thomas; Schäfer, Guido
12
2008
Convexly independent subsets of the Minkowski sum of planar point sets. Zbl 1160.52013
Eisenbrand, Friedrich; Pach, János; Rothvoß, Thomas; Sopher, Nir B.
6
2008
A PTAS for static priority real-time scheduling with resource augmentation. Zbl 1152.90438
Eisenbrand, Friedrich; Rothvoß, Thomas
3
2008
all top 5

Cited by 576 Authors

14 Pokutta, Sebastian
10 Fiorini, Samuel
10 Tiwary, Hans Raj
8 Braun, Gábor
8 Rothvoß, Thomas
7 Weltge, Stefan
6 Faenza, Yuri
6 Grandoni, Fabrizio
6 Ljubić, Ivana
5 Bley, Andreas
5 Eisenbrand, Friedrich
5 Fukunaga, Takuro
5 Kaibel, Volker
5 Könemann, Jochen
5 Kortsarz, Guy
5 Nutov, Zeev
5 Santos, Francisco
5 Shitov, Yaroslav Nikolaevich
4 Avis, David M.
4 Baruah, Sanjoy K.
4 Conforti, Michele
4 Gillis, Nicolas
4 Glineur, François
4 Gouveia, Joao
4 Huynh, Tony
4 Jansen, Klaus
4 Marchetti-Spaccamela, Alberto
4 Olver, Neil
4 Padrol, Arnau
4 Pashkovich, Kanstantsin
4 Ravi, Ramamoorthi
4 Sanità, Laura
4 Saurabh, Saket
4 Zambelli, Giacomo
3 Bansal, Nikhil
3 Bonifaci, Vincenzo
3 Chen, Jian-Jia
3 Christodoulou, George C.
3 Cornuéjols, Gérard P.
3 Dadush, Daniel
3 Davis, Robert I.
3 de Wolf, Ronald Michiel
3 Di Summa, Marco
3 Ding, Wei
3 Feldmann, Andreas Emil
3 Fomin, Fedor V.
3 Hrubeš, Pavel
3 Hsieh, Sun-Yuan
3 Iwata, Satoru
3 Kim, Edward D.
3 Koutecký, Martin
3 Lee, Troy
3 Leitner, Markus
3 Lokshtanov, Daniel
3 Mastrolilli, Monaldo
3 Pálvölgyi, Dömötör
3 Qiu, Ke
3 Robinson, Richard Z.
3 Roy, Aurko
3 Scheithauer, Guntram
3 Sgouritsa, Alkmini
3 Sitters, Rene A.
3 Thomas, Rekha R.
3 Vandaele, Arnaud
3 Walter, Matthias
3 Wiese, Andreas
3 Wu, Chenchen
3 Xu, Dachuan
3 Zhang, Zhao
2 Abu-Affash, A. Karim
2 Althaus, Ernst
2 Angelopoulos, Spyros
2 Aprile, Manuel
2 Arulselvan, Ashwin
2 Bodur, Merve
2 Bonnet, Edouard
2 Bremner, David
2 Busch, Costas
2 Calinescu, Gruia
2 Chakrabarty, Deeparnab
2 Chen, Chi-Yeh
2 Cohen, Nachshon
2 Criado Gallart, Francisco
2 De Loera, Jesús A.
2 Del Pia, Alberto
2 Dey, Santanu S.
2 Deza, Antoine
2 Dobrin, Radu
2 Du, Ding-Zhu
2 Escoffier, Bruno
2 Fawzi, Hamza
2 Gajarský, Jakub
2 Gettings, Oliver
2 Gollowitzer, Stefan
2 Grappe, Roland
2 Hähnle, Nicolai
2 Hajiaghayi, Mohammad Taghi
2 Hliněný, Petr
2 Iori, Manuel
2 Jain, Rahul
...and 476 more Authors
all top 5

Cited in 70 Serials

43 Mathematical Programming. Series A. Series B
21 Algorithmica
16 Theoretical Computer Science
14 Mathematics of Operations Research
12 Discrete & Computational Geometry
12 Real-Time Systems
11 SIAM Journal on Computing
11 Journal of Combinatorial Optimization
10 Discrete Applied Mathematics
8 Information Processing Letters
8 Operations Research Letters
8 SIAM Journal on Discrete Mathematics
6 Journal of Computer and System Sciences
6 Theory of Computing Systems
6 Discrete Optimization
4 Discrete Mathematics
4 International Journal of Foundations of Computer Science
4 European Journal of Operational Research
4 The Electronic Journal of Combinatorics
4 Journal of Discrete Algorithms
3 European Journal of Combinatorics
3 Computational Geometry
3 Computational Complexity
3 Computational Optimization and Applications
3 INFORMS Journal on Computing
3 Optimization Letters
2 Applied Mathematics and Computation
2 Information and Computation
2 Computers & Operations Research
2 Journal of Parallel and Distributed Computing
2 Journal of Global Optimization
2 SIAM Review
2 Top
2 Optimization Methods & Software
2 Foundations of Computational Mathematics
2 Mathematical Programming Computation
2 Journal of the Operations Research Society of China
1 Linear and Multilinear Algebra
1 Advances in Mathematics
1 Journal of Combinatorial Theory. Series A
1 Journal of Combinatorial Theory. Series B
1 Operations Research
1 Proceedings of the American Mathematical Society
1 Combinatorica
1 Social Choice and Welfare
1 Graphs and Combinatorics
1 Annals of Operations Research
1 Linear Algebra and its Applications
1 Bulletin of the American Mathematical Society. New Series
1 SIAM Journal on Optimization
1 Cybernetics and Systems Analysis
1 Combinatorics, Probability and Computing
1 The Journal of Artificial Intelligence Research (JAIR)
1 Constraints
1 Doklady Mathematics
1 Journal of Scheduling
1 Journal of the ACM
1 Annals of Mathematics. Second Series
1 RAIRO. Operations Research
1 Journal of Systems Science and Complexity
1 Journal of Machine Learning Research (JMLR)
1 OR Spectrum
1 JMMA. Journal of Mathematical Modelling and Algorithms
1 Computational Management Science
1 Discrete Mathematics, Algorithms and Applications
1 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
1 Theory of Computing
1 EURO Journal on Computational Optimization
1 Computer Science Review
1 Algebraic Combinatorics

Citations by Year