max planck institut
informatik

Homepage

Andreas Karrenbauer Department 1: Algorithms and Complexity Max-Planck-Institut für Informatik Campus E1 4, office 311D 66123 Saarbrücken Germany Email: firstname.lastname@mpi-inf.mpg.de Phone: +49 681 9325 1058 Fax: +49 681 9325 1099

---

Teaching

---

• This semester: core lecture Optimization 2013
• Previous semesters

---

---

Research Interests

---

• Integer Programming
• Combinatorial Optimization
• Discrete Optimization in Image Processing
• Applied and Industrial Discrete Optimization
• Algorithm Engineering

---

Publications

---

• Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds
  L. Becchetti, V. Bonifaci, M. Dirnberger, A. Karrenbauer, K. Mehlhorn
  Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), 2013, to appear
  

• Blinking Molecule Tracking
  A. Karrenbauer, D. Wöll
  Proceedings of the 12th International Symposium on Experimental Algorithms (SEA), 2013, to appear
  

• A novel method for automatic single molecule tracking of blinking molecules at low intensities
  D. Wöll, C. Kölbl, B. Stempfle, A. Karrenbauer
  Physical Chemistry Chemical Physics, vol. 15, pp. 6196–6205, DOI: 10.1039/C3CP44693J, 2013
  

• Leveling the Grid
  S. Cornelsen, A. Karrenbauer, S. Li
  Proceedings of the SIAM Meeting on Algorithm Engineering and Experiments (ALENEX), 2012, pp. 45 - 54
  

• Accelerated Bend Minimization
  S. Cornelsen, A. Karrenbauer
  Journal of Graph Algorithms and Applications, Vol. 16, no. 3, pp. 635-650, 2012, DOI: 10.7155/jgaa.00265
  
  The conference version appeared in
  Proceedings of the 19th International Symposium on Graph Drawing (GD 2011), LNCS 7034, 2012, pp. 111-122
  

• Recovering missing coefficients in DCT-transformed images
  S. Li, A. Karrenbauer, D. Saupe, C.C.J. Kuo
  Proceedings of the 18th IEEE International Conference on Image Processing (ICIP), 2011, pp. 1569-1572
  

• Approximating the interval constrained coloring problem
  E. Althaus, S. Canzar, K. Elbassioni, A. Karrenbauer, J. Mestre
  in Algorithmica, vol. 61, no. 2, pp. 342–361, 2011, doi: 10.1007/s00453-010-9406-0
  
  The conference version appeared in
  Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT), 2008, pp. 210-221

• A combinatorial algorithm for the 1-median problem in R^d with the Chebyshev-norm
  J. Hatzl, A. Karrenbauer
  Operations Research Letters, vol. 38, no. 5, September 2010, pp. 383-385, doi:10.1016/j.orl.2010.07.002
  

• A 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks
  A. Karrenbauer, T. Rothvoß
  Approximation and Online Algorithms, LNCS 6534, 2011, pp. 166-177, doi:10.1007/978-3-642-18318-8_15

• Computing H/D-Exchange rates of single residues from data of proteolytic fragments
  E. Althaus, S. Canzar, M. R. Emmett, C. Ehrler, A. Karrenbauer, A. G. Marshall, A. Meyer-Baese, J. D. Tipton, and H. Zhang
  BMC Bioinformatics 2010, 11:424, doi:10.1186/1471-2105-11-424
  
  The conference version appeared in
  Proceedings of the 23rd Annual ACM Symposium on Applied Computing, 2008, pp. 1273-1277

• The interval constrained 3-coloring problem
  J. Byrka, A. Karrenbauer, L. Sanità
  9th Latin American Theoretical Informatics Symposium (LATIN), 2010, LNCS 6034, pp. 592 – 603
  

• An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling
  A. Karrenbauer, T. Rothvoß
  17th Annual European Symposium on Algorithms (ESA), 2009, LNCS 5757, pp. 432–443
  

