Library

Description: This thesis deals with a Dial-a-Ride problem on trees and considers both offline and online versions of this problem. We study the behavior of certain algorithms on random instances, i.e. we do probabilistic analysis. The focus is on results describing the typical behavior of the algorithms, i.e. results holding with (asymptotically) high probability. For the offline version, we present a simplified proof of a result of Coja-Oghlan, Krumke und Nierhoff. The results states that some heuristic using a minimum spanning tree to approximate a Steiner tree gives optimal results with high probability. This explains why this heuristic produces optimal solutions quite often. In the second part, probabilistic online versions of the problem are introduced. We study the online strategies REPLAN and IGNORE. Regarding the IGNORE strategy we can show that it works almost optimal under high load with high probability.

Description: All-optical telecommunication networks allow for switching connections by lightpaths which can pass several network links without any opto-electronic conversion. Upon arrival of a connection request, it must be decided online, i.e., without knowledge of future requests, if it is accepted and in that case on which lightpaths the connection is routed. This online problem with the goal of maximizing the total profit gained by accepted requests is called Dynamic Singleclass Call Admission Problem (DSCA). We present existing and new algorithms for the DSCA as well as their theoretical and practical evaluation.

Description: Als Cluster Analyse bezeichnet man den Prozess der Suche und Beschreibung von Gruppen (Clustern) von Objekten, so daß die Objekte innerhalb eines Clusters bezüglich eines gegebenen Maßes maximal homogen sind. Die Homogenität der Objekte hängt dabei direkt oder indirekt von den Ausprägungen ab, die sie für eine Anzahl festgelegter Attribute besitzen. Die Suche nach Clustern läßt sich somit als Optimierungsproblem auffassen, wobei die Anzahl der Cluster vorher bekannt sein muß. Wenn die Anzahl der Objekte und der Attribute groß ist, spricht man von komplexen, hoch-dimensionalen Cluster Problemen. In diesem Fall ist eine direkte Optimierung zu aufwendig, und man benötigt entweder heuristische Optimierungsverfahren oder Methoden zur Reduktion der Komplexität. In der Vergangenheit wurden in der Forschung fast ausschließlich Verfahren für geometrisch basierte Clusterprobleme entwickelt. Bei diesen Problemen lassen sich die Objekte als Punkte in einem von den Attributen aufgespannten metrischen Raum modellieren; das verwendete Homogenitätsmaß basiert auf der geometrischen Distanz der den Objekten zugeordneten Punkte. Insbesondere zur Bestimmung sogenannter metastabiler Cluster sind solche Verfahren aber offensichtlich nicht geeignet, da metastabile Cluster, die z.B. in der Konformationsanalyse von Biomolekülen von zentraler Bedeutung sind, nicht auf einer geometrischen, sondern einer dynamischen Ähnlichkeit beruhen. In der vorliegenden Arbeit wird ein allgemeines Clustermodell vorgeschlagen, das zur Modellierung geometrischer, wie auch dynamischer Clusterprobleme geeignet ist. Es wird eine Methode zur Komplexitätsreduktion von Clusterproblemen vorgestellt, die auf einer zuvor generierten Komprimierung der Objekte innerhalb des Datenraumes basiert. Dabei wird bewiesen, daß eine solche Reduktion die Clusterstruktur nicht zerstört, wenn die Komprimierung fein genug ist. Mittels selbstorganisierter neuronaler Netze lassen sich geeignete Komprimierungen berechnen. Um eine signifikante Komplexitätsreduktion ohne Zerstörung der Clusterstruktur zu erzielen, werden die genannten Methoden in ein mehrstufiges Verfahren eingebettet. Da neben der Identifizierung der Cluster auch deren effiziente Beschreibung notwendig ist, wird ferner eine spezielle Art der Komprimierung vorgestellt, der eine Boxdiskretisierung des Datenraumes zugrunde liegt. Diese ermöglicht die einfache Generierung von regelbasierten Clusterbeschreibungen. Für einen speziellen Typ von Homogenitätsfunktionen, die eine stochastische Eigenschaft besitzen, wird das mehrstufige Clusterverfahren um eine Perroncluster Analyse erweitert. Dadurch wird die Anzahl der Cluster, im Gegensatz zu herkömmlichen Verfahren, nicht mehr als Eingabeparameter benötigt. Mit dem entwickelten Clusterverfahren kann erstmalig eine computergestützte Konformationsanalyse großer, für die Praxis relevanter Biomoleküle durchgeführt werden. Am Beispiel des HIV Protease Inhibitors VX-478 wird dies detailliert beschrieben.

