Author Publications

Export as [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0
Group by: Date | Item Type
Jump to: 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 | 2009 | 2008 | 2007 | 2006 | 2005 | 2004 | 2003
Number of items: 63.

2016

Manthey, Bodo and Waanders, Marten (2016) Approximation algorithms for k-connected graph factors. In: 13th Workshop on Approximation and Online Algorithms, WAOA 2015, 17-18 December 2015, Patras, Greece (pp. pp. 1-12).

2015

Balcan, Maria-Florina and Manthey, Bodo and Röglin, Heiko and Roughgarden, Tim (2015) Analysis of algorithms beyond the worst case. Dagstuhl reports, 4 (9). pp. 30-49. ISSN 2192-5283

Bläser, Markus and Manthey, Bodo (2015) Smoothed complexity theory. ACM transactions on computation theory, 7 (2). A:1-A20. ISSN 1942-3454

Bringmann, Karl and Engels, Christian and Manthey, Bodo and Rao, B.V. Raghavendra (2015) Random shortest paths: non-euclidean instances for metric optimization problems. Algorithmica, 73 (1). pp. 42-62. ISSN 0178-4617

Brunsch, Tobias and Cornelissen, Kamiel and Manthey, Bodo and Röglin, Heiko and Rösner, Clemens (2015) Smoothed analysis of the successive shortest path algorithm. SIAM journal on computing, 44 (6). pp. 1798-1819. ISSN 0097-5397

Cornelissen, Kamiel and Manthey, Bodo (2015) Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm. In: 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 26-28 May 2015, Istanbul, Turkey (pp. pp. 157-160).

Cornelissen, Kamiel and Manthey, Bodo (2015) Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm. In: 21st Computing and Combinatorics Conference, COCOON 2015, 4-6 August 2015, Beijing, China (pp. pp. 701-712).

Hurink, Johann and Manthey, Bodo (2015) 12th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2013) : editorial. Discrete applied mathematics, 195 . p. 1. ISSN 0166-218X

Künnemann, Marvin and Manthey, Bodo (2015) Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic. In: 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015, 6-10 July 2015, Kyoto, Japan (pp. pp. 859-871).

Künnemann, Marvin and Manthey, Bodo (2015) Smoothed approximation ratio of the 2-opt heuristic for the TSP. In: 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 26-28 May 2015, Istanbul, Turkey (pp. pp. 1-4).

Manthey, Bodo (2015) Smoothed analysis of local search algorithms. In: 14th International Symposium on Algorithms and Data Structures, WADS 2015, 5-7 August 2015, Victoria, BC, Canada (pp. pp. 518-527).

2014

Cornelissen, Kamiel and Hoeksma, Ruben and Manthey, Bodo and Narayanaswamy, N.S. and Rahul, C.S. (2014) Approximability of Connected Factors. In: 11th Workshop on Approximation and Online Algorithms, WAOA 2013, 5-6 September 2013, Sophia Antipolis, France (pp. pp. 120-131).

Graaf, Maurits de and Manthey, Bodo (2014) Probabilistic analysis of power assignments. In: 39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014, 25-29 September 2014, Budapest, Hungary (pp. pp. 201-212).

Hoeksma, Ruben and Manthey, Bodo and Uetz, Marc (2014) Decomposition algorithm for the single machine scheduling polytope. In: Combinatorial Optimization, Third International Symposium, ISCO 2014, 5-7 March 2014, Lisbon, Portugal (pp. pp. 280-291).

2013

Bläser, Markus and Manthey, Bodo and Rao, B.V. Raghavendra (2013) Smoothed analysis of partitioning algorithms for Euclidean functionals. Algorithmica, 66 (2). pp. 397-418. ISSN 0178-4617

Bomhoff, Matthijs and Manthey, Bodo (2013) Bisimplicial edges in bipartite graphs. Discrete applied mathematics, 161 (12). pp. 1699-1706. ISSN 0166-218X

Bringmann, Karl and Engels, Christian and Manthey, Bodo and Rao, B.V. Raghavendra (2013) Random shortest paths: non-euclidean instances for metric optimization problems. In: 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, 26-30 August 2013, Klosterneuburg, Austria (pp. pp. 219-230).

Brunsch, T. and Cornelissen, K. and Manthey, B. and Röglin, H. (2013) Smoothed analysis of the successive shortest path algorithm. In: 24th ACM-SIAM Symposium on Discrete Algorithms 2013, 6-8 January 2013, New Orleans, LA, USA (pp. pp. 1180-1189).

Brunsch, Tobias and Cornelissen, Kamiel and Manthey, Bodo and Röglin, Heiko (2013) Smoothed analysis of belief propagation for minimum-cost flow and matching. In: 7th International Workshop on Algorithms and Computation, WALCOM 2013, 14-16 February 2013, Kharagpur, India (pp. pp. 182-193).

