×
Author ID: manthey.bodo Recent zbMATH articles by "Manthey, Bodo"
Published as: Manthey, Bodo
External Links: MGP

Publications by Year

Citations contained in zbMATH Open

60 Publications have been cited 220 times in 134 Documents Cited by Year
Smoothed analysis of the \(k\)-means method. Zbl 1281.68224
Arthur, David; Manthey, Bodo; Röglin, Heiko
18
2011
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. Zbl 1275.90076
Bläser, Markus; Manthey, Bodo; Sgall, Jiří
11
2006
Approximating maximum weight cycle covers in directed graphs with weights zero and one. Zbl 1079.68068
Bläser, Markus; Manthey, Bodo
11
2005
Stochastic mean payoff games: smoothed analysis and approximation schemes. Zbl 1332.68064
Boros, Endre; Elbassioni, Khaled; Fouz, Mahmoud; Gurvich, Vladimir; Makino, Kazuhisa; Manthey, Bodo
10
2011
Smoothed analysis of partitioning algorithms for Euclidean functionals. Zbl 1279.90140
Bläser, Markus; Manthey, Bodo; Raghavendra Rao, B. V.
9
2013
Smoothed analysis of binary search trees. Zbl 1120.68043
Manthey, Bodo; Reischuk, Rüdiger
9
2007
Approximation algorithms for multi-criteria traveling salesman problems. Zbl 1161.90019
Manthey, Bodo; Shankar Ram, L.
8
2009
\(k\)-means has polynomial smoothed complexity. Zbl 1292.68187
Arthur, David; Manthey, Bodo; Röglin, Heiko
7
2009
On approximating restricted cycle covers. Zbl 1165.05028
Manthey, Bodo
7
2008
Smoothed analysis of the 2-opt heuristic for the TSP: polynomial bounds for Gaussian noise. Zbl 1407.90277
Manthey, Bodo; Veenstra, Rianne
6
2013
Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences. Zbl 1273.68152
Manthey, Bodo; Röglin, Heiko
6
2009
On approximating multicriteria TSP. Zbl 1295.90063
Manthey, Bodo
5
2012
Minimum-weight cycle covers and their approximability. Zbl 1172.05344
Manthey, Bodo
5
2009
Private computation: \(k\)-connected versus 1-connected networks. Zbl 1103.68507
Bläser, Markus; Jakoby, Andreas; Liskiewicz, Maciej; Manthey, Bodo
5
2006
Smoothed analysis of the successive shortest path algorithm. Zbl 1326.05039
Brunsch, Tobias; Cornelissen, Kamiel; Manthey, Bodo; Röglin, Heiko; Rösner, Clemens
5
2015
Towards understanding the smoothed approximation ratio of the 2-Opt heuristic. Zbl 1440.68334
Künnemann, Marvin; Manthey, Bodo
5
2015
Smoothed analysis of left-to-right maxima with applications. Zbl 1295.68233
Damerow, Valentina; Manthey, Bodo; Meyer Auf Der Heide, Friedhelm; Räcke, Harald; Scheideler, Christian; Sohler, Christian; Tantau, Till
4
2012
On smoothed analysis of quicksort and Hoare’s find. Zbl 1241.68059
Fouz, Mahmoud; Kufleitner, Manfred; Manthey, Bodo; Zeini Jahromi, Nima
4
2012
Approximating multi-criteria Max-TSP. Zbl 1158.68546
Bläser, Markus; Manthey, Bodo; Putz, Oliver
4
2008
The intractability of computing the Hamming distance. Zbl 1078.68044
Manthey, Bodo; Reischuk, Rüdiger
4
2005
Random shortest paths: non-Euclidean instances for metric optimization problems. Zbl 1319.90072
Bringmann, Karl; Engels, Christian; Manthey, Bodo; Raghavendra Rao, B. V.
4
2015
Approximability of connected factors. Zbl 1383.68096
Cornelissen, Kamiel; Hoeksma, Ruben; Manthey, Bodo; Narayanaswamy, N. S.; Rahul, C. S.
3
2014
Average-case approximation ratio of the 2-opt algorithm for the TSP. Zbl 1159.90494
Engels, Christian; Manthey, Bodo
3
2009
Smoothed analysis of binary search trees and quicksort under additive noise. Zbl 1173.68458
Manthey, Bodo; Tantau, Till
3
2008
Smoothed analysis of belief propagation for minimum-cost flow and matching. Zbl 1379.68278
Brunsch, Tobias; Cornelissen, Kamiel; Manthey, Bodo; Röglin, Heiko
3
2013
On approximating multi-criteria TSP. Zbl 1236.68298
Manthey, Bodo
3
2009
Improved approximation algorithms for max-2SAT with cardinality constraint. Zbl 1019.68136
Bläser, Markus; Manthey, Bodo
3
2002
Non-approximability of weighted multiple sequence alignment. Zbl 1044.68160
Manthey, Bodo
3
2003
On approximating restricted cycle covers. Zbl 1177.90397
Manthey, Bodo
3
2006
Multi-criteria TSP: Min and Max combined. Zbl 1284.90066
Manthey, Bodo
3
2010
Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences. Zbl 1404.68197
Manthey, Bodo; Roeglin, Heiko
3
2013
Decomposition algorithm for the single machine scheduling polytope. Zbl 1445.90034
Hoeksma, Ruben; Manthey, Bodo; Uetz, Marc
3
2014
Probabilistic analysis of power assignments. Zbl 1382.90045
de Graaf, Maurits; Manthey, Bodo
3
2017
Smoothed analysis of belief propagation for minimum-cost flow and matching. Zbl 1276.05090
Brunsch, Tobias; Cornelissen, Kamiel; Manthey, Bodo; Röglin, Heiko
2
2013
Approximating independent set in perturbed graphs. Zbl 1287.05105
Manthey, Bodo; Plociennik, Kai
2
2013
In memoriam Walter Kern. Zbl 1473.01064
Hochstättler, Winfried; Hurink, Johann; Manthey, Bodo; Paulusma, Daniel; Peis, Britta; Still, Georg
2
2021
Deterministic algorithms for multi-criteria max-TSP. Zbl 1278.90361
Manthey, Bodo
2
2012
Privacy in non-private environments. Zbl 1208.94038
Bläser, Markus; Jakoby, Andreas; Liśkiewicz, Maciej; Manthey, Bodo
2
2011
Non-approximability of weighted multiple sequence alignment for arbitrary metrics. Zbl 1185.68833
Manthey, Bodo
2
2005
Smoothed analysis of binary search trees. Zbl 1173.68457
Manthey, Bodo; Reischuk, Rüdiger
2
2005
Approximation algorithms for connected graph factors of minimum weight. Zbl 1390.68760
Cornelissen, Kamiel; Hoeksma, Ruben; Manthey, Bodo; Narayanaswamy, N. S.; Rahul, C. S.; Waanders, Marten
2
2018
Two approximation algorithms for 3-cycle covers. Zbl 1013.90123
Bläser, Markus; Manthey, Bodo
2
2002
Adding cardinality constraints to integer programs with applications to maximum satisfiability. Zbl 1190.90084
Bläser, Markus; Heynen, Thomas; Manthey, Bodo
2
2008
Approximating bounded-degree spanning trees and connected factors with leaves. Zbl 1409.05198
Kern, Walter; Manthey, Bodo
1
2017
Efficient implementation of Carathéodory’s theorem for the single machine scheduling polytope. Zbl 1354.90109
Hoeksma, Ruben; Manthey, Bodo; Uetz, Marc
1
2016
Smoothed complexity theory. Zbl 1347.68155
Bläser, Markus; Manthey, Bodo
1
2015
Approximability of minimum AND-circuits. Zbl 1172.68061
Arpe, Jan; Manthey, Bodo
1
2009
On smoothed analysis of Quicksort and Hoare’s find. Zbl 1248.68580
Fouz, Mahmoud; Kufleitner, Manfred; Manthey, Bodo; Jahromi, Nima Zeini
1
2009
The intractability of computing the Hamming distance. Zbl 1205.68173
Manthey, Bodo; Reischuk, Rüdiger
1
2003
Smoothed complexity theory. Zbl 1365.68272
Bläser, Markus; Manthey, Bodo
1
2012
Deterministic algorithms for multi-criteria TSP. Zbl 1331.68294
Manthey, Bodo
1
2011
Smoothed analysis of partitioning algorithms for Euclidean functionals. Zbl 1342.90155
Bläser, Markus; Manthey, Bodo; Raghavendra Rao, B. V.
1
2011
Approximation algorithms for restricted cycle covers based on cycle decompositions. Zbl 1167.05336
Manthey, Bodo
1
2006
Probabilistic analysis of optimization problems on generalized random shortest path metrics. Zbl 1477.68561
Klootwijk, Stefan; Manthey, Bodo; Visser, Sander K.
1
2019
Privacy in non-private environments. Zbl 1094.94507
Bläser, Markus; Jakoby, Andreas; Liśkiewicz, Maciej; Manthey, Bodo
1
2004
Multi-criteria TSP: Min and Max combined. Zbl 1242.90217
Manthey, Bodo
1
2012
Probabilistic analysis of optimization problems on generalized random shortest path metrics. Zbl 1477.68562
Klootwijk, Stefan; Manthey, Bodo; Visser, Sander K.
1
2021
Approximation algorithms for \(k\)-connected graph factors. Zbl 1383.68098
Manthey, Bodo; Waanders, Marten
1
2015
Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm. Zbl 1468.90137
Cornelissen, Kamiel; Manthey, Bodo
1
2015
Probabilistic analysis of power assignments. Zbl 1426.90176
de Graaf, Maurits; Manthey, Bodo
1
2014
In memoriam Walter Kern. Zbl 1473.01064
Hochstättler, Winfried; Hurink, Johann; Manthey, Bodo; Paulusma, Daniel; Peis, Britta; Still, Georg
2
2021
Probabilistic analysis of optimization problems on generalized random shortest path metrics. Zbl 1477.68562
Klootwijk, Stefan; Manthey, Bodo; Visser, Sander K.
1
2021
Probabilistic analysis of optimization problems on generalized random shortest path metrics. Zbl 1477.68561
Klootwijk, Stefan; Manthey, Bodo; Visser, Sander K.
1
2019
Approximation algorithms for connected graph factors of minimum weight. Zbl 1390.68760
Cornelissen, Kamiel; Hoeksma, Ruben; Manthey, Bodo; Narayanaswamy, N. S.; Rahul, C. S.; Waanders, Marten
2
2018
Probabilistic analysis of power assignments. Zbl 1382.90045
de Graaf, Maurits; Manthey, Bodo
3
2017
Approximating bounded-degree spanning trees and connected factors with leaves. Zbl 1409.05198
Kern, Walter; Manthey, Bodo
1
2017
Efficient implementation of Carathéodory’s theorem for the single machine scheduling polytope. Zbl 1354.90109
Hoeksma, Ruben; Manthey, Bodo; Uetz, Marc
1
2016
Smoothed analysis of the successive shortest path algorithm. Zbl 1326.05039
Brunsch, Tobias; Cornelissen, Kamiel; Manthey, Bodo; Röglin, Heiko; Rösner, Clemens
5
2015
Towards understanding the smoothed approximation ratio of the 2-Opt heuristic. Zbl 1440.68334
Künnemann, Marvin; Manthey, Bodo
5
2015
Random shortest paths: non-Euclidean instances for metric optimization problems. Zbl 1319.90072
Bringmann, Karl; Engels, Christian; Manthey, Bodo; Raghavendra Rao, B. V.
4
2015
Smoothed complexity theory. Zbl 1347.68155
Bläser, Markus; Manthey, Bodo
1
2015
Approximation algorithms for \(k\)-connected graph factors. Zbl 1383.68098
Manthey, Bodo; Waanders, Marten
1
2015
Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm. Zbl 1468.90137
Cornelissen, Kamiel; Manthey, Bodo
1
2015
Approximability of connected factors. Zbl 1383.68096
Cornelissen, Kamiel; Hoeksma, Ruben; Manthey, Bodo; Narayanaswamy, N. S.; Rahul, C. S.
3
2014
Decomposition algorithm for the single machine scheduling polytope. Zbl 1445.90034
Hoeksma, Ruben; Manthey, Bodo; Uetz, Marc
3
2014
Probabilistic analysis of power assignments. Zbl 1426.90176
de Graaf, Maurits; Manthey, Bodo
1
2014
Smoothed analysis of partitioning algorithms for Euclidean functionals. Zbl 1279.90140
Bläser, Markus; Manthey, Bodo; Raghavendra Rao, B. V.
9
2013
Smoothed analysis of the 2-opt heuristic for the TSP: polynomial bounds for Gaussian noise. Zbl 1407.90277
Manthey, Bodo; Veenstra, Rianne
6
2013
Smoothed analysis of belief propagation for minimum-cost flow and matching. Zbl 1379.68278
Brunsch, Tobias; Cornelissen, Kamiel; Manthey, Bodo; Röglin, Heiko
3
2013
Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences. Zbl 1404.68197
Manthey, Bodo; Roeglin, Heiko
3
2013
Smoothed analysis of belief propagation for minimum-cost flow and matching. Zbl 1276.05090
Brunsch, Tobias; Cornelissen, Kamiel; Manthey, Bodo; Röglin, Heiko
2
2013
Approximating independent set in perturbed graphs. Zbl 1287.05105
Manthey, Bodo; Plociennik, Kai
2
2013
On approximating multicriteria TSP. Zbl 1295.90063
Manthey, Bodo
5
2012
Smoothed analysis of left-to-right maxima with applications. Zbl 1295.68233
Damerow, Valentina; Manthey, Bodo; Meyer Auf Der Heide, Friedhelm; Räcke, Harald; Scheideler, Christian; Sohler, Christian; Tantau, Till
4
2012
On smoothed analysis of quicksort and Hoare’s find. Zbl 1241.68059
Fouz, Mahmoud; Kufleitner, Manfred; Manthey, Bodo; Zeini Jahromi, Nima
4
2012
Deterministic algorithms for multi-criteria max-TSP. Zbl 1278.90361
Manthey, Bodo
2
2012
Smoothed complexity theory. Zbl 1365.68272
Bläser, Markus; Manthey, Bodo
1
2012
Multi-criteria TSP: Min and Max combined. Zbl 1242.90217
Manthey, Bodo
1
2012
Smoothed analysis of the \(k\)-means method. Zbl 1281.68224
Arthur, David; Manthey, Bodo; Röglin, Heiko
18
2011
Stochastic mean payoff games: smoothed analysis and approximation schemes. Zbl 1332.68064
Boros, Endre; Elbassioni, Khaled; Fouz, Mahmoud; Gurvich, Vladimir; Makino, Kazuhisa; Manthey, Bodo
10
2011
Privacy in non-private environments. Zbl 1208.94038
Bläser, Markus; Jakoby, Andreas; Liśkiewicz, Maciej; Manthey, Bodo
2
2011
Deterministic algorithms for multi-criteria TSP. Zbl 1331.68294
Manthey, Bodo
1
2011
Smoothed analysis of partitioning algorithms for Euclidean functionals. Zbl 1342.90155
Bläser, Markus; Manthey, Bodo; Raghavendra Rao, B. V.
1
2011
Multi-criteria TSP: Min and Max combined. Zbl 1284.90066
Manthey, Bodo
3
2010
Approximation algorithms for multi-criteria traveling salesman problems. Zbl 1161.90019
Manthey, Bodo; Shankar Ram, L.
8
2009
\(k\)-means has polynomial smoothed complexity. Zbl 1292.68187
Arthur, David; Manthey, Bodo; Röglin, Heiko
7
2009
Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences. Zbl 1273.68152
Manthey, Bodo; Röglin, Heiko
6
2009
Minimum-weight cycle covers and their approximability. Zbl 1172.05344
Manthey, Bodo
5
2009
Average-case approximation ratio of the 2-opt algorithm for the TSP. Zbl 1159.90494
Engels, Christian; Manthey, Bodo
3
2009
On approximating multi-criteria TSP. Zbl 1236.68298
Manthey, Bodo
3
2009
Approximability of minimum AND-circuits. Zbl 1172.68061
Arpe, Jan; Manthey, Bodo
1
2009
On smoothed analysis of Quicksort and Hoare’s find. Zbl 1248.68580
Fouz, Mahmoud; Kufleitner, Manfred; Manthey, Bodo; Jahromi, Nima Zeini
1
2009
On approximating restricted cycle covers. Zbl 1165.05028
Manthey, Bodo
7
2008
Approximating multi-criteria Max-TSP. Zbl 1158.68546
Bläser, Markus; Manthey, Bodo; Putz, Oliver
4
2008
Smoothed analysis of binary search trees and quicksort under additive noise. Zbl 1173.68458
Manthey, Bodo; Tantau, Till
3
2008
Adding cardinality constraints to integer programs with applications to maximum satisfiability. Zbl 1190.90084
Bläser, Markus; Heynen, Thomas; Manthey, Bodo
2
2008
Smoothed analysis of binary search trees. Zbl 1120.68043
Manthey, Bodo; Reischuk, Rüdiger
9
2007
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. Zbl 1275.90076
Bläser, Markus; Manthey, Bodo; Sgall, Jiří
11
2006
Private computation: \(k\)-connected versus 1-connected networks. Zbl 1103.68507
Bläser, Markus; Jakoby, Andreas; Liskiewicz, Maciej; Manthey, Bodo
5
2006
On approximating restricted cycle covers. Zbl 1177.90397
Manthey, Bodo
3
2006
Approximation algorithms for restricted cycle covers based on cycle decompositions. Zbl 1167.05336
Manthey, Bodo
1
2006
Approximating maximum weight cycle covers in directed graphs with weights zero and one. Zbl 1079.68068
Bläser, Markus; Manthey, Bodo
11
2005
The intractability of computing the Hamming distance. Zbl 1078.68044
Manthey, Bodo; Reischuk, Rüdiger
4
2005
Non-approximability of weighted multiple sequence alignment for arbitrary metrics. Zbl 1185.68833
Manthey, Bodo
2
2005
Smoothed analysis of binary search trees. Zbl 1173.68457
Manthey, Bodo; Reischuk, Rüdiger
2
2005
Privacy in non-private environments. Zbl 1094.94507
Bläser, Markus; Jakoby, Andreas; Liśkiewicz, Maciej; Manthey, Bodo
1
2004
Non-approximability of weighted multiple sequence alignment. Zbl 1044.68160
Manthey, Bodo
3
2003
The intractability of computing the Hamming distance. Zbl 1205.68173
Manthey, Bodo; Reischuk, Rüdiger
1
2003
Improved approximation algorithms for max-2SAT with cardinality constraint. Zbl 1019.68136
Bläser, Markus; Manthey, Bodo
3
2002
Two approximation algorithms for 3-cycle covers. Zbl 1013.90123
Bläser, Markus; Manthey, Bodo
2
2002
all top 5

