MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

A Journey with Discrete Optimization: from the Real World to Theory and Back

Andreas Karrenbauer
Max-Planck-Institut für Informatik - D1
Joint Lecture Series
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
AG Audience
English

Date, Time and Location

Wednesday, 2 July 2014
12:15
60 Minutes
E1 5
002
Saarbrücken

Abstract

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.

Contact

Jennifer Müller
2900
--email hidden
passcode not visible
logged in users only

Jennifer Müller, 06/27/2014 09:12
Jennifer Müller, 04/04/2014 09:45 -- Created document.