It is known to be an NP-complete problem to color a graph with a given number of colors. We present some approximation algorithms which come close to the desired number of colors. We also develop an algorithm that colors k-colorable graphs with ~O(n^a(k)) colors, where a(2)=0, a(3)=3/14 and a(k)=1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) for k >= 4, as presented in [20]. This formula has been generalized for new possible base algorithms. / Das Problem, einen Graphen mit einer gegebenen Anzahl Farben zu färben, ist als NP-vollständig bekannt. Hier werden einige Algorithmen vorgestellt, die für dieses Problem eine gute Approximation liefern. Des Weiteren wird ein allgemeines Färbungsverfahren hergeleitet, das für k-färbbare Graphen den bisher besten existierenden Algorithmus darstellt. Es können k-färbbare Graphen mit ~O(n^a(k)) Farben gefärbt werden, wobei a(2)=0, a(3)=3/14 und a(k) = 1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) für k >= 4 gilt [20]. Diese Formel wurde für neue Basisalgorithmen verallgemeinert.

In dieser Arbeit untersuchen wir Algorithmen für Scheduling-Probleme. Wir betrachten semi-online Makespan-Scheduling und generalisiertes Bin Covering. Im online Makespan- Scheduling-Problem sind m Maschinen und n Jobs gegeben, wobei letztere jeweils eine individuelle Bearbeitungszeit haben. Es wird zu jedem Zeitpunkt ein Job offengelegt und muss sofort und unwiderruflich einer Maschine zugewiesen werden, ohne Wissen über zukünftige Jobs. Die Last einer Maschine wird als die Summe der Bearbeitungszeiten der ihr zugewiesenen Jobs definiert. Das Ziel ist es, eine Zuweisung von Jobs zu Maschinen zu finden, sodass die höchste Last einer Maschine minimiert wird. Im semi-online Scheduling-Modell wird dieses strikte Szenario relaxiert. Wir untersuchen drei verschied- ene Modelle. Im ersten ist uns die kumulierte Bearbeitungszeit der Jobs vor Ankunft der einzelnen Jobs bekannt. Im zweiten Modell dürfen wir bis zu einem gewissen Grade bereits zugewiesene Jobs anderen Maschinen neu zuordnen.Im dritten semi-online Scheduling-Modell darf ein Algorithmus mehrere Lösungen parallel konstruieren, von denen die beste ausgegeben wird. Beim generalisierten Bin Covering sind uns m Bintypen und n Objekte gegeben. Ein Bintyp Mj hat einen Bedarf dj und einen Profit rj. Jedes Objekt Jt hat eine Größe pt. Ein Bin vom Typ Mj heißt abgedeckt, wenn die Summe der Größen der ihm zugewiesenen Objekte mindestens dj ist. Wenn ein Bin vom Typ Mj abgedeckt ist, erzielen wir einen Profit von rj. Ziel ist es, die Objekte Bins zuzuweisen, sodass der erzielte Gesamtprofit maximiert wird. Wir untersuchen zwei Modelle, die sich in der Verfügbarkeit von Bintypen unterscheiden. Im Unit-Supply-Modell steht uns von jedem Bintyp genau ein Bin zur Verfügung. Im Gegensatz dazu stehen uns im Infinite-Supply-Modell von jedem Bintyp beliebig viele Bins zur Verfügung. Das Unit-Supply-Modell ist daher eine Verallgemeinerung des Infinite-Supply-Modells. Für alle Modelle zeigen wir beinahe scharfe obere und untere Schranken. / In this thesis we study algorithms for scheduling problems. We investigate semi-online minimum makespan scheduling and generalized bin covering. In online minimum makespan scheduling we are given a set of m machines and n jobs, where each job Jt is specified by a processing time. The jobs arrive one by one and we have to assign them to the machines without any knowledge about future incoming jobs. The load of a machine is defined to be total processing time of the assigned jobs. The goal is to place the jobs on the machines such that the maximum load of a machine is minimized. In semi-online minimum makespan scheduling this strict setting is softened. We investigate three different models. In the first setting an algorithm is given an advice on the total processing time of the jobs. In the second setting we may reassign jobs upto a limited amount. The third semi-online setting we study is minimum makespan scheduling with parallel schedules. In this problem an algorithm may maintain several schedules, the best of which is output after the arrival of the entire job sequence. In generalized bin covering we are given m bin types and n items. Each bin type Mj is specified by a demand dj and a revenue rj. Each item Jt has a size pj. A bin of type Mj is said to be covered if the total size of the assigned items is at least the demand dj. Then the revenue rj is earned. The goal is to find an assignment of items to bins maximizing the total obtained revenue. We study two models of bin supply. In the unit supply model there is only one bin of each type available. By contrast in the infinite supply model each bin type is available arbitrarily often, and hence the former is a generalization of the latter. We provide nearly tight upper and lower bounds for all models.