Cited by 235 Authors

32 Manthey, Bodo
5 Bläser, Markus
4 Cornelissen, Kamiel
4 Klootwijk, Stefan
4 Röglin, Heiko
3 Boros, Endre
3 Boyle, Elette
3 Elbassioni, Khaled M.
3 Fouz, Mahmoud
3 Friedrich, Tobias
3 Gurvich, Vladimir A.
3 Han, Yo-Sub
3 Hoeksma, Ruben
3 Khachay, Mikhail Yur’evich
3 Ko, Sang-Ki
3 Kowalik, Łukasz
3 Makino, Kazuhisa
3 Narayanaswamy, N. S.
3 Ng, Timothy
3 Rahul, C. S.
3 Ram, L. Shankar
3 Salomaa, Kai T.
2 Balkanski, Eric
2 Ball, Marshall
2 Behrendt, Lukas
2 Brunsch, Tobias
2 Casel, Katrin
2 Chatterjee, Krishnendu
2 Cohen, Ran
2 Dadush, Daniel
2 Dai, Guowei
2 de Graaf, Maurits
2 Deng, Xiao-Tie
2 Faenza, Yuri
2 Galby, Esther
2 Gao, Yansong
2 Gourvès, Laurent
2 Huiberts, Sophie
2 Krinninger, Sebastian
2 Kubik, Mathieu
2 Kufleitner, Manfred
2 Künnemann, Marvin
2 Lagodzinski, J. A. Gregor
2 Löser, Alexander
2 Malkin, Tal G.
2 Marx, Dániel
2 Monnot, Jérôme
2 Moran, Tal
2 Mucha, Marcin
2 Neznakhina, Katherine
2 Raghavendra Rao, B. V.
2 Rauch Henzinger, Monika
2 Reijnders, Victor M. J. J.
2 Schepper, Philipp
2 Sharma, Roohani
2 Stadler, Peter F.
2 Tale, Prafullkumar
2 Uetz, Marc
2 Vanderpooten, Daniel
2 Visser, Sander K.
2 Weerasena, Lakmali
2 Wilhelm, Marcus
2 Zeini Jahromi, Nima
2 Zhang, Jie
1 Abdullah, Amirali
1 Adamaszek, Anna
1 Ahmed, Shabbir
1 Archibald, Margaret
1 Aswani, Anil
1 Austrin, Per
1 Bazgan, Cristina
1 Beimel, Amos
1 Berkemer, Sarah J.
1 Bienkowski, Marcin
1 Borgwardt, Steffen
1 Boucherie, Richard J.
1 Brieden, Andreas
1 Bringmann, Karl
1 Cazaux, Bastien
1 Chandran, L. Sunil
1 Cohen-Addad, Vincent
1 Creignou, Nadia
1 Curticapean, Radu
1 Cygan, Marek
1 Data, Deepesh
1 de A. T. de Carvalho, Francisco
1 de Klerk, Etienne
1 Deepak, Maram Sai Krishna
1 Deift, Percy A.
1 Ding, Wei
1 Elsässer, Robert
1 Engels, Christian
1 Espuny Díaz, Alberto
1 Etscheid, Michael
1 Filho, Fernando M. De Oliveira
1 Floridi, Luciano
1 Florios, Kostas
1 Friggstad, Zachary
1 Gaffke, Norbert
1 Ganian, Robert
...and 135 more Authors
all top 5

