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