Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A Journey with Discrete Optimization: from the Real World to Theory and Back
Speaker:Andreas Karrenbauer
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Joint Lecture Series
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Wednesday, 2 July 2014
Duration:60 Minutes
Building:E1 5
Discrete Optimization problems appear in many applications as well as in interdisciplinary research. This leads to interesting theoretical questions with direct practical relevance. In this talk, I will highlight several examples, but I will mainly focus on optimization problems arising with flat panel displays (e.g. OLED). That is, lifetime and power consumption can be improved by displaying each image in a special way. To this end, a discrete optimization problem has to be solved in real-time for varying content. We abstract the computational task for several display technologies in one mathematical framework. From a combinatorial perspective, this boils down to decomposing the edge set of a given bipartite graph into a few number of complete bipartite subgraphs (a.k.a. bicliques). Though we showed that even finding only suboptimal solutions is theoretically very hard, i.e. in the same ballpark as the well-known graph coloring problem, we developed suitable restrictions and refinements of the model by alternating theoretical analysis and experimental evaluation in an algorithm engineering process that led to a method with industrial strength. That is, our algorithm is implemented on a chip that drives the world's first commercially available transparent OLED display.

I will conclude my talk with a brief discussion about two other lines of research where we (i) use integer programming for optimizing keyboard layouts and (ii) work on efficient algorithms for network flow problems arising in image processing and computer vision.

Name(s):Jennifer Müller
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Jennifer Müller, 06/27/2014 09:12 AM
  • Jennifer Müller, 04/04/2014 09:45 AM -- Created document.