Library

Description: Im Mai 2009 wurde Wolfram|Alpha gestartet, ein Service, der seinen Namen von seinem Entwickler, dem britischen Mathematiker Stephen Wolfram, ableitet. Dem Benutzer soll nicht nur eine Liste von Webseiten als Ergebnis auf Anfragen geliefert werden, sondern Antworten auf konkrete Fragen geben. In diesem Report soll gezeigt werden, warum sichWolframjAlpha von Suchmaschinen abgrenzt und was die Berechnung von Antworten auf natürlichsprachliche Fragen möglich machen kann.

Description: Wolfram|Alpha was started in May 2009 and it's a service whose name derives from the british mathematician Stephen wolfram. As a result for a request the user is not just supported with a list of websites but with answers for concrete questions. In this report it will be shown why Wolfram|Alpha seperates from search engines and moreover what makes the computation of answers for natural language queries possible.

Description: Executing applications in the Grid often requires access to multiple geographically distributed resources. In a Grid environment, these resources belong to different administrative domains, each employing its own scheduling policy. That is, at which time an activity (e.g., compute job, data transfer) is started, is decided by the resource's local management system. In such an environment, the coordinated execution of distributed applications requires guarantees on the quality of service (QoS) of the needed resources. Reserving resources in advance is an accepted means to obtain QoS guarantees from a single provider. The challenge, however, is to coordinate advance reservations of multiple resources. This work presents a system architecture and mechanisms to coordinate multiple advance reservations -- called co-reservations -- for delivering QoS guarantees to complex applications. We formally define the co-reservation problem as an optimization problem. The presented model supports three dimensions of freedom: the start time, the duration and the service level of a reservation. Requests and resources are described in a simple language. After matching the static properties and requirements of either side in a mapping, the reservation mechanism probes information about the future status of the resources. The versatile design of the probing step allows the efficient processing of requests, but also lets the resources express their preferences among the myriads of reservation candidates. Next, the best mapping is found through an implementation of the formal co-reservation model. Then, the mapping has to be secured, i.e., resources need to be allocated to a co-reservation candidate with all-or-nothing semantics. We study several goal-driven sequential and concurrent allocation mechanisms and define schemes for handling allocation failures. Finally, we introduce the concept of virtual resources for seamlessly embedding co-reservations into Grid resource management.

Description: Die Ausführung von Anwendungen erfordert oft mehrere, geographisch verteilte Ressourcen. In Grid-Umgebungen gehören diese Ressourcen zu verschiedenen administrativen Organisationen, wobei jede ihre eigene Schedulingregeln verwendet. Das bedeutet, zu welcher Zeit eine Aktivität gestartet wird (z.B. ein Rechenjob), wird vom lokalen Ressourcenmanagementsystem entschieden. Die koordinierte Ausführung von verteilten Anwendungen erfordert Dienstgütegarantien für die benötigten Ressourcen. Das Reservieren von Ressourcen im Voraus ist ein Mittel, um Dienstgütegarantien von einem einzelnen Ressourcenanbieter zu erhalten. Die Herausforderung in dieser Arbeit ist, Vorausreservierungen von mehreren Ressourcen zu koordinieren. Es wird ein System für die Koordinierung mehrerer Vorausreservierungen -- Co-Reservierungen genannt -- für die Bereitstellung von Dienstgütegarantien vorgestellt. Wir definieren das Co-Reservierungsproblem als Optimierungsproblem. Das vorgestellte Modell unterstützt drei Freiheitsgrade: die Startzeit, die Dauer und die Dienstgüte einer Reservierung. Anfragen und Ressourcen werden in einer einfachen Sprache beschrieben. Nachdem statische Eigenschaften und Anforderungen beider Seiten überprüft wurden, ermittelt der Reservierungsmechanismus Informationen über den zukünftigen Zustand der Ressourcen. Dieser Schritt ist so allgemein gehalten, daß er sowohl ein effizientes Bearbeiten der Anfragen erlaubt als auch den Ressourcen ermöglicht ihre Präferenzen auszudrücken. Im Anschluss wird die optimale Zuweisung von Anfragen zu Ressourcen ermittelt. Im letzten Schritt muss diese Zuweisung umgesetzt werden, d.h., entweder alle oder keine Ressource wird allokiert. Es werden mehrere sequentielle und parallele Allokationsverfahren vorgestellt sowie deren Auswirkung auf verschiedene Metriken untersucht. Die Einbettung von Co-Reservierungen in das Grid-Ressourcenmanagement wird anhand des Konzeptes der virtuellen Ressource dargestellt.

Description: The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role.

Description: We give the basic definitions and some theoretical results about hyperdeterminants, introduced by A.~Cayley in 1845. We prove integrability (understood as $4d$-consistency) of a nonlinear difference equation defined by the $2 \times 2 \times 2$ - hyperdeterminant. This result gives rise to the following hypothesis: the difference equations defined by hyperdeterminants of any size are integrable. We show that this hypothesis already fails in the case of the $2\times 2\times 2\times 2$ - hyperdeterminant.

Description: Starting from the conservation laws for mass, momentum and energy together with a three species, bulk microphysic model, a model for the interaction of internal gravity waves and deep convective hot towers is derived by using multiscale asymptotic techniques. From the resulting leading order equations, a closed model is obtained by applying weighted averages to the smallscale hot towers without requiring further closure approximations. The resulting model is an extension of the linear, anelastic equations, into which moisture enters as the area fraction of saturated regions on the microscale with two way coupling between the large and small scale. Moisture reduces the effective stability in the model and defines a potential temperature sourceterm related to the net effect of latent heat release or consumption by microscale up- and downdrafts. The dispersion relation and group velocity of the system is analyzed and moisture is found to have several effects: It reduces energy transport by waves, increases the vertical wavenumber but decreases the slope at which wave packets travel and it introduces a lower horizontal cutoff wavenumber, below which modes turn into evanescent. Further, moisture can cause critical layers. Numerical examples for steadystate and timedependent mountain waves are shown and the effects of moisture on these waves are investigated.

Description: Aktuelle Entwicklungen zeigen, dass Peer-to-Peer (P2P) Anwendungen wie Skype oder Bittorrent im Internet immer mehr an Bedeutung gewinnen. In den letzten Jahren hat es einen explosionsartigen Anstieg an Nutzern und Daten in solchen Netzen gegeben. Dabei stellt der eigentliche Dateitransfer zwischen zwei Rechnern kein großes Problem mehr dar und auch der Speicherbedarf für die große Menge an Daten kann durch die Weiterentwicklung der Hardware gut gedeckt werden. Das eigentliche Problem liegt vielmehr darin, den Rechner zu finden, der die gewünschten Daten hat. Client-Server Architekturen, wie zum Beispiel Napster, haben sich als ungünstig herausgestellt. Wenige Server, die eine große Anzahl an Clients bedienen müssen, sind einerseits sehr anfällig gegenüber Angriffen und Ausfällen (Single Point of Failure)und kommen auch nicht mit der ständig wachsenden Anzahl an Nutzern zurecht. Verteilte Hashtabellen (DHT) bieten hier einen guten Lösungsansatz, der mit einer großen Anzahl an Nutzern skaliert und ausfallsicher ist. Andere dezentrale Lösungen, wie zum Beispiel das P2P Netzwerk Gnutella haben zwar das Problem des Single Point of Failure gelöst, jedoch haben sie starke Nachteile bei der Suche nach Keys. Bei einer Suche wird ein Broadcast verwendet (jeder schickt die Anfrage an jeden weiter) und damit ein enormer Netzwerkverkehr erzeugt. In "Why Gnutella Can't Scale. No, Really" wird erklärt, dass eine Suchanfrage bei Standardeinstellungen in der Clientsoftware einen Netzwerkverkehr von 17MB erzeugt. Deswegen wird zusätzlich eine Lösung benötigt, die Keys und Values geordnet verteilt, damit sie gezielt gesucht werden können. Aus diesem Grund beschäftigt sich die folgende Arbeit mit einer völlig dezentralen Architektur, die außerdem eine sinnvolle Platzierung der Keys vornimmt. Die dezentrale Architektur hat den Vorteil, dass die Endgeräte den Hauptteil des Dienstes selbst erbringen und damit jeder zusätzliche Teilnehmer seine eigenen Ressourcen beisteuert. Diese Arbeit präsentiert Chord#, eine dezentrale, skalierbare und selbstorganisierende verteilte Hashtabelle. Chord# wurde ausgewählt, da in dieser Arbeit auch Wert auf Bereichsabfragen gelegt wurde. Diese sind zum Beispiel bei dem Chord Algorithmus nicht möglich, da dieser eine Hashfunktion für die Keys verwendet und somit die Daten zwar gleichmäßig aber unsortiert auf die Teilnehmer verteilt. Es wird in dieser Arbeit gezeigt, dass mit Hilfe von Chord# auch ohne die Hashfunktion gute Ergebnisse erzielt werden. Außerdem können durch den Verzicht auf die Hashfunktion Bereichsabfragen ermöglicht werden. Dafür wird der Chord# Algorithmus in Java implementiert (ca. 1500 Zeilen Code) und in dem Forschungsnetz PlanetLab ausführlich auf Laufzeiten, Instandhaltungskosten und Skalierung getestet.

Description: Recent developments show that peer-to-peer (p2p) applications, such as Skype or Bittorrent have become increasingly important in the internet. Over the last years there has been a rapid growth of both users and data in such networks. However, the actual file transfer between two peers is not really an issue anymore. The same holds true for data storage, since the new hardware grants users enough space to store their data. The real problem is finding the peers that possess the desired data. Client-server architectures like Napster have proven to be ineffective addressing that problem. One or few servers being responsible for many peers are vulnerable to attacks or failures (single point of failure). Additionally, they are unable to cope with the rapidly growing number of peers. Distributed hashtables (DHT) are a good approach to solve these problems, since they scale nicely with large numbers of peers and provide a high tolerance for errors. Other decentralized solutions like the p2p network Gnutella solved the problem of Single Point of Failure but show considerable disadvantages when searching for keys. The peers in Gnutella use a broadcast (sending the message to all peers they know)resulting in massive traffic. According to "Why Gnutella Can't Scale. No, Really.", each search using standard client settings yields 17MB traffc. This calls for a different solution, distributing keys and values to peers quickly and efficiently so they can be found fast. For that reason this thesis focuses on a fully distributed architecture using organized key placement. One major advantage of distributed architecture is the fact, that the peers do most of the work themselves. This way, new peers joining the network add resources to it. This thesis presents Chord#, a scalable, self-organizing and completely decentralized DHT. It has been chosen due to its capability to allow range queries. The regular Chord algorithm does not support range queries, because of the hashfunction it uses to evenly distribute the keys among the peers. This results in similar or logical coherent keys most likely not being close together in the network. This thesis shows Chord# achieving same results as Chord - regarding performance costs - without the hashfunction. In dropping the hashfunction this algorithm allows the use of range queries. The Chord# algorithm is implemented in Java (about 1500 lines of code) and thoroughly tested in the research network PlanetLab. The results are evaluated regarding performance, maintenance and scalability.

