Please use this identifier to cite or link to this item: doi:10.22028/D291-25992
Title: Engineering combinatorial optimization algorithms to improve the lifetime of OLED displays
Author(s): Karrenbauer, Andreas
Language: English
Year of Publication: 2007
SWD key words: Optimierung
Bildschirm
Nutzungsdauer
OLED
Free key words: Steuergerät
algorithm engineering
optimization
controller
display
lifetime
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
Abstract: In this thesis, we consider an optimization problem arising in the design of controllers for OLED displays. Our objective is to minimize amplitude of the electrical current through the diodes which has a direct impact on the lifetime of such a display. To this end, we model this problem as an integer linear program. Subsequently, we refine this formulation by exploiting the combinatorial structure of the problem. We establish a general approximation framework based on network flow techniques. We apply an algorithm engineering approach to improve our heuristics by interacting experimental evaluations and theoretical investigations. For example on the theoretical side, we present a fully combinatorial linear-time algorithm for the MAXFLOW problem on graphs with bounded bandwidth and accordingly numbered nodes. With respect to our application, we implement a custom-made version of this algorithm to solve an important subproblem. Finally, we develop fully combinatorial approximation algorithms well suited for being implemented in the hardware of a control device that drives an OLED display. Moreover, our algorithms achieve near optimal solutions in practice yielding significantly longer lifetimes of passive matrix OLED displays.
In dieser Arbeit betrachten wir ein Optimierungsproblem, das im Zusammenhang mit der Entwicklung von Steuergeräten für OLED Bildschirme auftritt. Unser Ziel ist es, die Amplitude der Stromstärke, die einen direkten Einfluss auf die Lebensdauer eines solchen Bildschirms hat, zu minimieren. Dazu modellieren wir das Problem als ein ganzzahliges lineares Programm. Danach verfeinern wir diese Formulierung, indem wir die kombinatorische Struktur des Problems ausnutzen. Wir erstellen ein allgemeines Approximationssystem basierend auf Netzwerkflusstechniken. Wir wenden einen algorithm engineering Ansatz an, um unsere Heuristiken durch wechselwirkende experimentelle Auswertungen und theoretische Untersuchungen zu verbessern. Zum Beispiel zeigen wir auf der theoretischen Seite einen vollkombinatorischen Linearzeitalgorithmus für das MAXFLOW Problem auf Graphen mit beschränkter Bandbreite und entsprechend nummerierten Knoten. In Bezug auf unsere Anwendung implementieren wir eine maßgeschneiderte Version dieses Algorithmus, um ein wichtiges Teilproblem zu lösen. Letztendlich haben wir einen vollkombinatorischen Approximationsalgorithmus entwickelt, der gut geeignet ist, um als Schaltkreis in ein Steuergerät für einen OLED Bildschirm integriert zu werden. Darüber hinaus erreichen unsere Algorithmen nahezu optimale Lösungen in der Praxis, was zu einer deutlich längeren Lebensdauer eines OLED Bildschirms mit passiver Matrix führt.
Link to this record: urn:nbn:de:bsz:291-scidok-32416
hdl:20.500.11880/26048
http://dx.doi.org/10.22028/D291-25992
Advisor: Mehlhorn, Kurt
Date of oral examination: 22-Dec-2007
Date of registration: 3-Aug-2010
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
Dissertation_7033_Karr_Andr_2007.pdf1,59 MBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.