• Domain walls and chaos in the disordered SOS model
  K. Schwarz, A. Karrenbauer, G. Schehr, H. Rieger
  J. Stat. Mech.(2009) P08022

• Multiline Addressing by Network Flow
  F. Eisenbrand, A. Karrenbauer, M. Skutella, C. Xu
  in Algorithmica, vol. 53, no. 4, pp. 583-596, 2009
  
  The conference version appeared in
  Yossi Azar & Thomas Erlebach (eds.): Algorithms - ESA 2006, Lecture Notes in Computer Science, Springer: Berlin, 2006, Proceedings of the 14th Annual European Symposium on Algorithms (ESA'06), pp. 744-755

• Matching techniques ride to rescue OLED displays
  A. Karrenbauer
  Proceedings of the 3rd Annual International Conference on Combinatorial Optimization and Applications (COCOA), Lecture Notes in Computer Science 5573, Springer, 2009, pp. 110-122

• A Video-Capable Algorithm for Local-Dimming RGB Backlight
  M. Albrecht, A. Karrenbauer, and C. Xu
  SID 2009 International Symposium Digest of Technical Papers, 2009, pp. 753-756

• A clipper-free Algorithm for efficient HW-Implementation of local dimming LED-Backlight
  M. Albrecht, A. Karrenbauer, and C. Xu,
  Proceedings of the 28th International Display Research Conference (IDRC), 2008, pp. 286-289

• Algorithms for longer OLED Lifetime
  F. Eisenbrand, A. Karrenbauer, C. Xu
  in Camil Demetrescu (ed.): WEA 2007, LNCS 4525, Springer, 2007, pp. 338-351, Proceedings of the 6th International Workshop on Experimental Algorithms (WEA'07)

• A new addressing scheme for PM OLED Display
  C. Xu, A. Karrenbauer, K. M. Soh, J. Wahl
  SID 2007 International Symposium Digest of Technical Papers, 2007, pp. 97-100

• Packing a Trunk - now with a Twist, best paper award (2nd prize)
  F. Eisenbrand, S. Funke, A. Karrenbauer, J. Reichel, E. Schömer
  Proceedings of the 2005 ACM Symposium on Solid and Physical Modeling (SPM'05), 2005, pp. 197-206

• Energy-Aware Stage Illumination
  F. Eisenbrand, S. Funke, A. Karrenbauer, D. Matijevic
  in J. S. B. Mitchell, G. Rote (Eds.): Proceedings of the 21st ACM Symposium on Computational Geometry (SoCG), Pisa, Italy, 2005, pp. 336-345

Biography

---

• since January 2013
  Group Coordinator in the Algorithms and Complexity department at the Max Planck Institute for Informatics and Research Group Leader within the Max Planck Center for Visual Computing and Communication, Saarbrücken, Germany.

• July 2010 - December 2012
  Fellow at the Zukunftskolleg of the University of Konstanz, Germany.

• October 2008 - June 2010
  Postdoctoral Researcher in the Discrete Optimization group at EPFL, Lausanne, Switzerland.

• January 2008 - September 2008
  Postdoctoral Researcher in the Algorithms and Complexity department at the Max Planck Institute for Computer Science.

• October 2004 - December 2007
  Ph.D. student in Computer Science at Saarland University and at the Max Planck Institute for Computer Science.
  Ph.D. Thesis: "Engineering Combinatorial Optimization Algorithms to Improve the Lifetime of OLED Displays"

• October 2000 - July 2004
  Studies in Computer Science at Saarland University.
  Master's Thesis: "Packing Boxes with Arbitrary Rotations".

• October 2000 - April 2007
  Studies in Physics at Saarland University.
  Master's Thesis: On the ground state and excited states in models for elastic media with random disorder.

---

• Andreas Karrenbauer:
• Research Interests
• Publications
• Education
• Private