Cited in 44 Serials

12 Algorithmica
11 Theoretical Computer Science
6 Discrete Applied Mathematics
4 Information Processing Letters
4 SIAM Journal on Computing
3 Operations Research Letters
3 Information and Computation
3 Random Structures & Algorithms
3 Journal of Global Optimization
3 European Journal of Operational Research
3 Mathematical Programming. Series A. Series B
2 INFORMS Journal on Computing
2 Theory of Computing Systems
2 Journal of Combinatorial Optimization
2 Journal of Discrete Algorithms
2 Proceedings of the Steklov Institute of Mathematics
2 Mathematics in Computer Science
1 Acta Informatica
1 Discrete Mathematics
1 Applied Mathematics and Computation
1 Computing
1 Information Sciences
1 Journal of Computer and System Sciences
1 Journal of Statistical Planning and Inference
1 Operations Research
1 Quaestiones Mathematicae
1 SIAM Journal on Numerical Analysis
1 Synthese
1 Discrete & Computational Geometry
1 SIAM Journal on Matrix Analysis and Applications
1 Journal of Cryptology
1 Machine Learning
1 International Journal of Computational Geometry & Applications
1 International Journal of Foundations of Computer Science
1 Pattern Recognition
1 Distributed Computing
1 Combinatorics, Probability and Computing
1 Electronic Journal of Probability
1 Doklady Mathematics
1 Journal of Graph Algorithms and Applications
1 Discrete Optimization
1 Journal of Computational and Graphical Statistics
1 Fuzzy Information and Engineering
1 SN Operations Research Forum

Citations by Year