Author Publications

Export as [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0
Group by: Date | Item Type
Number of items: 64.

Article

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 (2011) Smoothed analysis of the k-means method. Journal of the ACM, 58 (5). p. 19. ISSN 0004-5411

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 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

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 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 (2005) Approximating maximum weight cycle covers in directed graphs with weights zero and one. Algorithmica, 42 (2). pp. 121-139. ISSN 0178-4617

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

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

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

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 (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 (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 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

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

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 (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 (2012) On smoothed analysis of quicksort and Hoare's find. Algorithmica, 62 (3-4). pp. 879-905. ISSN 0178-4617

Hoeksma, Ruben and Manthey, Bodo and Uetz, Marc (2016) Efficient implementation of Carathéodory’s theorem for the single machine scheduling polytope. Discrete applied mathematics, 215 . pp. 136-145. ISSN 0166-218X

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

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

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

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, 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 (2012) Multi-criteria TSP: Min and max combined. Operations Research Letters, 40 (1). pp. 36-38. ISSN 0167-6377

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

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

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 (2011) Towards explaining the speed of $k$-means. Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica, 2011 . pp. 45-54.

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

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

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

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

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

Conference or Workshop Item

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).

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).

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).

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).

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).

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 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).

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).

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).

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 (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).

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).

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 (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 (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 (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 (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).

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).

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).

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 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).

Report

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

This list was generated on Sun Dec 11 05:42:45 2016 CET.