In dieser Arbeit wird ein applikationsunabhängiges Reduktionssystem entworfen, das selbstständig und effizient für die ihm übergebenen Modellteile in allen Betrachtersituationen aus einem möglichen Spektrum von geometrie- und bild-basierten Approximationsformen jeweils die geeignete Approximation generiert, deren Komplexität möglichst gering ist und bei deren Verwendung ein Szenenbild erzeugt werden kann, dessen Bildfehler die vom Nutzer vorgegebenen Schranken nicht überschreitet. Das System nutzt bild- und geometrie-basierte Approximationsformen für unterschiedliche Bereiche im Sichtvolumen des Betrachters. Nailboards sind die benutzten bild-basierten Approximationen. In dieser Arbeit werden neue Nailboardarten vorgestellt, die für die Approximation von semi-transparenten Objekten und von dynamisch beleuchteten Objekten effizient verwendet werden können. Die vorgestellten Erzeugungs- und Darstellungsmethoden nutzen die Fähigkeiten der aktuellen Hardware intensiv aus, um die Nailboards im Echtzeitkontext nutzbar zu machen. Texturierte, sichtabhängige geometrie-basierte Approximationen werden aus einem texturierten Viewdependent Progressive Mesh (VDPM) gewonnen. In dieser Arbeit wird eine effiziente Methode zur Erzeugung von VDPM vorgestellt, aus der Approximationen mit optimal angepassten Parameterkoordinaten gewonnen werden können, ohne dass ein der VDPM-Erzeugung nachgeschalteter Optimierungsschritt der Parameterkoordinaten aller im VDPM kodierten Approximationen notwendig ist. Die Erzeugung der notwendigen Texturen erfolgt unter Nutzung einer schnellen Parametrisierungsmethode und hardware-gestützter Methoden zur Erzeugung dicht gepackter Texturatlanten. Durch die Kombination von selektiven Zugriffsmethoden auf TFGR mit effizienten Randanpassungsmethoden, wird erstmals ein effizientes und qualitativ hochwertiges Multiresolution Rendering mittels TFGR ermöglicht. Aus dem TFGR werden texturierte sichtunabhängige Approximationen gewonnen. Zur echtzeitfähigen, vollautomatischen Erzeugung aller drei Approximationsformen wird in dieser Arbeit ein Reduktionssystem vorgeschlagen, das diese Approximationsformen verteilt generiert. Für eine effiziente Kommunikation innerhalb dieses Systems werden entsprechende Kompressions-, Caching- und State-Differencing-Mechanismen vorgeschlagen. Lastverteilungsmechanismen sichern eine effiziente Ausnutzung der zur Verfügung stehenden Ressourcen ab. / In this thesis, an application-independent system for the distributed generation of object approximations used for multi-resolution rendering is proposed. The system generates approximations of objects of a scene sent to him in an efficient and fully automatic manner. The system is able to generate different kinds of geometry-based and image-based object approximations. For each given objects of a scene it generates that kind of approximation that is suitable for the current view. That means that its complexity is minimal and that it causes an error in the image generated with this approximation that does not exceed a user-specified threshold. Nailboards are image-based approximations that approximate objects whose size is small compared to the whole scene. In this thesis new kinds of nailboards are presented which can be used efficiently for the approximation of semi-transparent objects and objects in scenes with a dynamic illumination. Capabilities of current graphics hardware are intensively used to generate and render all kinds of Nailboards in real-time. So-called textured view-dependent progressive meshes (VDPM) are used as view dependent geometry-bases approximations for objects whose size is large compared to the whole scene. In this thesis an efficient method for generating VDPM is presented. This method allows the extraction of approximations with optimally adapted texture coordinates without the necessity of an separate optimization step for the texture coordinates in the generation procedure. The textures necessary for the compensation of detail loss are generated using a fast parameterization method from Yoshizawa. The generation of texture atlases is done hardware-accelerated. Further on a hardware-accelerated method for hardware-accelerated multi-resolution rendering using multi chart geometry images (MCGIM) is presented. Out of the MCGIM view-independent geometry-based approximations are extracted. Finally a system for the distributed generation of object approximations is proposed. It generates all three kinds of approximations fully automatic and almost in real time. For an efficient communication within this system suitable compression, caching and state-differencing mechanisms are proposed. Load balancing mechanisms ensure efficient utilization of available resources.