Description: One of the biggest impacts on the performance of a Distributed Hash Table (DHT), once established, is its ability to balance load among its nodes. DHTs supporting range queries for example suffer from a potentially huge skew in the distribution of their items since techniques such as consistent hashing can not be applied. Thus explicit load balancing schemes need to be deployed. Several such schemes have been developed and are part of recent research, most of them using only information locally available in order to scale to arbitrary systems. Gossiping techniques however allow the retrieval of fairly good estimates of global information with low overhead. Such information can then be added to existing load balancing algorithms that can use the additional knowledge to improve their performance. Within this thesis several schemes are developed that use global information like the average load and the standard deviation of the load among the nodes to primarily reduce the number of items an algorithm moves to achieve a certain balance. Two novel load balancing algorithms have then been equipped with implementations of those schemes and have been simulated on several scenarios. Most of these variants show better balance results and move far less items than the algorithms they are based on. The best of the developed algorithms achieves a 15-30% better balance and moves only about 50-70% of the number of items its underlying algorithm moves. This variation is also very robust to erroneous estimates and scales linearly with the system size and system load. Further experiments with self-tuning algorithms that set an algorithm’s parameter according to the system’s state show that even more improvements can be gained if additionally applied. Such a variant based on the algorithm described by Karger and Ruhl shows the same balance improvements of 15-30% as the variant above but reduces the number of item movements further to 40-65%.

Description: In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.

Description: Eines der Hauptanliegen bei der Initiierung des Kooperativen Bibliotheksverbundes Berlin-Brandenburg (KOBV) war die Schaffung einer modernen, leistungsfähigen Informationsinfrastruktur unter Einbeziehung möglichst aller Bibliotheken der in ihrer Dichte und Vielfalt in Deutschland einmaligen Bibliothekslandschaft. Sie wurde beim Aufbau des KOBV durch die Wahl des Verbundmodelles mit seinen offenen, integrativen Strukturen befördert. Die Ziele und Strategien des KOBV leiten sich aus dem Grundauftrag der Bibliotheken her, ihre NutzerInnen optimal mit Medien und Informationen zu versorgen. Mit dem KOBV haben die Bibliotheken eine gemeinsame Plattform und ein regionales Netzwerk geschaffen, mit deren Hilfe sie die Informationsinfrastruktur in Berlin und Brandenburg zusammen aufgebaut und grundlegend verbessert haben. Nach rund elf Jahren ist der KOBV in eine neue Phase eingetreten, indem er – unter Wahrung seiner institutionellen Eigenständigkeit – eine Strategische Allianz mit dem Bibliotheksverbund Bayern (BVB) eingegangen ist und die bislang auf die Region bezogene Kooperation der Bibliotheken überregional ausgeweitet hat. Wenn auch die Universalbibliotheken des KOBV in dieser Zusammenarbeit einen Kurswechsel zur zentralen Katalogisierung vollziehen, bedeutet dies für den KOBV insgesamt keinen Paradigmenwechsel: Er bleibt ein dezentraler Verbund und wird sein flexibles technisches Mischkonzept von verteilter und zentraler Datenhaltung fortführen. Dieses lässt den Bibliotheken die Freiheit zu entscheiden, ob sie zentral oder dezentral katalogisieren möchten. Die KOBV-Zentrale, die im KOBV keine Aufgaben in der Katalogisierung wahrnimmt, wird wie bislang allen Mitgliedsbibliotheken die ASP-Dienste und weiteren Angebote gleichermaßen zur Verfügung stellen und die Dienstleistungen für NutzerInnen und Bibliotheken weiter ausbauen. Mit dem vorhandenen Know How, der eingesetzten modernen Technologie und der strategischen Entscheidung, Ressourcen und Kompetenzen mit dem BVB zu bündeln und durch verbundübergreifende arbeitsteilige Verfahren Synergien zu gewinnen, ist der KOBV gut aufgestellt, um die Herausforderungen der kommenden Jahre anzugehen und das Leistungsspektrum der KOBV-Bibliotheken durch die Entwicklung neuer Dienste auszuweiten.

Description: Entwurf und Entwicklung eines eingebetteten Hauptspeicher-Datenbanksystems mit Snapshot-Reads.

Description: Design and implementation of an embedded main memory database with snapshot reads.

Description: Das Ziel dieser Arbeit ist die Schaffung einer Zugriffs-Komponente für das Grid-Datenmanagement-System ZIB-DMS, das dessen transparente Einbindung in den Verzeichnisbaum eines Linux-Systems erlaubt. Dazu wird unter Verwendung des FUSE-Rahmenwerkes ein Userspace-Dateisystem mit Anbindung an das ZIB-DMS konzipiert und implementiert. Im Fokus stehen dabei die Abbildung der erweiterten Verwaltungsmechanismen des Systems auf die limitierte Schnittstelle hierarchischer Dateisysteme und die dazu notwendigen Änderungen am ZIB-DMS.

Description: The goal of this work is to create an access component for the Grid data management system ZIB-DMS, that allows a transparent integration into the directory tree of a Linux system. For this purpose the FUSE framework is used to design and implement a userspace file system with connections to the ZIB-DMS. The focus is on the mapping of the extended management mechanisms of the system to the limited interface of hierarchical file systems and the therefore necessary changes to ZIB-DMS.

Description: We present a framework for transactional data access on data stored in a DHT. It allows to atomically read and write items and to run distributed transactions consisting of a sequence of read and write operations on the items. Items are symmetrically replicated in order to achieve durability of data stored in the SON. To provide availability of items despite the unavailability of some replicas, operations on items are quorum-based. They make progress as long as a majority of replicas can be accessed. Our framework processes transactions optimistically with an atomic commit protocol that is based on Paxos atomic commit. We present algorithms for the whole framework with an event based notation. Additionally we discuss the problem of lookup inconsistencies and its implications on the one-copy serializability property of the transaction processing in our framework.

Description: When planning teams for projects with specific goals, employees of a company have to group together so well, that all necessary knowledge for conquering the project’s challenges are met within the member’s skills. A tool that facilitates semantic web technologies can support the team recruiter, who is responsible for chosing the members of the team, in terms of finding the most efficient combinations of the company’s employees based on their expertises.

Description: Key/value stores which are built on structured overlay networks often lack support for atomic transactions and strong data consistency among replicas. This is unfortunate, because consistency guarantees and transactions would allow a wide range of additional application domains to benefit from the inherent scalability and fault-tolerance of DHTs. The Scalaris key/value store supports strong data consistency and atomic transactions. It uses an enhanced Paxos Commit protocol with only four communication steps rather than six. This improvement was possible by exploiting information from the replica distribution in the DHT. Scalaris enables implementation of more reliable and scalable infrastructure for collaborative Web services that require strong consistency and atomic changes across multiple items.

Description: Basierend auf einem vorhandenen Ansatz zur Einführung von anisotropen Tetraedern im Randbereich eines reinen Tetraedergitters wird ein Gittergenerator für hybride Gitter implementiert. Das hybride Gitter besteht in Randnähe primär aus anisotropen Prismen und im Inneren der Geometrie aus isotropen Tetraedern. Eine erhöhte Auflösung im Randbereich soll zu besseren Ergebnissen von numerischen Strömungssimulationen führen, für welche eine problemangepasste Diskretisierung des zu untersuchenden Gebietes benötigt wird. In dem zuvor genannten Ansatz wird eine Reihe von Übergangselementen vorgeschlagen, die an scharfen Kanten der Oberfläche platziert werden sollen. Im Rahmen dieser Diplomarbeit wird die Idee der Übergangselemente aufgegriffen und bei hybriden Gittern eingesetzt, um auch komplexe Eingabegeometrien vergittern zu können. Der ursprüngliche Gittergenerierungprozess wird überarbeitet und erweitert. Eine neue Menge an Übergangselementen wird eingeführt, es werden gekrümmte Extrusionsvektoren verwendet und es wird die Auswertung der medialen Oberfläche vorgenommen, um Überschneidungen im hybriden Gitter zu vermeiden. Der Gittergenerator wird als Modul in das Visualisierungs- und Analyseprogramm Amira implementiert und die erstellten hybriden Gitter werden auf ihre Elementqualität und die Güte der Strömungssimulationsergebnisse hin überprüft.

Description: Based on an existing approach for the introduction of anisotropic tetrahedra near the surface boundary of a tetrahedral grid a grid generator for hybrid grids is implemented. The hybrid grid consists near the surface boundary primarily of anisotropic prisms and inside the geometry of isotropic tetrahedra. An increased resolution near the boundary should lead to better results of numerical flow simulations, which needs a problem specific discretization of the analyzed domain. In the aforementioned approach a set of transition elements is suggested, which should be placed at sharp surface corners. As a part of this diploma thesis the concept of using transition elements is applied for creating hybrid grids even for very complex input geometries. The initial grid generation process is revised and enhanced. A new set of transition elements is introduced, curved extrusion vectors are used and the medial surface is evaluated to avoid intersections in the hybrid grid. The grid generator is implemented as a module for the visualization and analysis tool Amira and the element quality of the generated hybrid grids and the quality of flow simulations performed on the grids are tested.

Description: We consider an auction of slots to run trains through a railway network. In contrast to the classical setting for combinatorial auctions, there is not only competition for slots, but slots can mutually exclude each other, such that general conflict constraints on bids arise. This turns the winner determination problem associated with such an auction into a complex combinatorial optimization problem. It also raises a number of auction design questions, in particular, on incentive compatibilty. We propose a single-shot second price auction for railway slots, the Vickrey Track Auction (VTA). We show that this auction is incentive compatible, i.e., rational bidders are always motivated to bid their true valuation, and that it produces efficient allocations, even in the presence of constraints on allocations. These properties are, however, lost when rules on the submission of bids such as, e.g., lowest bids, are imposed. Our results carry over to generalized" Vickrey auctions with combinatorial constraints.

