Homepage

Rene Beier Since September 2007 I work for TomTom in Berlin, Adlershof. Max-Planck-Institut für Informatik Department 1: Algorithms and Complexity Campus E1 4 66123 Saarbrücken Germany Email: Get my email address via email Phone: +49 681 9325 112 Fax: +49 681 9325 199

Research Interests

• Randomized algorithms
• Probabilistic analysis of algorithms
• Smoothed analysis
• Discrete optimization

Group Resposibilities

• Travel committee

Recent Teaching

• Lecture Optimierung (SS 06)
• Lecture Randomized Algorithms (WS 05/06)

Publications

Journal Papers

• Rene Beier, Artur Czumaj, Piotr Krysta and Berthold Vöcking
  Computing equilibria for a service provider game with (im)perfect information
  ACM Transactions on Algorithms, 2(4): 679-706, 2006.
   
• Rene Beier and Berthold Vöcking
  Typical Properties of Winners and Losers in Discrete Optimization
  SIAM J. Comput., 35(4): 855-881, 2006.
   
• Rene Beier and Berthold Vöcking
  An Experimental Study of Random Knapsack Problems
  Algorithmica, 45(1): 121-136, 2006.
   
• Rene Beier and Berthold Vöcking
  Random Knapsack in Expected Polynomial Time.
  Journal of Computer and System Sciences 69(3): 306-329, 2004.
  

Conference Papers

• Rene Beier, Heiko Röglin and Berthold Vöcking
  The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization
  Proc. of the 12th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2007, Ithaca, USA
  To Appear
  
  
• Rene Beier and Berthold Vöcking
  An Experimental Study of Random Knapsack Problems
  Proc. of the 12th Annual European Symposium on Algorithms (ESA), 2004, Bergen, Norway
  [ps]
  
  
• Rene Beier and Berthold Vöcking
  Typical Properties of Winners and Losers in Discrete Optimization
  Proc. of the 36rd Annual ACM Symposium on Theory of Computing (STOC), 2004, Chicago
  [ps]
  
  
• Rene Beier and Berthold Vöcking
  Probabilistic Analysis of Knapsack Core Algorithms
  Proc. of the 15th Symposium on Discrete Algorithms (SODA), 2004, New Orleans
  [ps]
  
  
• Rene Beier, Artur Czumaj, Piotr Krysta and Berthold Vöcking
  Computing Equilibria for Congestion Games with (Im)perfect Information
  Proc. of the 15th Symposium on Discrete Algorithms (SODA), 2004, New Orleans
  [ps]
  
  
• Rene Beier and Berthold Vöcking
  Random Knapsack in Expected Polynomial Time
  Proc. of the 35rd Annual ACM Symposium on Theory of Computing (STOC), 2003, San Diego
  [ps]
  
  
• Cyril Banderier, Rene Beier and Kurt Mehlhorn
  Smoothed Analysis of Three Combinatorial Problems
  Proc. of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS) , 2003, Bratislava
  [ps]
  
  
• Rene Beier, Peter Sanders, Naveen Sivadasan
  Energy Optimal Routing in Radio Networks Using Geometric Data Structures
  Proc. of the 29th International Colloquium on Automata,Languages, and Programming (ICALP), 2002, Malaga/Spain
  [ps]
  
  
• Rene Beier, Job Sibeyn
  A Powerful Heuristic for Telephone Gossiping
  Proc. of the 7th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2000, L'Aquila
  [ps]
  
  

Theses

• Ph.D. thesis
  Probabilistic Analysis of Discrete Optimization Problems
  Advisor: Berthold Vöcking
  Universität des Saarlandes, Saarbrücken, 2004
   
• Diploma thesis
  Eine Heuristik für das Gossiping Problem
  Universität des Saarlandes, Saarbrücken, 2000