Brunsch, Tobias and Cornelissen, Kamiel and Manthey, Bodo and Röglin, Heiko (2013) Smoothed analysis of belief propagation for minimum-cost flow and matching. Journal of graph algorithms and applications, 17 (6). pp. 647-670. ISSN 1526-1719

Brunsch, Tobias and Cornelissen, Kamiel and Manthey, Bodo and Röglin, Heiko (2013) Smoothed analysis of the successive shortest path algorithm. In: 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2013, 21-23 May 2013, Enschede, Netherlands (pp. pp. 27-30).

(2013) Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2013). In: 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2013, 21-23 May 2013, Enschede, Netherlands (pp. pp. 1-222).

Hoeksma, Ruben and Manthey, Bodo and Uetz, Marc (2013) Decomposition algorithm for the single machine scheduling polytope. [Report]

Manthey, B. and Röglin, H. (2013) Worst-case and smoothed analysis of k-means clustering with Bregman divergences. Journal of Computational Geometry, 4 (1). pp. 94-132. ISSN 1920-180X

Manthey, Bodo and Veenstra, Rianne (2013) Smoothed analysis of the 2-opt heuristic for the TSP: polynomial bounds for Gaussian noise. In: 24th International Symposium on Algorithms and Computation, ISAAC 2013, 16-18 December 2013, Hong Kong, China (pp. pp. 579-589).

Manthey, Bodo and Plociennik, Kai (2013) Approximating independent set in perturbed graphs. Discrete applied mathematics, 161 (12). pp. 1761-1768. ISSN 0166-218X

2012

Bläser, Markus and Manthey, Bodo (2012) Smoothed complexity theory. In: 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012, 27-31 August 2012, Bratislava, Slovakia (pp. pp. 198-209).

Damerow, Valentina and Manthey, Bodo and Meyer auf der Heide, Friedhelm and Räcke, Heide Harald and Scheideler, Christian and Sohler, Christian and Tantau, Till (2012) Smoothed analysis of left-to-right maxima with applications. ACM Transactions on Algorithms, 8 (3). p. 30. ISSN 1549-6325

Engels, Christian and Manthey, Bodo and Raghavendra Rao, B.V. (2012) Random shortest path metrics with applications. In: Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012), 29-31 May 2012, Munich, Germany (pp. pp. 121-124).

Fouz, Mahmoud and Kufleitner, Manfred and Manthey, Bodo and Zeini Jahromi, Nima (2012) On smoothed analysis of quicksort and Hoare's find. Algorithmica, 62 (3-4). pp. 879-905. ISSN 0178-4617

Manthey, Bodo (2012) Multi-criteria TSP: Min and max combined. Operations Research Letters, 40 (1). pp. 36-38. ISSN 0167-6377

Manthey, Bodo (2012) On approximating multi-criteria TSP. ACM transactions on algorithms, 8 (2). p. 17. ISSN 1549-6325

Manthey, Bodo (2012) Deterministic algorithms for multi-criteria Max-TSP. Discrete Applied Mathematics, 160 (15). pp. 2277-2285. ISSN 0166-218X

2011

Arthur, David and Manthey, Bodo and Röglin, Heiko (2011) Smoothed analysis of the k-means method. Journal of the ACM, 58 (5). p. 19. ISSN 0004-5411

Bläser, Markus and Jakoby, Andreas and Liskiewicz, Maciej and Manthey, Bodo (2011) Privacy in non-private environments. Theory of Computing Systems, 48 (1). pp. 211-245. ISSN 1432-4350

Bläser, Markus and Manthey, Bodo and Rao, B.V. Raghavendra (2011) Smoothed analysis of partitioning algorithms for Euclidean functionals. In: 12th International Symposium on Algorithms and Data Structures, WADS 2011, 15-17 Aug 2011, New York, NY, USA (pp. pp. 110-121).

Boros, Endre and Elbassioni, Khaled and Fouz, Mahmoud and Gurvich, Vladimir and Makino, Kazuhisa and Manthey, Bodo (2011) Stochastic mean payoff games: smoothed analysis and approximation schemes. In: 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, 4-8 July 2011, Zurich, Switzerland (pp. pp. 147-158).

Manthey, Bodo (2011) Deterministic algorithms for multi-criteria TSP. In: 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011, 23-25 May 2011, Tokyo, Japan (pp. pp. 264-275).

Manthey, Bodo (2011) Towards explaining the speed of $k$-means. Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica, 2011 . pp. 45-54.

Manthey, Bodo and Röglin, Heiko (2011) Smoothed analysis: analysis of algorithms beyond worst case. it - Information Technology, 53 (6). pp. 280-286. ISSN 1611-2776

2010

Bomhoff, Matthijs and Manthey, Bodo (2010) Bisimplicial edges in bipartite graphs. In: Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010, 25-27 May 2010, Cologne, Germany (pp. pp. 29-32).