Description: The present dissertation deals with the structure of polyhedral subdivisions of point configurations. Of particular interest are the global properties of the set of all subdivisions of a given point configuration. An important open problem in this context is the following: can one always transform any triangulation of a given point configuration to any other triangulation of the same configuration by means of bistellar operations? In other words, is the set of all triangulations of a given point configuration always bistellarly connected? The results presented in this thesis contribute progress from two directions. \begin{itemize} \item The set of all subdivisions that are induced by a polytope projection is in general not bistellarly connected in a generalized sense. This result is obtained by constructing a counterexample to the so-called Generalized Baues Conjecture.'' \item The set of all triangulations of a cyclic polytope forms a bounded poset. The covering relations are given by increasing bistellar operations. Thus we get an affirmative answer to the above question in the case of cyclic polytopes. \end{itemize} In the introduction, the mathematical environment of the structures under consideration is illuminated. The "Generalized Baues Conjecture" has connections to various mathematical concepts, such as combinatorial models for loop spaces, discriminants of polynomials in several variables, etc. The triangulation posets of cyclic polytopes are natural generalizations of the well-studied Tamari lattices in order theory. Moreover, there is a connection to the higher Bruhat orders, which have similar structural properties. As a by-product, the investigations yield the shellability of all triangulations of cyclic polytopes without new vertices. This is in particular interesting because most triangulations of cyclic polytopes are non-regular.

Description: Die vorliegende Dissertation beschäftigt sich mit strukturellen Fragen in der Theorie der polyedrischen Unterteilungen von Punktkonfigurationen. Hierbei sind vor allem globale Eigenschaften der Menge aller Unterteilungen einer gegebenen Punktkonfiguration von Interesse. Eine wichtige ungelöste Frage in diesem Zusammenhang ist die folgende: Ist es immer möglich, von einer beliebigen Triangulierung einer gegebenen Punktkonfiguration zu jeder anderen Triangulierung derselben Konfiguration zu gelangen, indem man sogenannte bistellare Operationen durchführt? Mit anderen Worten, ist die Menge aller Triangulierungen einer gegebenen Punktkonfiguration stets bistellar zusammenhängend? Die Ergebnisse der vorliegenden Doktorarbeit liefern auf zwei Seiten dieser nach wie vor offenen Frage Fortschritte: \begin{itemize} \item Die Menge aller durch eine Polytopprojektion induzierten Unterteilungen ist nicht immer --- in einem verallgemeinerten Sinne --- bistellar zusammenhängend. Dieses Resultat wird durch ein Gegenbeispiel zur sogenannten "Verallgemeinerten Baues Vermutung"' erzielt. \item Die Menge aller Triangulierungen eines zyklischen Polytops bildet eine beschränkte Halbordnung. Die Ueberdeckungsrelationen sind gerichtete bistellare Operationen. Für zyklische Polytope ist die obige Frage nach bistellarem Zusammenhang also positiv beantwortet. \end{itemize} In der Einleitung wird das mathematische Umfeld der betrachteten Strukturen näher beleuchtet: Die "Verallgemeinerte Baues Vermutung" steht in Verbindung mit verschiedensten mathematischen Konzepten, angefangen von kombinatorischen Modellen von Schleifenräumen bis hin zu Diskriminanten von Polynomen in mehreren Variablen. Die Triangulierungs-Halbordnungen von zyklischen Polytopen sind zugleich natürliche Verallgemeinerungen der gut studierten Tamari-Verbände in der Ordnungstheorie. Ausserdem existiert ein Zusammenhang mit den höheren Bruhat-Ordnungen, die ähnliche Struktureigenschaften aufweisen. Ein Nebenprodukt der Untersuchungen ist die Schälbarkeit aller Triangulierungen von zyklischen Polytopen ohne neue Ecken. Das ist um so interessanter, da die meisten Triangulierungen von zyklischen Polytopen nicht-regulär sind.