In dieser Arbeit wird ein applikationsunabhängiges Reduktionssystem entworfen, das selbstständig und effizient für die ihm übergebenen Modellteile in allen Betrachtersituationen aus einem möglichen Spektrum von geometrie- und bild-basierten Approximationsformen jeweils die geeignete Approximation generiert, deren Komplexität möglichst gering ist und bei deren Verwendung ein Szenenbild erzeugt werden kann, dessen Bildfehler die vom Nutzer vorgegebenen Schranken nicht überschreitet. Das System nutzt bild- und geometrie-basierte Approximationsformen für unterschiedliche Bereiche im Sichtvolumen des Betrachters. Nailboards sind die benutzten bild-basierten Approximationen. In dieser Arbeit werden neue Nailboardarten vorgestellt, die für die Approximation von semi-transparenten Objekten und von dynamisch beleuchteten Objekten effizient verwendet werden können. Die vorgestellten Erzeugungs- und Darstellungsmethoden nutzen die Fähigkeiten der aktuellen Hardware intensiv aus, um die Nailboards im Echtzeitkontext nutzbar zu machen. Texturierte, sichtabhängige geometrie-basierte Approximationen werden aus einem texturierten Viewdependent Progressive Mesh (VDPM) gewonnen. In dieser Arbeit wird eine effiziente Methode zur Erzeugung von VDPM vorgestellt, aus der Approximationen mit optimal angepassten Parameterkoordinaten gewonnen werden können, ohne dass ein der VDPM-Erzeugung nachgeschalteter Optimierungsschritt der Parameterkoordinaten aller im VDPM kodierten Approximationen notwendig ist. Die Erzeugung der notwendigen Texturen erfolgt unter Nutzung einer schnellen Parametrisierungsmethode und hardware-gestützter Methoden zur Erzeugung dicht gepackter Texturatlanten. Durch die Kombination von selektiven Zugriffsmethoden auf TFGR mit effizienten Randanpassungsmethoden, wird erstmals ein effizientes und qualitativ hochwertiges Multiresolution Rendering mittels TFGR ermöglicht. Aus dem TFGR werden texturierte sichtunabhängige Approximationen gewonnen. Zur echtzeitfähigen, vollautomatischen Erzeugung aller drei Approximationsformen wird in dieser Arbeit ein Reduktionssystem vorgeschlagen, das diese Approximationsformen verteilt generiert. Für eine effiziente Kommunikation innerhalb dieses Systems werden entsprechende Kompressions-, Caching- und State-Differencing-Mechanismen vorgeschlagen. Lastverteilungsmechanismen sichern eine effiziente Ausnutzung der zur Verfügung stehenden Ressourcen ab. / In this thesis, an application-independent system for the distributed generation of object approximations used for multi-resolution rendering is proposed. The system generates approximations of objects of a scene sent to him in an efficient and fully automatic manner. The system is able to generate different kinds of geometry-based and image-based object approximations. For each given objects of a scene it generates that kind of approximation that is suitable for the current view. That means that its complexity is minimal and that it causes an error in the image generated with this approximation that does not exceed a user-specified threshold. Nailboards are image-based approximations that approximate objects whose size is small compared to the whole scene. In this thesis new kinds of nailboards are presented which can be used efficiently for the approximation of semi-transparent objects and objects in scenes with a dynamic illumination. Capabilities of current graphics hardware are intensively used to generate and render all kinds of Nailboards in real-time. So-called textured view-dependent progressive meshes (VDPM) are used as view dependent geometry-bases approximations for objects whose size is large compared to the whole scene. In this thesis an efficient method for generating VDPM is presented. This method allows the extraction of approximations with optimally adapted texture coordinates without the necessity of an separate optimization step for the texture coordinates in the generation procedure. The textures necessary for the compensation of detail loss are generated using a fast parameterization method from Yoshizawa. The generation of texture atlases is done hardware-accelerated. Further on a hardware-accelerated method for hardware-accelerated multi-resolution rendering using multi chart geometry images (MCGIM) is presented. Out of the MCGIM view-independent geometry-based approximations are extracted. Finally a system for the distributed generation of object approximations is proposed. It generates all three kinds of approximations fully automatic and almost in real time. For an efficient communication within this system suitable compression, caching and state-differencing mechanisms are proposed. Load balancing mechanisms ensure efficient utilization of available resources.