Description: Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to be propagated causing delays of subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bi-criteria optimization approach. On the one hand we want to maximize the profit of a schedule, that is more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in [BorndoerferSchlechte2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see [Ehrgott2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional $\epsilon$-constraint remains solvable in polynomial time. Finally, we present some preliminary results on macroscopic real-world data of a part of the German long distance railway network.

Description: The latest machine generation installed at supercomputer centres in Germany offers a peak performance in the tens of Tflop/s range. We study performance and scaling of our quantum chromodynamics simulation programme BQCD that we obtained on two of these machines, an IBM Blue Gene/L and an SGI Altix 4700. We compare the performance of Fortran/MPI code with assembler code. The latter allows to exploit concurrency at more levels, in particular in overlapping communication and computation as well as prefetching data from main memory.

Description: We study the optimal control of a maximum-norm objective functional subject to an elliptic-type PDE and pointwise state constraints. The problem is transformed into a problem where the non-differentiable L^{\infty}-norm in the functional will be replaced by a scalar variable and additional state constraints. This problem is solved by barrier methods. We will show the existence and convergence of the central path for a class of barrier functions. Numerical experiments complete the presentation.

Description: Der Artikel gibt einen Einblick in das reiche Feld der Zusammenarbeit zwischen Mathematik und Medizin. Beispielhaft werden drei Erfolgsmodelle dargestellt: Medizinische Bildgebung, mathematische Modellierung und Biosignalverarbeitung im Bereich der Dynamik des Herzens sowie mathematische Modellierung und Simulation in der Krebstherapie Hyperthermie und der Mund-Kiefer-Gesichts-Chirurgie. In allen Fällen existiert ein Gleichklang der Interessen von Medizin und Mathematik: Beide Disziplinen wollen die Resultate schnell und zuverlässig. Für die Klinik heißt das, dass notwendige Rechnungen in möglichst kurzer Zeit, und zwar auf dem PC, ablaufen müssen und dass die Resultate so genau und belastbar sein müssen, dass medizinische Entscheidungen darauf aufbauen können. Für die Mathematik folgt daraus, dass höchste Anforderungen an die Effizienz der verwendeten Algorithmen und die darauf aufbauende Software in Numerik und Visualisierung zu stellen sind. Jedes Kapitel endet mit einer Darstellung der Perspektive des jeweiligen Gebietes. Abschließend werden mögliche Handlungsoptionen für Politik und Wirtschaft diskutiert.

Description: This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use. We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques.

Description: We study performance and scaling of the Berlin Quantum Chromodynamics Program (BQCD) on the SGI Altix 4700 at Leibniz Supercomputing Centre (LRZ). We employ different communication methods (MPI, MPI with two OpenMP threads per process, as well as the shmem library) and run the MPI version on the two types of nodes of that machine. For comparison with other machines we made performance measurements on an IBM p690 cluster and a Cray XT4.

Description: Mit dem Informationsdienst Math&Industry soll ein Prototyp eines dezentralen Informationssystems für Förderprogramme und Forschungsprojekte geschaffen werden, das sich auf andere Programme (bezüglich angewandter Mathematik, aber auch darüber hinaus) übertragen lässt. Das betrifft sowohl die Konzeption (Strukturierung der Informationen) als auch die Werkzeuge, die anderen BMBF-Förderprogrammen zur Verfügung gestellt werden können. Damit sollen diese in die Lage versetzt werden, die in Math&Industry entwickelten Konzepte und Werkzeuge an ihre spezifischen Bedürfnisse anzupassen.

Description: In dieser Arbeit wird eine Serie von Remeshing-Verfahren um die Berücksichtigung von nicht-mannigfaltigen Dreiecksvernetzungen und Merkmalskantenzügen erweitert. Die betrachteten Verfahren arbeiten im Wesentlichen lokal. Daher können die im Rahmen dieser Arbeit entwickelten Erweiterungen, die nicht-mannigfaltige Kantenzüge und Merkmalskantenzüge betreffen, separat beschrieben werden. Dabei wird ein Ansatz verfolgt, beide Arten von besonderen Kantenzügen aufgrund ihrer Gemeinsamkeiten einheitlich zu behandeln. Dieser besteht zum einen darin, eine Korrespondenz zwischen Kantenzügen auf der Eingabe- und der Ausgabefläche zu erhalten, indem die Remeshing-Operationen auf den Kantenzügen in entsprechend eingeschränkter Weise verwendet werden. Zum anderen wird beschrieben, wie die Abtastdichte der Kantenzüge dynamisch an die Abtastdichte der Umgebung angepasst werden kann, um für weitgehende Isotropie in der Nähe von Merkmalskantenzügen zu sorgen.

Description: A unified approach for consistent remeshing of arbitrary non-manifold triangle meshes with additional user-defined feature lines is presented. The method is based on local operations only and produces meshes of high regularity and triangle quality while preserving the geometry as well as topology of the feature lines as well as the input mesh.

Description: This work introduces a novel streamline seeding technique based on dual streamlines that are orthogonal to the vector field, instead of tangential. The greedy algorithm presented here produces a net of orthogonal streamlines that is iteratively refined resulting in good domain coverage and a high degree of continuity and uniformity. The algorithm is easy to implement and efficient, and it naturally extends to curved surfaces.

Description: In dieser Arbeit wird eine neue Strategie zur Platzierung von Stromlinien vorgestellt. Hierzu werden zusätzliche duale Stromlinien verwendet, die --im Gegensatz zur üblichen Definition-- orthogonal zum Vektorfeld verlaufen. Der vorgestellte Greedy-Algorithmus berechnet ein Netz aus orthogonalen Stromlinien, welches iterativ verfeinert wird, was zu einer guten Abdeckung der Domäne und einer gleichmäßigen Verteilung der Stromlinien führt. Es handelt sich um einen einfach zu implementierenden und effizienten Algorithmus, der direkt auf gekrümmten Oberflächen anwendbar ist.

Description: In dieser Diplomarbeit wird untersucht, wie auf der Basis von Literaturreferenzen ein Zitationsgraph durch ein automatisches Verfahren aufgebaut werden kann. Zur Lösung des Problems werden Probabilistische Relationale Modelle herangezogen. Eine problemspezifische Erweiterung des Modells ermöglicht es, dass bestehende Unsicherheiten im Zitationsgraphen mit Hilfe eines Inferenzverfahrens aufgelöst werden können. Zur Evaluierung des Verfahren werden Experimente auf dem Cora-Datensatz durchgeführt.

Description: This article is about the optimal track allocation problem (OPTRA) to find, in a given railway network, a conflict free set of train routes of maximum value. We study two types of integer programming formulations: a standard formulation that models block conflicts in terms of packing constraints, and a new extended formulation that is based on additional configuration' variables. We show that the packing constraints in the standard formulation stem from an interval graph, and that they can be separated in polynomial time. It follows that the LP relaxation of a strong version of this model, including all clique inequalities from block conflicts, can be solved in polynomial time. We prove that the extended formulation produces the same LP bound, and that it can also be computed with this model in polynomial time. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view, because it features a constant number of rows and is therefore amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hannover-Fulda-Kassel region of the German long distance railway network are reported.

Description: We study barrier methods for state constrained optimal control problems with PDEs. In the focus of our analysis is the path of minimizers of the barrier subproblems with the aim to provide a solid theoretical basis for function space oriented path-following algorithms. We establish results on existence, continuity and convergence of this path. Moreover, we consider the structure of barrier subdifferentials, which play the role of dual variables.

Description: For the treatment of equilibrated molecular systems in a heat bath we propose a transition state theory that is based on conformation dynamics. In general, a set-based discretization of a Markov operator ${\cal P}^\tau$ does not preserve the Markov property. In this article, we propose a discretization method which is based on a Galerkin approach. This discretization method preserves the Markov property of the operator and can be interpreted as a decomposition of the state space into (fuzzy) sets. The conformation-based transition state theory presented here can be seen as a first step in conformation dynamics towards the computation of essential dynamical properties of molecular systems without time-consuming molecular dynamics simulations.

Description: We present a middleware to store multidimensional data sets on Internet-scale distributed systems and to efficiently perform range queries on them. Our structured overlay network \emph{SONAR (Structured Overlay Network with Arbitrary Range queries)} puts keys which are adjacent in the key space on logically adjacent nodes in the overlay and is thereby able to process multidimensional range queries with a single logarithmic data lookup and local forwarding. The specified ranges may have arbitrary shapes like rectangles, circles, spheres or polygons. Empirical results demonstrate the routing performance of SONAR on several data sets, ranging from real-world data to artificially constructed worst case distributions. We study the quality of SONAR's routing information which is based on local knowledge only and measure the indegree of the overlay nodes to find potential hot spots in the routing process. We show that SONAR's routing table is self-adjusting, even under extreme situations, keeping always a maximum of $\lceil \log N \rceil$ routing entries.

Description: \begin{abstract} In systems biology, the stochastic description of biochemical reaction kinetics is increasingly being employed to model gene regulatory networks and signalling pathways. Mathematically speaking, such models require the numerical solution of the underlying evolution equat ion, also known as the chemical master equation (CME). Up to now, the CME has almost exclusively been treated by Monte-Carlo techniques, the most prominent of which is the simulation algorithm suggest ed by Gillespie in 1976. Since this algorithm requires an update for each single reaction event, realizations can be computationally very costly. As an alternative, we here propose a novel approach, which focuses on the discrete partial differential equation (PDE) structure of the CME and thus allows to adopt ideas from adaptive discrete Galerkin methods (as designed by two of the present authors in 1989), which have proven to be highly efficient in the mathematical modelling of polyreaction kinetics. Among the two different options of discretizing the CME as a discrete PDE, the method of lines approach (first space, then time) and the Rothe method (first time, then space), we select the latter one for clear theoretical and algorithmic reasons. First numeric al experiments at a challenging model problem illustrate the promising features of the proposed method and, at the same time, indicate lines of necessary further research. \end{abstract}

Description: Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or $\frac{1}{2}$, such cuts are known as $\{0,\frac{1}{2}\}$-cuts. It has been proven by Caprara and Fischetti (1996) that separation of $\{0,\frac{1}{2}\}$-cuts is NP-hard. In this paper, we study ways to separate $\{0,\frac{1}{2}\}$-cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated $\{0,\frac{1}{2}\}$-cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the algorithmic framework. Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers.

Description: In this paper a Godunov-type projection method for computing approximate solutions of the zero Froude number (incompressible) shallow water equations is presented. It is second-order accurate and locally conserves height (mass) and momentum. To enforce the underlying divergence constraint on the velocity field, the predicted numerical fluxes, computed with a standard second order method for hyperbolic conservation laws, are corrected in two steps. First, a MAC-type projection adjusts the advective velocity divergence. In a second projection step, additional momentum flux corrections are computed to obtain new time level cell-centered velocities, which satisfy another discrete version of the divergence constraint. The scheme features an exact and stable second projection. It is obtained by a Petrov-Galerkin finite element ansatz with piecewise bilinear trial functions for the unknown incompressible height and piecewise constant test functions. The stability of the projection is proved using the theory of generalized mixed finite elements, which goes back to Nicola{\"i}des (1982). In order to do so, the validity of three different inf-sup conditions has to be shown. Since the zero Froude number shallow water equations have the same mathematical structure as the incompressible Euler equations of isentropic gas dynamics, the method can be easily transfered to the computation of incompressible variable density flow problems.

Description: Die Diplomarbeit präsentiert ein Transaktionsverfahren für strukturierte Overlay-Netzwerke, das an die Erfordernisse verteilter Informationssysteme mit relationalem Datenmodell angepasst ist. Insbesondere wird der Einsatz von Transaktionen für verteilte Wikis betrachtet, die moderne Funktionalitäten, wie Metadaten und zusätzliche Indexe für die Navigation, unterstützen. Konsistenz und Dauerhaftigkeit der gespeicherten Daten erfordert die Behandlung von Knotenausfällen. Die Arbeit schlägt dafür das Zellenmodell vor: Das Overlay wird aus replizierten Zustandsmaschinen gebildet, um Verfügbarkeit zu gewährleisten. Das Transaktionsverfahren baut darauf auf und verwendet Two-Phase-Commit mit Fehlererkennung und Widerherstellung von ausgefallenen Transaktionsmanagern. Anwendungen wird eine Auswahl an pessimistischen und hybrid-optimistischen Nebenläufigkeitskontrollverfahren geboten, die die Minimierung von Latenzeffekten und die schnelle Ausführung von Nur-Lese-Transaktionen ermöglichen. Für die Beispielanwendung Wiki wird der erforderliche Pseudocode angegeben und die verschiedenen Nebenläufigkeitskontrollverfahren hinsichtlich ihrer Nachrichtenkomplexität verglichen.

Description: The diploma thesis presents a transaction processing scheme for structured overlay networks and uses it to develop a distributed Wiki application based on a relational data model. The Wiki supports rich metadata and additional indexes for navigation purposes. Ensuring consistency and durability requires handling of node failures. Such failures are masked by providing high availability of nodes. This in turn is achieved by constructing the overlay from replicated state machines (cell model). Atomicity is realized using two phase commit with additional support for failure detection and restoration of the transaction manager. The developed transaction processing scheme provides the application with a mixture of pessimistic, hybrid optimistic and multiversioning concurrency control techniques to minimize the impact of replication on latency and optimize for read operations. The pseudocode of the relevant Wiki functions is presented and the different concurrency control techniques are evaluated in terms of message complexity.

Description: We provide information on the Survivable Network Design Library (SNDlib), a data library for fixed telecommunication network design that can be accessed at http://sndlib.zib.de. In version 1.0, the library contains data related to 22 networks which, combined with a set of selected planning parameters, leads to 830 network planning problem instances. In this paper, we provide a mathematical model for each planning problem considered in the library and describe the data concepts of the SNDlib. Furthermore, we provide statistical information and details about the origin of the data sets.

Description: The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported.

Description: We consider a multicommodity routing problem, where demands are released \emph{online} and have to be routed in a network during specified time windows. The objective is to minimize a time and load dependent convex cost function of the aggregate arc flow. First, we study the fractional routing variant. We present two online algorithms, called Seq and Seq$^2$. Our first main result states that, for cost functions defined by polynomial price functions with nonnegative coefficients and maximum degree~$d$, the competitive ratio of Seq and Seq$^2$ is at most $(d+1)^{d+1}$, which is tight. We also present lower bounds of $(0.265\,(d+1))^{d+1}$ for any online algorithm. In the case of a network with two nodes and parallel arcs, we prove a lower bound of $(2-\frac{1}{2} \sqrt{3})$ on the competitive ratio for Seq and Seq$^2$, even for affine linear price functions. Furthermore, we study resource augmentation, where the online algorithm has to route less demand than the offline adversary. Second, we consider unsplittable routings. For this setting, we present two online algorithms, called U-Seq and U-Seq$^2$. We prove that for polynomial price functions with nonnegative coefficients and maximum degree~$d$, the competitive ratio of U-Seq and U-Seq$^2$ is bounded by $O{1.77^d\,d^{d+1}}$. We present lower bounds of $(0.5307\,(d+1))^{d+1}$ for any online algorithm and $(d+1)^{d+1}$ for our algorithms. Third, we consider a special case of our framework: online load balancing in the $\ell_p$-norm. For the fractional and unsplittable variant of this problem, we show that our online algorithms are $p$ and $O{p}$ competitive, respectively. Such results where previously known only for scheduling jobs on restricted (un)related parallel machines.

Description: Die Zentrale des Kooperativen Bibliotheksverbunds Berlin-Brandenburg (KOBV) betreibt seit Januar 2004 das KOBV-Portal, in dem u.a. vielfältige Open-Linking-Dienste eingebunden sind. Dieser Beitrag erläutert Open-Linking allgemein und stellt die KOBV spezifischen Dienste im Detail vor. Dabei wird auch die Zugriffsentwicklung auf die KOBV-Open-Linking-Dienste evaluiert. Ein Ergebnis ist, dass signifikante Steigerungen der Nutzung erst dann bewirkt werden, wenn Maßnahmen durchgeführt werden, die erstens die Open-Linking-Dienste stärker ins Bewusstsein der NutzerInnen rücken und zweitens den Weg dorthin im KOBV-Portal verkürzen. Vor allem muss ein schneller Weg zu den Open-Linking-Diensten gewährleistet sein, um die Nutzung deutlich zu steigern. Um zusätzlich den Bekanntheitsgrad der Open-Linking-Dienste bundesweit zu erhöhen, regt die KOBV-Zentrale andere Bibliotheken und Verbünde dazu an, analoge Open-Linking-Dienste einzurichten. Auf diese Weise wird die Handhabung von Open-Linking selbstverständlicher.

Description: Dieser Artikel berichtet über eine erfolgreiche Schüleraktivität, die seit Jahren am Zuse-Institut Berlin (ZIB) bei Besuchen von Schülergruppen erprobt und verfeinert worden ist. Das hier zusammengestellte Material ist gedacht als Basis für eine Unterrichtseinheit in Leistungskursen Mathematik an Gymnasien. Inhaltlich wird von einem zwar für Schüler (wie auch Lehrer) neuen, aber leicht fasslichen Gegenstand ausgegangen: der Drei-Term-Rekursion für Besselfunktionen. Die Struktur wird erklärt und in ein kleines Programm umgesetzt. Dazu teilen sich die Schüler selbstorganisierend in Gruppen ein, die mit unterschiedlichen Taschenrechnern "um die Wette" rechnen. Die Schüler und Schülerinnen erfahren unmittelbar die katastrophale Wirkung von an sich kleinen'' Rundungsfehlern, sie landen -- ebenso wie der Supercomputer des ZIB -- im Bessel'schen Irrgarten''. Die auftretenden Phänomene werden mathematisch elementar erklärt, wobei lediglich auf das Konzept der linearen Unabhängigkeit zurückgegriffen wird. Das dabei gewonnene vertiefte Verständnis fließt ein in die Konstruktion eines klassischen Algorithmus sowie eines wesentlich verbesserten Horner-artigen Algorithmus.

Description: In this paper we study capacitated network design problems, differentiating directed, bidirected and undirected link capacity models. We complement existing polyhedral results for the three variants by new classes of facet-defining valid inequalities and unified lifting results. For this, we study the restriction of the problems to a cut of the network. First, we show that facets of the resulting cutset polyhedra translate into facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Second, we provide an analysis of the facial structure of cutset polyhedra, elaborating the differences caused by the three different types of capacity constraints. We present flow-cutset inequalities for all three models and show under which conditions these are facet-defining. We also state a new class of facets for the bidirected and undirected case and it is shown how to handle multiple capacity modules by Mixed Integer Rounding (MIR).

Description: In this paper we study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that only depends on the demands previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is 4K2 (1+K)2 -competitive, where K is the number of commodities. For the single-source single-destination case, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.

Description: In this paper, we empirically investigate the NP-hard problem of finding sparse solutions to linear equation systems, i.e., solutions with as few nonzeros as possible. This problem has received considerable interest in the sparse approximation and signal processing literature, recently. We use a branch-and-cut approach via the maximum feasible subsystem problem to compute optimal solutions for small instances and investigate the uniqueness of the optimal solutions. We furthermore discuss five (modifications of) heuristics for this problem that appear in different parts of the literature. For small instances, the exact optimal solutions allow us to evaluate the quality of the heuristics, while for larger instances we compare their relative performance. One outcome is that the basis pursuit heuristic performs worse, compared to the other methods. Among the best heuristics are a method due to Mangasarian and a bilinear approach.

Description: The performance evaluation of W-CDMA networks is intricate as cells are strongly coupled through interference. Pole equations have been developed as a simple tool to analyze cell capacity. Numerous scientific contributions have been made on their basis. In the established forms, the pole equations rely on strong assumptions such as homogeneous traffic, uniform users, and constant downlink orthogonality factor. These assumptions are not met in realistic scenarios. Hence, the pole equations are typically used during initial network dimensioning only. Actual network (fine-) planning requires a more faithful analysis of each individual cell's capacity. Complex analytical analysis or Monte-Carlo simulations are used for this purposes. In this paper, we generalize the pole equations to include inhomogeneous data. We show how the equations can be parametrized in a cell-specific way provided the transmit powers are known. This allows to carry over prior results to realistic settings. This is illustrated with an example: Based on the pole equation, we investigate the accuracy of average snapshot'' approximations for downlink transmit powers used in state-of-the-art network optimization schemes. We confirm that the analytical insights apply to practice-relevant settings on the basis of results from detailed Monte-Carlo simulation on realistic datasets.

Description: This paper deals with directed, bidirected, and undirected capacitated network design problems. Using mixed integer rounding (MIR), we generalize flow-cutset inequalities to these three link types and to an arbitrary modular link capacity structure, and propose a generic separation algorithm. In an extensive computational study on 54 instances from the Survivable Network Design Library (SNDlib), we show that the performance of cplex can significantly be enhanced by this class of cutting planes. The computations reveal the particular importance of the subclass of cutset-inequalities.

Description: Wigner transformation provides a one-to-one correspondence between functions on position space (wave functions) and functions on phase space (Wigner functions). Weighted integrals of Wigner functions yield quadratic quantities of wave functions like position and momentum densities or expectation values. For molecular quantum systems, suitably modified classical transport of Wigner functions provides an asymptotic approximation of the dynamics in the high energy regime. The article addresses the computation of Wigner functions by Monte Carlo quadrature. An ad aption of the Metropolis algorithm for the approximation of signed measures with disconnected support is systematically tested in combination with a surface hopping algorithm for non-adiabatic quantum dynamics. The numerical experiments give expectation values and level populations with an error of two to three percent, which agrees with the theoretically expected accuracy.

Description: We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints into account, including node hardware, several bitrates, and survivability against single physical node or link failures. This model is solved using a branch-and-cut approach with problem-specific preprocessing and cutting planes based on either of the two layers. On several realistic two-layer planning scenarios, we show that these cutting planes are still useful in the multi-layer context, helping to increase the dual bound and to reduce the optimality gaps.

Description: In \emph{classical optimization} it is assumed that full information about the problem to be solved is given. This, in particular, includes that all data are at hand. The real world may not be so nice'' to optimizers. Some problem constraints may not be known, the data may be corrupted, or some data may not be available at the moments when decisions have to be made. The last issue is the subject of \emph{online optimization} which will be addressed here. We explain some theory that has been developed to cope with such situations and provide examples from practice where unavailable information is not the result of bad data handling but an inevitable phenomenon.

Description: Die Arbeit präsentiert ein Transaktionsverfahren für strukturierte Overlay-Netzwerke, das an die Erfordernisse verteilter Informationssysteme mit relationalem Datenmodell angepasst ist. Insbesondere wird der Einsatz von Transaktionen für verteilte Wikis betrachtet, die moderne Funktionalitäten, wie Metadaten und zusätzliche Indexe für die Navigation, unterstützen. Konsistenz und Dauerhaftigkeit der gespeicherten Daten erfordert die Behandlung von Knotenausfällen. Die Arbeit schlägt dafür das Zellenmodell vor: Das Overlay wird aus replizierten Zustandsmaschinen gebildet, um Verfügbarkeit zu gewährleisten. Das Transaktionsverfahren baut darauf auf und verwendet Two-Phase-Commit mit Fehlererkennung und Widerherstellung von ausgefallenen Transaktionsmanagern. Anwendungen wird eine Auswahl an pessimistischen und hybrid-optimistischen Nebenläufigkeitskontrollverfahren geboten, die die Minimierung von Latenzeffekten und die schnelle Ausführung von Nur-Lese-Transaktionen ermöglichen. Für die Beispielanwendung Wiki wird der erforderliche Pseudocode angegeben und die verschiedenen Nebenläufigkeitskontrollverfahren hinsichtlich ihrer Nachrichtenkomplexität verglichen.

Description: The report presents a transaction processing scheme for structured overlay networks and uses it to develop a distributed Wiki application based on a relational data model. The Wiki supports rich metadata and additional indexes for navigation purposes. Ensuring consistency and durability requires handling of node failures. Such failures are masked by providing high availability of nodes. This in turn is achieved by constructing the overlay from replicated state machines (cell model). Atomicity is realized using two phase commit with additional support for failure detection and restoration of the transaction manager. The developed transaction processing scheme provides the application with a mixture of pessimistic, hybrid optimistic and multiversioning concurrency control techniques to minimize the impact of replication on latency and optimize for read operations. The pseudocode of the relevant Wiki functions is presented and the different concurrency control techniques are evaluated in terms of message complexit

Description: Berlin als Stadtstaat ist Kommune und Land der Bundesrepublik zugleich und Standort vieler renommier-ter Wissenschafts- und Kultureinrichtungen. In enger Zusammenarbeit der Wissenschaftseinrichtungen mit dem IT-Dienstleistungszentrum Berlin (ITDZ, ehemals Landesbetrieb für Informationstechnik), der für die Behörden Berlins zuständigen Einrichtung, wurde seit 1993 ein landeseigenes Glasfasernetz mit einer derzeitigen Länge von 856 km Glasfaserkabel (je Kabel bis zu 144 Einzelfasern) zur gemeinsamen Nutzung von Wissenschaft und Verwaltung errichtet und weiter ausgebaut. 1994 erfolgte der offizielle Start des Berliner Wissenschaftsnetzes BRAIN (Berlin Research Area Information Network), als durch einen Beschluss des Senats von Berlin die Nutzung des landeseigenen Glasfasernetzes durch die Wissen-schaftseinrichtungen festgeschrieben wurde. Bereits 1995 wurden durch die Wissenschaftseinrichtungen auf diesem Glasfasernetz die ersten sieben Anschlüsse in ATM-Technik (Classical BRAIN-ATM) in Betrieb genommen, 1999 wurden anschließend auch erste Strecken in Ethernet-Technik (Classical BRAIN-GE) betrieben. Diese heterogenen Netze mit unterschiedlichen Netzgeräten wurden dezentral von den Netzadministratoren der beteiligten Einrichtungen nach globalen Absprachen betreut. Die dezentrale Administration erschwerte das Management und die Erweiterungen der Gesamtnetze. Basierend auf den vorliegenden Erfahrungen vereinbarten die Berliner Wissenschaftseinrichtungen, ein technisch neues Verbundnetz in Gigabit-Ethernet-Technik mit einheitlichen Geräten und einem zentralen Netzwerkmana-gement aufzubauen und zu betreiben. Seit November 2003 betreibt BRAIN auf dem landeseignen Glasfasernetz ein auf MPLS-Technik basie-rendes Gigabit-Ethernet-Netz, das „BRAIN-Verbundnetz“, mit den Diensten LAN-to-LAN-Kopplung der Einrichtungen, regionaler IP-Verkehr, Übergang zum Verwaltungsnetz und WiN-Backup. Das BRAIN-Verbundnetz löste die dezentral betreuten Vorläufernetze komplett ab. Von den derzeit 27 BRAIN-Teilnehmern nutzen 24 Einrichtungen an 53 in der Stadt verteilten Standorten die Dienste des BRAIN-Verbundnetzes, 18 Standorte sind mit 1000 Mbit/s und 35 Standorte mit 100 Mbit/s angeschlossen. Für verteilte Standorte einer Einrichtung besteht zudem die Möglichkeit, diese über dedizierte Fasern oder Bandbreiten miteinander zu vernetzen. Seit dem 2. Quartal 2007 wird im Rahmen eines Pilotprojekts der Nutzen eines zentral gemanagten Fibre Channel-Netzwerks "BRAIN-SAN" ermittelt, um Möglichkeiten einer verteilten Datenhaltung der Berliner Hochschulen und wissenschaftlichen Einrichtungen zu schaf-fen. Zusätzlich zu den vorgenannten Diensten nutzt der DFN-Verein die BRAIN-Struktur für die Verbindun-gen der X-WiN-Kernnetzknoten in Berlin und Potsdam untereinander und für Zugangsleitungen zu den Anwendern. Mit Stand 2007 nutzt das Berliner Wissenschaftsnetz BRAIN vom landeigenen Glasfasernetz 2100 km Einzelfasern und verbindet insgesamt 43 Einrichtungen (BRAIN-Teilnehmer und DFN-Anwender) aus Wissenschaft, Bildung und Kultur mit 129 Standorten. Der Betrieb von BRAIN wird im wesentlichen durch seine Nutzer finanziert. Das Land Berlin trägt aller-dings pauschal die überwiegenden Kosten für die Wartung des Glasfasernetzes, soweit es vom ITDZ be-reit gestellt wird. Zentrales Planungs- und Steuerungsorgan für BRAIN ist die von der Senatsverwaltung für Bildung, Wis-senschaft und Forschung eingerichtete BRAIN-Planungsgruppe. Sie besteht aus Mitarbeitern der Rechen-zentren der drei Berliner Universitäten und des ZIB. Nach außen wird BRAIN in rechtlicher und wirtschaftlicher Hinsicht treuhänderisch vom ZIB vertreten, die BRAIN-Geschäftsstelle befindet sich ebenfalls im ZIB.

Description: Berlin as a city state is both local authority and federal state of the Federal Republic, as well as a location of many renowned institutions of research and culture. In close cooperation of the institutions of research with the IT service centre Berlin (ITDZ, the former Landesbetrieb für Informationstechnik) - which is the appropriate facility for the authorities of Berlin - a glass fibre network of a total extension of 856 kilome-tres of fibre optics (144 fibres each cable optic) for the common use of research and administration has been established and advanced since 1993. In 1994, when a resolution of the Senate of Berlin laid down the use of the appropriate fibre networks by the research facilities, this was the official beginning of the Berlin Research Area Information Network (BRAIN). The first seven interfaces in this fibre network in ATM technology (Classical BRAIN-ATM) were already established by the research facilities in 1995. In 1999, first systems run in Ethernet technology (Classical BRAIN-GE). These heterogeneous networks with different interfaces have been supported locally by the network administrators of the research facili-ties following global agreements. Management and advancement of the overall networks were encum-bered by these local administrations. Based on the existing experience, Berlin's research facilities agreed on the building and advancement of a technically new integrated network in gigabit Ethernet technology with standardised facilities and a centrally managed network. Since November 2003 the Berlin Research Area Information Network established a Gigabit Ethernet - called “BRAIN Integrated Network” - based on MPLS technology, including LAN to LAN linking of the facilities, local IP traffic, interface to the administration's network and WIN back-up. This BRAIN Inte-grated Network has completely replaced the locally administered predecessor networks. 24 of 27 BRAIN participants use the services of the BRAIN Integrated Network on 53 locations spread all over the city. 18 locations are connected with 1000 Mbit/s and 35 locations with 100 Mbit/s. Moreover, spread locations of a single facility have the possibililty to communicate by dedicated fibres or bandwidths. From the 2nd quarter 2007 within the scope of a pilot scheme, the advantage of a centrally administered fibre channel network "BRAIN-SAN" will be determined in order to accomplish possibilities of a spread data manage-ment of Berlin's universities and research facilities. In addition to the aforementioned services the DFN association makes use of BRAIN's structure for the connection of the X-WiN-core network nodes in Berlin and Potsdam und for access pathways to the us-ers. As from 2007, Berlin's research network BRAIN uses 2100 kilometres of single fibres from the country's fibre glass network and connects a total of 43 facilities (BRAIN participants and DFN users) from re-search, education and culture with 129 locations. The operations of BRAIN are funded basically by its users. However, the country of Berlin bears most of the costs for the maintenance of the glass fibre network, as far as it is provided by ITDZ. Central planning and steering body for BRAIN is the BRAIN planning group, which has been arranged by the administration of the Senatsverwaltung für Bildung, Wissenschaft und Forschung. It consists of staff from the computing centres of Berlin's three universities and of ZIB. BRAIN is represented legally and economically on a trust basis by the ZIB, where the BRAIN office is located also.

Description: Die Intention ist der kooperative Aufbau einer Infrastruktur durch die Bibliotheksverbünde, um den Nutzern Volltext-Angebote dauerhaft und komfortabel zur Verfügung zu stellen: Zeitschriftenartikel und elektronische Dokumente werden mittels Suchmaschinentechnologie indexiert und unter Berücksichtigung von Zugriffsrechten zugänglich gemacht. Realisiert ist dies bereits im KOBV-Volltextserver, der seit Ende 2005 im Routinebetrieb läuft. Vorstellbar ist ein überregionales Netz von Volltextservern der Verbünde, die mittels Suchmaschinentechnologie indiziert und nahtlos in das regionale und lokale Literaturangebot integriert werden. Bei den lizenzierten Materialien sind insbesondere auch die Rechte der Verlage zu wahren und entsprechende Rechtemanagement-Verfahren einzusetzen. Es gilt, transparente Verfahren zu konzipieren und umzusetzen, um für die Verlage die notwendige Vertrauensbasis zu schaffen und gleichzeitig den Einrichtungen ihren berechtigten Zugriff auf die Volltexte zu sichern. Der vorliegende Text ist die schriftliche Fassung eines Vortrages auf dem 3. Leipziger Kongress für Information und Bibliothek "Information und Ethik", der vom 19.-22. März 2007 im Congress Center Leipzig stattfand.

Description: Zur Unterstützung der Bibliotheken bei ihren Open-Access-Aktivitäten betreibt die KOBV-Zentrale seit Anfang 2005 den Service "Opus- und Archivierungsdienste". Die KOBV-Zentrale agiert als Application Service Provider (ASP) für sämtliche technischen Komponenten des Publikationsprozesses, indem sie die gesamte technische Infrastruktur bereitstellt und betreibt – angefangen bei den lokalen Publikationsservern bis hin zu lokalen Repositories zur Archivierung der elektronischen Dokumente. Der vorliegende Text ist die schriftliche Fassung eines gleichnamigen Vortrages auf der 31. ASpB-Tagung "Kooperation versus Eigenprofil?" der Arbeitsgemeinschaft der Spezialbibliotheken, die vom 25.-28. September 2007 in der Technischen Universität Berlin stattfand.

Description: A new approach to derive transparent boundary conditions (TBCs) for wave, Schrödinger, heat and drift-diffusion equations is presented. It relies on the pole condition and distinguishes between physical reasonable and unreasonable solutions by the location of the singularities of the spatial Laplace transform of the exterior solution. To obtain a numerical algorithm, a Möbius transform is applied to map the Laplace transform onto the unit disc. In the transformed coordinate the solution is expanded into a power series. Finally, equations for the coefficients of the power series are derived. These are coupled to the equation in the interior, and yield transparent boundary conditions. Numerical results are presented in the last section, showing that the error introduced by the new approximate TBCs decays exponentially in the number of coefficients.

Description: We present a unified approach for consistent remeshing of arbitrary non-manifold triangle meshes with additional user-defined feature lines, which together form a feature skeleton. Our method is based on local operations only and produces meshes of high regularity and triangle quality while preserving the geometry as well as topology of the feature skeleton and the input mesh.

Description: For medical diagnosis, visualization, and model-based therapy planning three-dimensional geometric reconstructions of individual anatomical structures are often indispensable. Computer-assisted, model-based planning procedures typically cover specific modifications of “virtual anatomy” as well as numeric simulations of associated phenomena, like e.g. mechanical loads, fluid dynamics, or diffusion processes, in order to evaluate a potential therapeutic outcome. Since internal anatomical structures cannot be measured optically or mechanically in vivo, three-dimensional reconstruction of tomographic image data remains the method of choice. In this work the process chain of individual anatomy reconstruction is described which consists of segmentation of medical image data, geometrical reconstruction of all relevant tissue interfaces, up to the generation of geometric approximations (boundary surfaces and volumetric meshes) of three-dimensional anatomy being suited for finite element analysis. All results presented herein are generated with amira ® – a highly interactive software system for 3D data analysis, visualization and geometry reconstruction.

Description: This work introduces novel internal and external memory algorithms for computing voxel skeletons of massive voxel objects with complex network-like architecture and for converting these voxel skeletons to piecewise linear geometry, that is triangle meshes and piecewise straight lines. The presented techniques help to tackle the challenge of visualizing and analyzing 3d images of increasing size and complexity, which are becoming more and more important in, for example, biological and medical research. Section 2.3.1 contributes to the theoretical foundations of thinning algorithms with a discussion of homotopic thinning in the grid cell model. The grid cell model explicitly represents a cell complex built of faces, edges, and vertices shared between voxels. A characterization of pairs of cells to be deleted is much simpler than characterizations of simple voxels were before. The grid cell model resolves topologically unclear voxel configurations at junctions and locked voxel configurations causing, for example, interior voxels in sets of non-simple voxels. A general conclusion is that the grid cell model is superior to indecomposable voxels for algorithms that need detailed control of topology. Section 2.3.2 introduces a noise-insensitive measure based on the geodesic distance along the boundary to compute two-dimensional skeletons. The measure is able to retain thin object structures if they are geometrically important while ignoring noise on the object's boundary. This combination of properties is not known of other measures. The measure is also used to guide erosion in a thinning process from the boundary towards lines centered within plate-like structures. Geodesic distance based quantities seem to be well suited to robustly identify one- and two-dimensional skeletons. Chapter 6 applies the method to visualization of bone micro-architecture. Chapter 3 describes a novel geometry generation scheme for representing voxel skeletons, which retracts voxel skeletons to piecewise linear geometry per dual cube. The generated triangle meshes and graphs provide a link to geometry processing and efficient rendering of voxel skeletons. The scheme creates non-closed surfaces with boundaries, which contain fewer triangles than a representation of voxel skeletons using closed surfaces like small cubes or iso-surfaces. A conclusion is that thinking specifically about voxel skeleton configurations instead of generic voxel configurations helps to deal with the topological implications. The geometry generation is one foundation of the applications presented in Chapter 6. Chapter 5 presents a novel external memory algorithm for distance ordered homotopic thinning. The presented method extends known algorithms for computing chamfer distance transformations and thinning to execute I/O-efficiently when input is larger than the available main memory. The applied block-wise decomposition schemes are quite simple. Yet it was necessary to carefully analyze effects of block boundaries to devise globally correct external memory variants of known algorithms. In general, doing so is superior to naive block-wise processing ignoring boundary effects. Chapter 6 applies the algorithms in a novel method based on confocal microscopy for quantitative study of micro-vascular networks in the field of microcirculation.

Description: Die vorliegende Arbeit führt I/O-effiziente Algorithmen und Standard-Algorithmen zur Berechnung von Voxel-Skeletten aus großen Voxel-Objekten mit komplexer, netzwerkartiger Struktur und zur Umwandlung solcher Voxel-Skelette in stückweise-lineare Geometrie ein. Die vorgestellten Techniken werden zur Visualisierung und Analyse komplexer drei-dimensionaler Bilddaten, beispielsweise aus Biologie und Medizin, eingesetzt. Abschnitt 2.3.1 leistet mit der Diskussion von topologischem Thinning im Grid-Cell-Modell einen Beitrag zu den theoretischen Grundlagen von Thinning-Algorithmen. Im Grid-Cell-Modell wird ein Voxel-Objekt als Zellkomplex dargestellt, der aus den Ecken, Kanten, Flächen und den eingeschlossenen Volumina der Voxel gebildet wird. Topologisch unklare Situationen an Verzweigungen und blockierte Voxel-Kombinationen werden aufgelöst. Die Charakterisierung von Zellpaaren, die im Thinning-Prozess entfernt werden dürfen, ist einfacher als bekannte Charakterisierungen von so genannten "Simple Voxels". Eine wesentliche Schlussfolgerung ist, dass das Grid-Cell-Modell atomaren Voxeln überlegen ist, wenn Algorithmen detaillierte Kontrolle über Topologie benötigen. Abschnitt 2.3.2 präsentiert ein rauschunempfindliches Maß, das den geodätischen Abstand entlang der Oberfläche verwendet, um zweidimensionale Skelette zu berechnen, welche dünne, aber geometrisch bedeutsame, Strukturen des Objekts rauschunempfindlich abbilden. Das Maß wird im weiteren mit Thinning kombiniert, um die Erosion von Voxeln auf Linien zuzusteuern, die zentriert in plattenförmigen Strukturen liegen. Maße, die auf dem geodätischen Abstand aufbauen, scheinen sehr geeignet zu sein, um ein- und zwei-dimensionale Skelette bei vorhandenem Rauschen zu identifizieren. Eine theoretische Begründung für diese Beobachtung steht noch aus. In Abschnitt 6 werden die diskutierten Methoden zur Visualisierung von Knochenfeinstruktur eingesetzt. Abschnitt 3 beschreibt eine Methode, um Voxel-Skelette durch kontrollierte Retraktion in eine stückweise-lineare geometrische Darstellung umzuwandeln, die als Eingabe für Geometrieverarbeitung und effizientes Rendering von Voxel-Skeletten dient. Es zeigt sich, dass eine detaillierte Betrachtung der topologischen Eigenschaften eines Voxel-Skeletts einer Betrachtung von allgemeinen Voxel-Konfigurationen für die Umwandlung zu einer geometrischen Darstellung überlegen ist. Die diskutierte Methode bildet die Grundlage für die Anwendungen, die in Abschnitt 6 diskutiert werden. Abschnitt 5 führt einen I/O-effizienten Algorithmus für Thinning ein. Die vorgestellte Methode erweitert bekannte Algorithmen zur Berechung von Chamfer-Distanztransformationen und Thinning so, dass diese effizient ausführbar sind, wenn die Eingabedaten den verfügbaren Hauptspeicher übersteigen. Der Einfluss der Blockgrenzen auf die Algorithmen wurde analysiert, um global korrekte Ergebnisse sicherzustellen. Eine detaillierte Analyse ist einer naiven Zerlegung, die die Einflüsse von Blockgrenzen vernachlässigt, überlegen. In Abschnitt 6 wird, aufbauend auf den I/O-effizienten Algorithmen, ein Verfahren zur quantitativen Analyse von Mikrogefäßnetzwerken diskutiert.

Description: One crucial step in virtual drug design is the identification of new lead structures with respect to a pharmacological target molecule. The search for new lead structures is often done with the help of a pharmacophore, which carries the essential structural as well as physico-chemical properties that a molecule needs to have in order to bind to the target molecule. In the absence of the target molecule, such a pharmacophore can be established by comparison of a set of active compounds. In order to identify their common features,a multiple alignment of all or most of the active compounds is necessary. Moreover, since the “outer shape” of the molecules plays a major role in the interaction between drug and target, an alignment algorithm aiming at the identification of common binding properties needs to consider the molecule’s “outer shape”, which can be approximated by the solvent excluded surface. In this thesis, we present a new approach to molecular surface alignment based on a discrete representation of shape as well as physico-chemical properties by points distributed on the solvent excluded surface. We propose a new method to distribute points regularly on a surface w.r.t. a smoothly varying point density given on that surface. Since the point distribution algorithm is not restricted to molecular surfaces, it might also be of interest for other applications. For the computation of pairwise surface alignments, we extend an existing point matching scheme to surface points, and we develop an efficient data structure speeding up the computation by a factor of three. Moreover, we present an approach to compute multiple alignments from pairwise alignments, which is able to handle a large number of surface points. All algorithms are evaluated on two sets of molecules: eight thermolysin inhibitors and seven HIV-1 protease inhibitors. Finally, we compare the results obtained from surface alignment with the results obtained by applying an atom alignment approach.

Description: Die Identifizierung neuer Leitstrukturen (lead structures) zur Entwicklung optimierter Wirkstoffe ist ein äußerst wichtiger Schritt in der virtuellen Wirkstoffentwicklung (virtual drug design). Die Suche nach neuen Leitstrukturen wird oft mit Hilfe eines Pharmakophor-Modells durchgeführt, welches die wichtigsten strukturellen wie auch physiko-chemischen Eigenschaften eines bindenden Moleküls in sich vereint. Ist das Zielmolekül (target) nicht bekannt, kann das Pharmakophor-Modell mit Hilfe des Vergleiches aktiver Moleküle erstellt werden. Hier ist insbesondere die gleichzeitige Überlagerung (multiple alignment) aller oder nahezu aller Moleküle notwendig. Da bei der Interaktion zweier Moleküle die "äußere Form" der Moleküle eine besondere Rolle spielt, sollte diese von jedem Überlagerungsalgorithmus, der sich mit der Identifizierung von Bindungseigenschaften befasst, berücksichtigt werden. Dabei kann die "äußere Form" durch eine bestimmte Art von molekularer Oberfläche approximiert werden, die man als solvent excluded surface bezeichnet. In dieser Arbeit stellen wir einen neuen Ansatz zur Überlagerung molekularer Oberflächen dar, der auf einer diskreten Repräsentation sowohl der Form als auch der molekularen Eigenschaften mittels Punkten beruht. Um die Punkte auf der molekularen Oberfläche möglichst regulär entsprechend einer gegebenen Punktdichte zu verteilen, entwickeln wir eine neue Methode. Diese Methode ist nicht auf Moleküloberflächen beschränkt und könnte daher auch für andere Anwendungen von Interesse sein. Basierend auf einem bekannten Point-Matching Verfahren entwickeln wir einen Point-Matching Algorithmus für Oberflächenpunkte. Dazu erarbeiten wir u.a. eine effiziente Datenstruktur, die den Algorithmus um einen Faktor von drei beschleunigt. Darüberhinaus stellen wir einen Ansatz vor, der Mehrfachüberlagerungen (multiple alignments) aus paarweisen Überlagerungen berechnet. Die Herausforderung besteht hierbei vor allem in der großen Anzahl von Punkten, die berücksichtigt werden muss. Die vorgestellten Algorithmen werden an zwei Gruppen von Molekülen evaluiert, wobei die erste Gruppe aus acht Thermolysin Inhibitoren besteht, die zweite aus sieben HIV-1 Protease Inhibitoren. Darüberhinaus vergleichen wir die Ergebnisse der Oberflächenüberlagerung mit denen einer Atommittelpunktüberlagerung.

Description: We propose a variant of the control reduced interior point method for the solution of state constrained problems. We show convergence of the corresponding interior point pathfollowing algorithm in function space. Morever, we provide error bounds for the iterates.

Description: This paper aims at presenting the complex coupled network of the human menstrual cycle to the interested community. Beyond the presently popular smaller models, where important network components arise only as extremely simplified source terms, we add: the GnRH pulse generator in the hypothalamus, receptor binding, and the biosynthesis in the ovaries. Simulation and parameter identification are left to a forthcoming paper.

Description: This work explores two applications of a classical result on the continuity of Nemyckii operators to optimal control with PDEs. First, we present an alternative approach to the analysis of Newton's method for function space problems involving semi-smooth Nemyckii operators. A concise proof for superlinear convergence is presented, and sharpened bounds on the rate of convergence are derived. Second, we derive second order sufficient conditions for problems, where the underlying PDE has poor regularity properties. We point out that the analytical structure in both topics is essentially the same.

Description: In this paper, we study the efficiency of Nash equilibria for a sequence of nonatomic routing games. We assume that the games are played consecutively in time in an online fashion: by the time of playing game $i$, future games $i+1,\dots,n$ are not known, and, once players of game $i$ are in equilibrium, their corresponding strategies and costs remain fixed. Given a sequence of games, the cost for the sequence of Nash equilibria is defined as the sum of the cost of each game. We analyze the efficiency of a sequence of Nash equilibria in terms of competitive analysis arising in the online optimization field. Our main result states that the online algorithm $\sl {SeqNash}$ consisting of the sequence of Nash equilibria is $\frac{4n}{2+n}$-competitive for affine linear latency functions. For $n=1$, this result contains the bound on the price of anarchy of $\frac{4}{3}$ for affine linear latency functions of Roughgarden and Tardos [2002] as a special case. Furthermore, we analyze a problem variant with a modified cost function that reflects the total congestion cost, when all games have been played. In this case, we prove an upper bound of $\frac{4n}{2+n}$ on the competitive ratio of $\sl {SeqNash}$. We further prove a lower bound of $\frac{3n-2}{n}$ of $\sl {SeqNash}$ showing that for $n=2$ our upper bound is tight.

Description: To approximate convolutions which occur in evolution equations with memory terms, a variable-stepsize algorithm is presented for which advancing $N$ steps requires only $O(N\log N)$ operations and $O(\log N)$ active memory, in place of $O(N^2)$ operations and $O(N)$ memory for a direct implementation. A basic feature of the fast algorithm is the reduction, via contour integral representations, to differential equations which are solved numerically with adaptive step sizes. Rather than the kernel itself, its Laplace transform is used in the algorithm. The algorithm is illustrated on three examples: a blow-up example originating from a Schrödinger equation with concentrated nonlinearity, chemical reactions with inhibited diffusion, and viscoelasticity with a fractional order constitutive law.

Description: This paper deals with MIP-based primal heuristics to be used within a branch-and-cut approach for solving multi-layer telecommunication network design problems. Based on a mixed-integer programming formulation for two network layers, we present three heuristics for solving important subproblems, two of which solve a sub-MIP. On multi-layer planning instances with many parallel logical links, we show the effectiveness of our heuristics in finding good solutions early in the branch-and-cut search tree.

Description: The dynamics of ventricular fibrillation caused by irregular excitation is simulated in the frame of the monodomain model with an action potential model due to Aliev-Panfilov for a human 3D geometry. The numerical solution of this multiscale reaction-diffusion problem is attacked by algorithms which are fully adaptive in both space and time (code library {\sc Kardos}). The obtained results clearly demonstrate an accurate resolution of the cardiac potential during the excitation and the plateau phases (in the regular cycle) as well as after a reentrant excitation (in the irregular cycle).

Description: The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the permutation of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up the branch-and-cut tree. We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving this kind of symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the branch-and-cut tree, removes redundant parts of the tree produced by the above mentioned permutations. The method relies on certain polyhedra, called orbitopes, which have been investigated in (Kaibel and Pfetsch (2006)). However, it does not add inequalities to the model, and thus, it does not increase the difficulty of solving the linear programming relaxations. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem motivated from frequency planning in mobile telecommunication networks.

Description: In this paper, we discuss the relation of unsplittable shortest path routing (USPR) to other routing schemes and study the approximability of three USPR network planning problems. Given a digraph $D=(V,A)$ and a set $K$ of directed commodities, an USPR is a set of flow paths $\Phi_{(s,t)}$, $(s,t)\in K$, such that there exists a metric $\lambda=(\lambda_a)\in \mathbb{Z}^A_+$ with respect to which each $\Phi_{(s,t)}$ is the unique shortest $(s,t)$-path. In the \textsc{Min-Con-USPR} problem, we seek for an USPR that minimizes the maximum congestion over all arcs. We show that this problem is hard to approximate within a factor of $\mathcal{O}(|V|^{1-\epsilon})$, but easily approximable within min$(|A|,|K|)$ in general and within $\mathcal{O}(1)$ if the underlying graph is an undirected cycle or a bidirected ring. We also construct examples where the minimum congestion that can be obtained by USPR is a factor of $\Omega(|V|^2)$ larger than that achievable by unsplittable flow routing or by shortest multi-path routing, and a factor of $\Omega(|V|)$ larger than by unsplittable source-invariant routing. In the CAP-USPR problem, we seek for a minimum cost installation of integer arc capacities that admit an USPR of the given commodities. We prove that this problem is $\mathcal{NP}$-hard to approximate within $2-\epsilon$ (even in the undirected case), and we devise approximation algorithms for various special cases. The fixed charge network design problem \textsc{Cap-USPR}, where the task is to find a minimum cost subgraph of $D$ whose fixed arc capacities admit an USPR of the commodities, is shown to be $\mathcal{NPO}$-complete. All three problems are of great practical interest in the planning of telecommunication networks that are based on shortest path routing protocols. Our results indicate that they are harder than the corresponding unsplittable flow or shortest multi-path routing problems.

Description: In this paper, we investigate the connection availabilities for the new protection scheme Demand-wise Shared Protection (DSP) and describe an appropriate approach for their computation. The exemplary case study on two realistic network scenarios shows that in most cases the availabilities for DSP are comparable with that for 1+1 path protection and better than in case of shared path protection.

Description: THESEUS, the ZIB threading environment, is a parallel implementation of a protein threading based on a multi-queued branch-and-bound optimal search algorithm to find the best sequence-to-structure alignment through a library of template structures. THESEUS uses a template core model based on secondary structure definition and a scoring function based on knowledge-based potentials reflecting pairwise interactions and the chemical environment, as well as pseudo energies for homology detection, loop alignment, and secondary structure matching. The threading core is implemented in C++ as a SPMD parallization architecture using MPI for communication. The environment is designed for generic testing of different scoring functions, e.g. different secondary structure prediction terms, different scoring matrices and information derived from multiple sequence alignments. A validaton of the structure prediction results has been done on the basis of standard threading benchmark sets. THESEUS successfully participated in the 6th Critical Assessment of Techniques for Protein Structure Prediction (CASP) 2004.

Description: We consider a multi-queue multi-server system with $n$ servers (processors) and $m$ queues. At the system there arrives a stationary and ergodic stream of $m$ different types of requests with service requirements which are served according to the following $k$-limited head of the line processor sharing discipline: The first $k$ requests at the head of the $m$ queues are served in processor sharing by the $n$ processors, where each request may receive at most the capacity of one processor. By means of sample path analysis and Loynes' monotonicity method, a stationary and ergodic state process is constructed, and a necessary as well as a sufficient condition for the stability of the $m$ separate queues are given, which are tight within the class of all stationary ergodic inputs. These conditions lead to tight necessary and sufficient conditions for the whole system, also in case of permanent customers, generalizing an earlier result by the authors for the case of $n$=$k$=1.

Description: In order to compute the thermodynamic weights of the different metastable conformations of a molecule, we want to approximate the molecule's Boltzmann distribution in a reasonable time. This is an essential issue in computational drug design. The energy landscape of active biomolecules is generally very rough with a lot of high barriers and low regions. Many of the algorithms that perform such samplings (e.g. the hybrid Monte Carlo method) have difficulties with such landscapes. They are trapped in low-energy regions for a very long time and cannot overcome high barriers. Moving from one low-energy region to another is a very rare event. For these reasons, the distribution of the generated sampling points converges very slowly against the thermodynamically correct distribution of the molecule. The idea of ConfJump is to use $a~priori$ knowledge of the localization of low-energy regions to enhance the sampling with artificial jumps between these low-energy regions. The artificial jumps are combined with the hybrid Monte Carlo method. This allows the computation of some dynamical properties of the molecule. In ConfJump, the detailed balance condition is satisfied and the mathematically correct molecular distribution is sampled.

Description: "`Volkssport Sudoku"' titelt der Stern in seiner Ausgabe vom 24. Mai2006. In der Tat traut sich derzeit kaum noch eine Zeitung, ohne Sudoku zu erscheinen. Die Begeisterung am Lösen dieser Zahlenrätsel offenbart eine unvermutete Freude am algorithmischen Arbeiten. Mathematisch kann man Sudokus als lineare diophantische Gleichungssysteme mit Nichtnegativitätsbedingungen formulieren. Solche ganzzahligen linearen Programme sind die wichtigsten Modellierungswerkzeuge in zahlreichen Anwendungsgebieten wie z.B. der Optimierung von Telekommunikations- und Verkehrsnetzen. Moderne Verfahren zur Lösung dieser Optimierungsprobleme sind durch Sudokus allerdings deutlich weniger zu beeindrucken als Zeitungsleser.

Description: This article surveys mathematical models and methods used for physical PCB layout, i.e., component placement and wire routing. The main concepts are briefly described together with relevant references.

Description: We study online multicommodity minimum cost routing problems in networks, where commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining the routing weights. We discuss an online algorithm that routes each commodity by minimizing a convex cost function that depends on the demands that are previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is $4K/2+K$-competitive, where $K$ is the number of commodities. For the parallel arc case this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.

Description: Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs $G$ where the stable set polytope STAB$(G)$ coincides with the clique constraint stable set polytope QSTAB$(G)$. For all imperfect graphs STAB$(G) \subset$ QSTAB$(G)$ holds and, therefore, it is natural to measure imperfection in terms of the difference between STAB$(G)$ and QSTAB$(G)$. Several concepts have been developed in this direction, for instance the dilation ratio of STAB$(G)$ and QSTAB$(G)$ which is equivalent to the imperfection ratio imp$(G)$ of $G$. To determine imp$(G)$, both knowledge on the facets of STAB$(G)$ and the extreme points of QSTAB$(G)$ is required. The anti-blocking theory of polyhedra yields all {\em dominating} extreme points of QSTAB$(G)$, provided a complete description of the facets of STAB$(\overline G)$ is known. As this is typically not the case, we extend the result on anti-blocking polyhedra to a {\em complete} characterization of the extreme points of QSTAB$(G)$ by establishing a 1-1 correspondence to the facet-defining subgraphs of $\overline G$. We discuss several consequences, in particular, we give alternative proofs of several famous results.

Description: We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time $O^\ast(2^n)$. This algorithm is based on the old dynamic programming method introduced by Held and Karp for the {\sc Tra veling Salesman} problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. However, our experiments show that the space use d by the algorithm is an important factor to what input sizes the algorithm is effective. For this purpose, we settle the problem of computing treewidth under the restriction that the space used is only polynomial. In this direction we give a simple $O^\ast(4^n)$ al gorithm that requires {\em polynomial} space. We also show that with a more complicated algorithm, using balanced separators, {\sc Treewidth} can be computed in $O^\ast(2.9512^n)$ time and polynomial space.

Description: The dynamic behavior of molecules can often be described by Markov processes. From computational molecular simulations one can derive transition rates or transition probabilities between subsets of the discretized conformational space. On the basis of this dynamic information, the spatial subsets are combined into a small number of so-called metastable molecular conformations. This is done by clustering methods like the Robust Perron Cluster Analysis (PCCA+). Up to now it is an open question how this coarse graining in space can be transformed to a coarse graining of the Markov chain while preserving the essential dynamic information. In the following article we aim at a consistent coarse graining of transition probabilities or rates on the basis of metastable conformations such that important physical and mathematical relations are preserved. This approach is new because PCCA+ computes molecular conformations as linear combinations of the dominant eigenvectors of the transition matrix which does not hold for other clustering methods.

Description: Das deutschsprachige Bibliothekswesen verfügt mit den \glqq Regeln für den Schlagwortkatalog \grqq (RSWK) unter Verwendung der \glqq Schlagwortnormdatei \grqq (SWD) über ein Instrumentarium, welches zusammen mit einem \glqq Faceted Browsing \grqq das bisher bestehende Angebot für ein Information Retrieval optimal ergänzen kann. Die Verbindung zwischen Standardvokabular (SWD) und Kettenbildung (RSWK) einerseits und eine nach Facetten-Eigenschaften gegliederte Navigation andererseits unterstützt bestmöglich eine inhaltlich bezogene Recherche. Die Stärken und Schwächen der RSWK/SWD werden erörtert und auch Klassifikationen (DDC und RVK) als mögliche Facetten diskutiert.

Description: A lot of problems arising in Combinatorial Optimization and Operations Research can be formulated as Mixed Integer Programs (MIP). Although MIP-solving is an NP-hard optimization problem, many practically relevant instances can be solved in reasonable time. In modern MIP-solvers like the branch-cut-and-price-framework SCIP, primal heuristics play a major role in finding and improving feasible solutions at the early steps of the solution process. This helps to reduce the overall computational effort, guides the remaining search process, and proves the feasibility of the MIP model. Furthermore, a heuristic solution with a small gap to optimality often is sufficient in practice. We investigate 16 different heuristics, all of which are available in SCIP. Four of them arise from the literature of the last decade, nine are specific implementations of general heuristic ideas, three have been newly developed. We present an improved version of the feasibility pump heuristic by Fischetti et al., which in experiments produced solutions with only a third of the optimality gap compared to the original version. Furthermore, we introduce two new Large Neighborhood Search (LNS) heuristics. Crossover is an LNS improvement heuristic making use of similarities of diverse MIP solutions to generate new incumbent solutions. RENS is an LNS rounding heuristic which evaluates the space of all possible roundings of a fractional LP-solution. This heuristic makes it possible to determine whether a point can be rounded to an integer solution and which is the best possible rounding. We conclude with a computational comparison of all described heuristics. It points out that a single heuristic on its own has only a slight impact on the overall performance of SCIP, but the combination of all of them reduces the running time by a factor of two compared to a version without any heuristics.

Description: We present a finite volume method for the solution of the two-dimensional Poisson equation $ \nabla\cdot( \beta( {\mbox{\boldmath $x$}}) \nabla u({\mbox{\boldmath $x$}})) = f(\mbox{\boldmath $x$}) $ with variable, discontinuous coefficients and solution discontinuities on irregular domains. The method uses bilinear ansatz functions on Cartesian grids for the solution $u({\mbox{\boldmath $x$})$ resulting in a compact nine-point stencil. The resulting linear problem has been solved with a standard multigrid solver. Singularities associated with vanishing partial volumes of intersected grid cells or the dual bilinear ansatz itself are removed by a two-step asymptotic approach. The method achieves second order of accuracy in the $L^\infty$ and $L^2$ norm.

Description: In this article we aim at an efficient sampling of the stationary distribution of dynamical systems in the presence of metastabilities. In the past decade many sophisticated algorithms have been inven ted in this field. We do not want to simply add a further one. We address the problem that one has applied a sampling algorithm for a dynamical system many times. This leads to different samplings which more or less represent the stationary distribution partially very well, but which are still far away from ergodicity or from the global stationary distribution. We will show how these samplings can be joined together in order to get one global sampling of the stationary distribution.

Description: The concept of jump system, introduced by Buchet and Cunningham (1995), is a set of integer points with a certain exchange property. In this paper, we discuss several linear and convex optimization problems on jump systems and show that these problems can be solved in polynomial time under the assumption that a membership oracle for a jump system is available. We firstly present a polynomial-time implementation of the greedy algorithm for the minimization of a linear function. We then consider the minimization of a separable-convex function on a jump system, and propose the first polynomial-time algorithm for this problem. The algorithm is based on the domain reduction approach developed in Shioura (1998). We finally consider the concept of M-convex functions on constant-parity jump systems which has been recently proposed by Murota (2006). It is shown that the minimization of an M-convex function can be solved in polynomial time by the domain reduction approach.

Description: We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain insight into ways of breaking certain symmetries in integer programs by adding constraints, e.g., for a well-known formulation of the graph coloring problem. We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining inequalities. For the cyclic group case, the descriptions turn out to be totally unimodular, while for the symmetric group case, both the description and the proof are more involved. The associated separation problems can be solved in linear time.

Description: The standard computational methods for computing the optimal value functions of Markov Decision Problems (MDP) require the exploration of the entire state space. This is practically infeasible for applications with huge numbers of states as they arise, e.\,g., from modeling the decisions in online optimization problems by MDPs. Exploiting column generation techniques, we propose and apply an LP-based method to determine an $\varepsilon$-approximation of the optimal value function at a given state by inspecting only states in a small neighborhood. In the context of online optimization problems, we use these methods in order to evaluate the quality of concrete policies with respect to given initial states. Moreover, the tools can also be used to obtain evidence of the impact of single decisions. This way, they can be utilized in the design of policies.

Description: Wir beschäftigen uns mit dem Problem der Betriebsplanung von Laserschweißrobotern im Karosseriebau. Gegeben ist eine Menge von Schweißnähten, die innerhalb einer Fertigungszelle an einem Karosserieteil gefertigt werden müssen. Die Schweißnähte werden durch mehrere parallel betriebene Roboter bearbeitet. Die Aufgabe besteht darin, für jeden Roboter eine Reihenfolge und eine zeitliche Koordinierung seiner Bewegungen zu finden, so dass alle Schweißnähte innerhalb der Taktzeit der Fertigungszelle bearbeitet werden und so wenig Laserquellen wie möglich eingesetzt werden. Dabei müssen einige Nebenbedingungen berücksichtigt werden. Für dieses spezielle Schweißproblem haben wir eine Formulierung als gemischt-ganzzahliges lineares Programm entwickelt, welches sich für die untersuchten praktischen Fälle sehr schnell lösen lässt.

Description: Modern applications of mathematical programming must take into account a multitude of technical details, business demands, and legal requirements. Teaching the mathematical modeling of such issues and their interrelations requires real-world examples that are well beyond the toy sizes that can be tackled with the student editions of most commercial software packages. We present a new tool, which is freely available for academic use including complete source code. It consists of an algebraic modeling language and a linear mixed integer programming solver. The performance and features of the tool are in the range of current state-of-the-art commercial tools, though not in all aspects as good as the best ones. Our tool does allow the execution and analysis of large real-world instances in the classroom and can therefore enhance the teaching of problem solving issues. Teaching experience has been gathered and practical usability was tested in classes at several universities and a two week intensive block course at TU Berlin. The feedback from students and teachers has been very positive.

Description: The Bottleneck Shortest Path Problem is a basic problem in network optimization. The goal is to determine the limiting capacity of any path between two specified vertices of the network. This is equivalent to determining the unsplittable maximum flow between the two vertices. In this note we analyze the complexity of the problem, its relation to the Shortest Path Problem, and the impact of the underlying machine/computation model.

Description: We introduce a new and rich class of graph coloring manifolds via the Hom complex construction of Lov\´{a}sz. The class comprises examples of Stiefel manifolds, series of spheres and products of spheres, cubical surfaces, as well as examples of Seifert manifolds. Asymptotically, graph coloring manifolds provide examples of highly connected, highly symmetric manifolds.

Description: We give coordinate-minimal geometric realizations in general position for 17 of the 20 vertex-minimal triangulations of the orientable surface of genus 3 in the 5x5x5-cube.

Description: Biochemical interactions are determined by the 3D-structure of the involved components - thus the identification of conformations is a key for many applications in rational drug design. {\sf ConFlow} is a new multilevel approach to conformational analysis with main focus on completeness in investigation of conformational space. In contrast to known conformational analysis, the starting point for design is a space-based description of conformational areas. A tight integration of sampling and analysis leads to an identification of conformational areas simultaneously during sampling. An incremental decomposition of high-dimensional conformational space is used to guide the analysis. A new concept for the description of conformations and their path connected components based on convex hulls and {\em Hypercubes}is developed. The first results of the {\sf ConFlow} application constitute a 'proof of concept' and are further more highly encouraging. In comparison to conventional industrial applications, {\sf ConFlow} achieves higher accuracy and a specified degree of completeness with comparable effort.

Description: We consider linear inverse problems where the solution is assumed to fulfill some general homogeneous convex constraint. We develop an algorithm that amounts to a projected Landweber iteration and that provides and iterative approach to the solution of this inverse problem. For relatively moderate assumptions on the constraint we can always prove weak convergence of the iterative scheme. In certain cases, i.e. for special families of convex constraints, weak convergence implies norm convergence. The presented approach covers a wide range of problems, e.g. Besov- or BV-restoration for which we present also numerical experiments in the context of image processing.

Description: Whenever the invariant stationary density of metastable dynamical systems decomposes into almost invariant partial densities, its computation as eigenvector of some transition probability matrix is an ill-conditioned problem. In order to avoid this computational difficulty, we suggest to apply an aggregation/disaggregation method which only addresses wellconditioned sub-problems and thus results in a stable algorithm. In contrast to existing methods, the aggregation step is done via a sampling algorithm which covers only small patches of the sampling space. Finally, the theoretical analysis is illustrated by two biomolecular examples.

Description: \noindent We give a partial description of the $(s,t)-p$-path polytope of a directed graph $D$ which is the convex hull of the incidence vectors of simple directed $(s,t)$-paths in $D$ of length $p$. First, we point out how the $(s,t)-p$-path polytope is located in the family of path and cycle polyhedra. Next, we give some classes of valid inequalities which are very similar to inequalities which are valid for the $p$-cycle polytope, that is, the convex hull of the incidence vectors of simple cycles of length $p$ in $D$. We give necessary and sufficient conditions for these inequalities to be facet defining. Furthermore, we consider a class of inequalities that has been identifie d to be valid for $(s,t)$-paths of cardinality at most $p$. Finally, we transfer the results to related polytopes, in particular, the undirected counterpart of the $(s,t)-p$-path polytope.

Description: The numerical integration of dynamical contact problems often leads to instabilities at contact boundaries caused by the non-penetration condition between bodies in contact. Even a recent energy dissipative modification due to Kane et al. (1999), which discretizes the non-penetration constraints implicitly, is not able to circumvent artificial oscillations. For this reason, the present paper suggests a contact stabilization which avoids artificial oscillations at contact interfaces and is also energy dissipative. The key idea of this contact stabilization is an additional $L^2$-projection at contact interfaces, which can easily be added to any existing time integration scheme. In case of a lumped mass matrix, this projection can be carried out completely locally, thus creating only negligible additional numerical cost. For the new scheme, an elementary analysis is given, which is confirmed by numerical findings in an illustrative test example (Hertzian two body contact).

Description: We discuss different approaches for the enumeration of triangulated surfaces. In particular, we enumerate all triangulated surfaces with 9 and 10 vertices. We also show how geometric realizations of orientable surfaces with few vertices can be obtained by choosing coordinates randomly.

Description: The concept of L##-convexity is introduced by Fujishige--Murota (2000) as a discrete convexity for functions defined over the integer lattice. The main aim of this note is to understand the difference of the two algorithms for L##-convex function minimization: Murota's steepest descent algorithm (2003) and Kolmogorov's primal algorithm (2005).

Description: In this survey on combinatorial properties of triangulated manifolds we discuss various lower bounds on the number of vertices of simplicial and combinatorial manifolds. Moreover, we give a list of all known examples of vertex-minimal triangulations.

Description: This paper concerns the problem of operating a landside container exchange area that is serviced by multiple semi-automated rail mounted gantry cranes (RMGs) that are moving on a single bi-directional traveling lane. Such a facility is being built by Patrick Corporation at the Port Botany terminal in Sydney. The gantry cranes are a scarce resource and handle the bulk of container movements. Thus, they require a sophisticated analysis to achieve near optimal utilization. We present a three stage algorithm to manage the container exchange facility, including the scheduling of cranes, the control of associated short-term container stacking, and the allocation of delivery locations for trucks and other container transporters. The key components of our approach are a time scale decomposition, whereby an integer program controls decisions across a long time horizon to produce a balanced plan that is fed to a series of short time scale online subproblems, and a highly efficient space-time divisioning of short term storage areas. A computational evaluation shows that our heuristic can find effective solutions for the planning problem; on real-world data it yields a solution at most~8\% above a lower bound on optimal RMG utilization.