Manthey, Bodo (2010) Multi-criteria TSP: Min and Max combined. In: 7th International Workshop Approximation and Online Algorithms, WAOA 2009, 10-11 September 2009, Copenhagen, Denmark (pp. pp. 205-216).

Manthey, Bodo and Plociennik, Kai (2010) Approximating independent set in semi-random graphs. In: 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010, 25-27 May 2010, Cologne, Germany (pp. pp. 119-122).

2009

Arpe, J. and Manthey, B. (2009) Approximability of Minimum AND-Circuits. Algorithmica, 53 (3). pp. 337-357. ISSN 0178-4617

Arthur, David and Manthey, Bodo and Röglin, Heiko (2009) k-Means has polynomial smoothed complexity. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, 24-27 Oct 2009, Atlanta, GA, USA (pp. pp. 405-414).

Engels, Christian and Manthey, Bodo (2009) Average-case approximation ratio of the 2-opt algorithm for the TSP. Operations Research Letters, 37 (2). pp. 83-84. ISSN 0167-6377

Fouz, Mahmoud and Kufleitner, Manfred and Manthey, Bodo and Zeini Jahromi, Nima (2009) On smoothed analysis of quicksort and Hoare's find. In: 15th Annual International Computing and Combinatorics Conference, COCOON 2009, 13-15 Jul 2009, Niagara Falls, NY, USA (pp. pp. 158-167).

Manthey, B. (2009) Minimum-weight cycle covers and their approximability. Discrete Applied Mathematics, 157 (7). pp. 1470-1480. ISSN 0166-218X

Manthey, B. and Shankar Ram, L. (2009) Approximation algorithms for multi-criteria traveling salesman problems. Algorithmica, 53 (1). pp. 69-88. ISSN 0178-4617

Manthey, Bodo (2009) On approximating multi-criteria TSP. In: 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, 26-28 Feb 2009, Freiburg, Germany (pp. pp. 637-648).

Manthey, Bodo and Röglin, Heiko (2009) Worst-case and smoothed analysis of $k$-means clustering with Bregman divergences. In: 20th International Symposium on Algorithms and Computation, ISAAC 2009, 16-18 Dec 2009, Honolulu, Hawaii, USA (pp. pp. 1024-1033).

Manthey, Bodo and Röglin, Heiko (2009) Improved smoothed analysis of the $k$-means method. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, 4-6 Jan 2009, New York, NY, USA (pp. pp. 461-470).

2008

Bläser, Markus and Heynen, Thomas and Manthey, Bodo (2008) Adding cardinality constraints to integer programs with applications to maximum satisfiability. Information Processing Letters, 105 (5). pp. 194-198. ISSN 0020-0190

Manthey, Bodo (2008) On approximating restricted cycle covers. SIAM Journal on Computing, 38 (1). pp. 181-206. ISSN 0097-5397

2007

Manthey, Bodo and Reischuk, Rüdiger (2007) Smoothed analysis of binary search trees. Theoretical Computer Science, 378 (3). pp. 292-315. ISSN 0304-3975

2006

Bläser, Markus and Jakoby, Andreas and Liśkiewicz, Maciej and Manthey, Bodo (2006) Private computation: k-connected versus 1-connected networks. Journal of Cryptology, 19 (3). pp. 341-357. ISSN 0933-2790

Bläser, Markus and Manthey, Bodo and Sgall, Jirí (2006) An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. Journal of Discrete Algorithms, 4 (4). pp. 623-632. ISSN 1468-0904

2005

Bläser, Markus and Manthey, Bodo (2005) Approximating maximum weight cycle covers in directed graphs with weights zero and one. Algorithmica, 42 (2). pp. 121-139. ISSN 0178-4617

Manthey, Bodo (2005) Non-approximability of weighted multiple sequence alignment for arbitrary metrics. Information Processing Letters, 95 (3). pp. 389-395. ISSN 0020-0190

Manthey, Bodo and Reischuk, Rüdiger (2005) The intractability of computing the Hamming distance. Theoretical Computer Science, 337 (1-3). pp. 331-346. ISSN 0304-3975

2004

Liśkiewicz, Maciej and Manthey, Bodo (2004) New lower and upper bounds for the competitive ratio of transmission protocols. Information Processing Letters, 89 (6). pp. 297-301. ISSN 0020-0190

2003

Böhme, Martin and Manthey, Bodo (2003) The computational power of compiling C++. Bulletin of the European Association for Theoretical Computer Science, 81 . pp. 264-270. ISSN 0252-9742

Manthey, Bodo (2003) Non-approximability of weighted multiple sequence alignment. Theoretical Computer Science, 296 (1). pp. 179-192. ISSN 0304-3975

This list was generated on Sat Aug 27 05:42:44 2016 CEST.