Bibliothek

Beschreibung: Was Komplexität ist, weiß niemand so richtig. In vielen Wissenschaftsgebieten wird der Begriff Komplexität verwendet, überall mit etwas anderer Bedeutung. Mathematik und Informatik hab en eine eigene Theorie hierzu entwickelt: die Komplexitätstheorie. Sie stellt zwar grundlegende Begriffe bereit, aber leider sind die meisten wichtigen Fragestellungen noch ungelöst. Diese kurze Einführung konzentriert sich auf einen speziellen, aber bedeutenden Aspekt der Theorie: Lösbarkeit von Problemen in deterministischer und nichtdeterministischer polynomialer Zeit. Hinter der für Uneingeweihte etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexitätstheorie. Anhand dieser Fragestellung werden einige Aspekte der Theorie erläutert und formell erklärt, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grundsätzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es für viele Probleme unseres Alltags keine effizienten Lösungsmethoden gibt?

Beschreibung: This report combines the contributions to INOC 2005 (Wessälly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within a demand. It combines advantages of dedicated and shared protection: It is more cost-efficient than dedicated protection and operationally easier than shared protection. In a previous model for DSP, the number of working and backup paths to be configured for a particular demand has been an input parameter; in the more general model for DSP investigated in this paper, this value is part of the decisions to take. To use the new DSP model algorithmically, we suggest a branch-and-cut approach which employs a column generation procedure to deal with the exponential number of routing variables. A computational study to compare the new resilience mechanism DSP with dedicated and shared path protection is performed. The results for five realistic network planning scenarios reveal that the best solutions for DSP are on average 15\% percent better than the corresponding 1+1 dedicated path protection solutions, and only 15\% percent worse than shared path protection.

Beschreibung: Die Functional Requirements for Bibliographic Records, kurz FRBR, sind eine Empfehlung der International Federation of Library Associations and Institutions (IFLA) von 1998 zur Neustrukturierung von Bibliothekskatalogen. Mit den FRBR wird ein logisches Denkmodell für bibliografische Beschreibungen vorgelegt. Die Diskussion über dieses Modell befindet sich im deutschsprachigen Raum - anders als im angloamerikanischen - noch in den Anfängen. Dem möchte dieser Aufsatz entgegen wirken, indem die Frage gestellt wird, inwieweit sich die logisch gedachten FRBR-Einheiten in den existierenden Daten wieder finden lassen. Dazu werden die Entitäten mit den dazugehörigen Attributen dem in der Bibliothekswelt Deutschlands und Österreichs üblichen MAB-Format (Maschinelles Austauschformat für Bibliotheken) gegenübergestellt und auf ihre Kompatibilität hin untersucht. Die Autoren sind Mitglieder der überregionalen {\glqq}Expertengruppe Datenformate{\grqq}, in der Formatfragen, die das Bibliothekswesen betreffen, diskutiert werden, insbesondere aber das MAB-Format gepflegt wird.

Beschreibung: In this paper we consider a simple variant of the Online Dial-a-Ride Problem from a probabilistic point of view. To this end, we look at a probabilistic version of this online Dial-a-Ride problem and introduce a probabilistic notion of the competitive ratio which states that an algorithm performs well on the vast majority of the instances. Our main result is that under the assumption of high load a certain online algorithm is probabilistically $(1+o(1))$-competitive if the underlying graph is a tree. This result can be extended to general graphs by using well-known approximation techniques at the expense of a distortion factor~$O(\log\|V\|)$.

Beschreibung: The identification of metastable conformations of molecules plays an important role in computational drug design. One main difficulty is the fact that the underlying dynamic processes take place in high dimensional spaces. Although the restriction of degrees of freedom to a few dihedral angles significantly reduces the complexity of the problem, the existing algorithms are time-consuming. They are based on the approximation of transition probabilities by an extensive sampling of states according to the Boltzmann distribution. We present a method which can identify metastable conformations without sampling the complete distribution. Our algorithm is based on local transition rates and uses only pointwise information about the potential energy surface. In order to apply the cluster algorithm PCCA+, we compute a few eigenvectors of the rate matrix by the Jacobi-Davidson method. Interpolation techniques are applied to approximate the thermodynamical weights of the clusters. The concluding example illustrates our approach for epigallocatechine, a molecule which can be described by seven dihedral angles.

Beschreibung: Zahlreiche lokale, nationale und internationale Informationsportale existieren mit zum Teil gleichen Angeboten und Dienstleistungen nebeneinander. Da der Aufbau und Betrieb von Portalen kostspielig ist, sollten die einzelnen Dienstleistungen abgestimmt und sinnvoll untereinander vernetzt werden. Für eine solch anzustrebende Kooperation unter Portalen ist es notwendig, ein jeweils eigenes Portalprofil zu definieren, um bei einer Gegenüberstellung der Profile die Abgrenzungen und Verknüpfungspunkte deutlich werden zu lassen. Die KOBV-Zentrale möchte mit der Profilbeschreibung des KOBV-Portals beginnen und so die eigenen Angebote des regionalen Portals mit denen anderer auf sinnvolle Weise verknüpfen. Für diese Positionsbestimmung werden die Dienstleistungen, die Zielgruppe, die Kriterien für die Ressourcenauswahl sowie die Abgrenzung zu anderen Portalen dargelegt.

Beschreibung: Conflict analysis for infeasible subproblems is one of the key ingredients in modern SAT solvers to cope with large real-world instances. In contrast, it is common practice for today's mixed integer programming solvers to just discard infeasible subproblems and the information they reveal. In this paper we try to remedy this situation by generalizing the SAT infeasibility analysis to mixed integer programming. We present heuristics for branch-and-cut solvers to generate valid inequalities from the current infeasible subproblem and the associated branching information. SAT techniques can then be used to strengthen the resulting cuts. We performed computational experiments which show the potential of our method: On feasible MIP instances, the number of required branching nodes was reduced by 50\% in the geometric mean. However, the total solving time increased by 15\%. on infeasible MIPs arising in the context of chip verification, the number of nodes was reduced by 90\%, thereby reducing the solving time by 60\%.

Beschreibung: We provide conditions for convergence of polyhedral surfaces and their discrete geometric properties to smooth surfaces embedded in Euclidian $3$-space. The notion of totally normal convergence is shown to be equivalent to the convergence of either one of the following: surface area, intrinsic metric, and Laplace-Beltrami operators. We further s how that totally normal convergence implies convergence results for shortest geodesics, mean curvature, and solutions to the Dirichlet problem. This work provides the justification for a discrete theory of differential geometric operators defined on polyhedral surfaces based on a variational formulation.

Beschreibung: The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported.

Beschreibung: Im Rahmen des klassischen Information Retrieval wurden verschiedene Verfahren für das Ranking sowie die Suche in einer homogenen strukturlosen Dokumentenmenge entwickelt. Die Erfolge der Suchmas chine Google haben gezeigt, dass die Suche in einer zwar inhomogenen aber zusammenhängenden Dokumentenmenge wie dem Internet unter Berücksichtigung der Dokumentenverbindungen (Links) sehr ef fektiv sein kann. Unter den von der Suchmaschine Google realisierten Konzepten ist ein Verfahren zum Ranking von Suchergebnissen (PageRank), das in diesem Artikel kurz erklärt wird. % Darüber hinaus wird auf die Konzepte eines Systems namens CiteSeer eingegangen, welches automatisch bibliographische Angaben indexiert (engl. \glqq Autonomous Citation Indexing\grqq, ACI). Letzteres erzeugt aus einer Menge von nicht-vernetzten wissenschaftlichen Dokumenten eine zusammenhängende Dokumentenmenge und ermöglicht den Einsatz von Ranking-Verfahren, die auf den von Google genutzten Verfahren basieren.

Beschreibung: A thorough convergence analysis of the Control Reduced Interior Point Method in function space is performed. This recently proposed method is a primal interior point pathfollowing scheme with the special feature, that the control variable is eliminated from the optimality system. Apart from global linear convergence we show, that this method converges locally almost quadratically, if the optimal solution satisfies a function space analogue to a non-degeneracy condition. In numerical experiments we observe, that a prototype implementation of our method behaves in compliance with our theoretical results.

Beschreibung: The use of point sets instead of meshes became more popular during the last years. We present a new method for anisotropic fairing of a point sampled surface using an anisotropic geometric mean curvature flow. The main advantage of our approach is that the evolution removes noise from a point set while it detects and enhances geometric features of the surface such as edges and corners. We derive a shape operator, principal curvature properties of a point set, and an anisotropic Laplacian of the surface. This anisotropic Laplacian reflects curvature properties which can be understood as the point set analogue of Taubin's curvature-tensor for polyhedral surfaces. We combine these discrete tools with techniques from geometric diffusion and image processing. Several applications demonstrate the efficiency and accuracy of our method.

Beschreibung: In this paper we introduce the fare planning problem for public transport which consists in designing a system of fares maximizing revenue. We propose a new simple general model for this problem. It i s based on a demand function and constraints for the different fares. The constraints define the structure of the fare system, e.g., distance dependent fares or zone fares. We discuss a simple example with a quadratic demand function and distance dependent fares. Then we introduce a more realistic discrete choice model in which passengers choose between different alternatives depending on the numb er of trips per month. We demonstrate the examples by computational experiments.

Beschreibung: Can OR methods help the public transport industry to break even? The article gives evidence that there exist significant potentials in this direction, which can be harnessed by a combination of modern mathematical methods and local planning knowledge. Many of the planning steps in public transport are classical combinatorial problems, which can be solved in unprecedented size and quality due the rapid progress in large-scale optimization. Three examples on vehicle scheduling, duty scheduling, and integrated vehicle and duty scheduling illustrate the level that has been reached and the improvements that can be achieved today. Extensions of such methods to further questions of strategic, online, and market-oriented planning are currently investigated. In this way, OR can make a significant contribution to answer the basic but extremely difficult question ``What is a good public transport network?.

Beschreibung: Laplace transforms which admit a holomorphic extension to some sector strictly containing the right half plane and exhibiting a potential behavior are considered. A spectral order, parallelizable method for their numerical inversion is proposed. The method takes into account the available information about the errors arising in the evaluations. Several numerical illustrations are provided.

Beschreibung: The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel rapid branching'' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH.

Beschreibung: The complexity of molecular kinetics can be reduced significantly by a restriction to metastable conformations which are almost invariant sets of molecular dynamical systems. With the Robust Perron Cl uster Analysis PCCA+, developed by Weber and Deuflhard, we have a tool available which can be used to identify these conformations from a transition probability matrix. This method can also be applied to the corresponding transition rate matrix which provides important information concerning transition pathways of single molecules. In the present paper, we explain the relationship between these tw o concepts and the extraction of conformation kinetics from transition rates. Moreover, we show how transition rates can be approximated and conclude with numerical examples.

Beschreibung: Die Autoren schreiben dieses Papier aus der eingeschränkten Sicht der Mathematik und der Informationstechnik. Um den speziellen Beitrag dieser Disziplinen überhaupt diskutieren zu können, sehen wir uns jedoch gezwungen, einen Rahmen abzustecken, den wir für das Jahr 2020 vorhersehen -- nach Wahrscheinlichkeit und aus unserem engeren fachlichen Blickwinkel. Vorab bitten wir schon einmal bei den medizinischen Fachleuten um Nachsicht, wenn wir uns in ihrem Revier allzu dillettantisch bewegen. Vielleicht fördert aber auch unser eingeschränkter Blickwinkel ansonsten unbedachte Aspekte zutage -- das hoffen wir zumindest.

Beschreibung: We consider nonlinear, scaling-invariant $N=1$ boson$+$fermion supersymmetric systems whose right-hand sides are homogeneous differential polynomials and satisfy some natural assumptions. We select the super-systems that admit infinitely many higher symmetries generated by recursion operators; we further restrict ourselves to the case when the dilaton dimensions of the bosonic and fermionic super-fields coincide and the weight of the time is half the weight of the spatial variable. We discover five systems that satisfy these assumptions; one system is transformed to the purely bosonic Burgers equation. We construct local, nilpotent, triangular, weakly non-local, and super-recursion operators for their symmetry algebras.

Beschreibung: We present a branch-and-cut algorithm for the NP-hard maximum feasible subsystem problem: For a given infeasible linear inequality system, determine a feasible subsystem containing as many inequalities as possible. The complementary problem, where one has to remove as few inequalities as possible in order to render the system feasible, can be formulated as a set covering problem. The rows of this formulation correspond to irreducible infeasible subsystems, which can be exponentially many. The main issue of a branch-and-cut algorithm for MaxFS is to efficiently find such infeasible subsystems. We present three heuristics for the corresponding NP-hard separation problem and discuss further cutting planes. This paper contains an extensive computational study of our implementation on a variety of instances arising in a number of applications.

Beschreibung: New evolutionary supersymmetric systems whose right-hand sides are homogeneous differential polynomials and which possess infinitely many higher symmetries are constructed. Their intrinsic geometry (symmetries, conservation laws, recursion operators, Hamiltonian structures, and exact solutions) is analyzed by using algebraic methods. A supersymmetric $N=1$ representation of the Burgers equation is obtained. An $N=2$ KdV-component system that reduces to the Burgers equation in the diagonal $N=1$ case $\theta^1=\theta^2$ is found; the $N=2$ Burgers equation admits and $N=2$ modified KdV symmetry. A one\/-\/parametric family of $N=0$ super\/-\/systems that exte nd the Burgers equation is described; we relate the systems within this family with the Burgers equation on associative algebras. A supersymmetric boson$+$fermion representation of the dispersionless Boussinesq equation is investigated. We solve this equation explicitly and construct its integrable deformation that generates two infinite sequences of the Hamiltonians. The Boussinesq equation with dispersion is embedded in a one-parametric family of two-component systems with dissipation. We finally construct a three-parametric supersymmetric system that incorporates the Boussinesq equation with dispersion and dissipation but never retracts to it for any values of the parameters.

Beschreibung: In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph $G$ is the maximum order of a bramble of $G$ minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms give often excellent lower bounds, in particular when applied to (close to) planar graphs.

Beschreibung: Seit einigen Jahren lizenzieren Bibliotheken mit erheblichem finanziellen Aufwand elektronische Zeitschriften. Anders als bei einer Papierausgabe ist der dauerhafte Zugriff auf die bezahlten Dokumente allerdings nicht garantiert: Die e-Zeitschriften liegen auf dem Verlagsserver, und der Verlag schaltet den Zugriff (meist IP-Range des Campus) auf seinem Server frei. Wird der Zugriff von Verlagsseite abgeschaltet, erlöschen sämtliche Zugriffsrechte, auch auf die in der Vergangenheit lizenzierten und bezahlten Zeitschriften. Auf die neuen Abonnementbedingungen hat das Friedrich-Althoff-Konsortium (FAK) reagiert und in seinen Vertr"agen den Erwerb der Archivdaten beim Auslaufen eines Vertrages festgeschrieben. Im Rahmen eines Projektes baut die KOBV-Zentrale einen Zeitschriftenserver auf, um den Zugriff auf die lizenzierten elektronischen Zeitschriften auch nach Ablauf der Lizenzverträge zu gewährleisten. Den Grundstock bilden die vom FAK in den Jahren 1997-2003 lizenzierten elektronischen Zeitschriften der Verlage Kluwer Academic Press, Springer und Elsevier - ein Volumen von rund 1.600 Zeitschriftentiteln mit knapp 1.400.000 Artikeln. Beim Aufbau des Zeitschriftenservers kommt der vertraglich-organisatorischen Komponente eine ebenso wichtige Rolle zu wie der technischen Realisierung. Hier hat die KOBV-Zentrale ein transparentes Verfahren konzipiert und umgesetzt, um für die Verlage die notwendige Vertrauensbasis zu schaffen und gleichzeitig den Einrichtungen ihren berechtigten Zugriff auf die Zeitschriften-Volltexte zu sichern. Die Zeitschriftenartikel werden sowohl im Rahmen des KOBV-Volltextservers, einem neuen Internet-Dienst der KOBV-Zentrale, zugänglich gemacht - volltext-indiziert mit der Suchmaschine Swish-e - als auch integriert in die Metadatensuche und den Open-Linking-Dienst des KOBV-Portals. Während die Metadatenrecherche und die Sicht auf die Abstracts für alle offen sind, ist der Zugriff auf die Artikel-Volltexte auf die an den Verträgen beteiligten Einrichtungen beschränkt. Dazu wurde ein Authentifizierungsverfahren auf der Basis von IP-Ranges eingerichtet. Der vorliegende Text ist die schriftliche Fassung eines gleichnamigen Vortrages auf der ASpB-Tagung 2005 \glqq Spezialbibliotheken zwischen Auftrag und Ressourcen{\grqq} der Arbeitsgemeinschaft der Spezialbibliotheken, die vom 06.-09. September 2005 in der Technischen Universität München stattfand.

Beschreibung: In diesem Bericht wurden Erfahrungen mit der Suchmaschine FAST im Rahmen des Projektes Verteilter Contentspeicher sowie die Suchmaschine FAST beschrieben. Das Ziel des Projektes Verteilter Contentspeicher war die Speicherung, Erschließung und das Angebot der digitalen Bestände der Journale und Dokumente der KOBV-Bibliotheken zu ermöglichen. Die Eignung der Suchmaschine FAST für das Projektvorhaben wurde systematisch und gründlich getestet, indem verschiedene Dokumentmengen mit FAST indexiert wurden.

Beschreibung: The thesis deals with the implementation and application of out-of-the-box tools in linear and mixed integer programming. It documents the lessons learned and conclusions drawn from five years of implementing, maintaining, extending, and using several computer codes to solve real-life industrial problems. By means of several examples it is demonstrated how to apply algebraic modeling languages to rapidly devise mathematical models of real-world problems. It is shown that today's MIP solvers are capable of solving the resulting mixed integer programs, leading to an approach that delivers results very quickly. Even though, problems are tackled that not long ago required the implementation of specialized branch-and-cut algorithms. In the first part of the thesis the modeling language Zimpl is introduced. Chapter 2 contains a complete description of the language. In the subsequent chapter details of the implementation are described. Both theoretical and practical considerations are discussed. Aspects of software engineering, error prevention, and detection are addressed. In the second part several real-world projects are examined that employed the methodology and the tools developed in the first part. Chapter 4 presents three projects from the telecommunication industry dealing with facility location problems. Chapter 5 characterizes questions that arise in UMTS planning. Problems, models, and solutions are discussed. Special emphasis is put on the dependency of the precision of the input data and the results. Possible reasons for unexpected and undesirable solutions are explained. Finally, the Steiner tree packing problem in graphs, a well-known hard combinatorial problem, is revisited. A formerly known, but not yet used model is applied to combine switchbox wire routing and via minimization. All instances known from the literature are solved by this approach, as are some newly generated bigger problem instances.

Beschreibung: We develop and experimentally compare policies for the control of a system of $k$ elevators with capacity one in a transport environment with $\ell$ floors, an idealized version of a pallet elevator system in a large distribution center of the Herlitz PBS AG in Falkensee. Each elevator in the idealized system has an individual waiting queue of infinite capacity. On each floor, requests arrive over time in global waiting queues of infinite capacity. The goal is to find a policy that, without any knowledge about future requests, assigns an elevator to each req uest and a schedule to each elevator so that certain expected cost functions (e.g., the average or the maximal flow times) are minimized. We show that a reoptimization policy for minimizing average sq uared waiting times can be implemented to run in real-time ($1\,s$) using dynamic column generation. Moreover, in discrete event simulations with Poisson input it outperforms other commonly used polic ies like multi-server variants of greedy and nearest neighbor.

Beschreibung: A method based on infinite parameter conservation laws is described to factor linear differential operators out of nonlinear partial differential equations (PDEs) or out of differential consequences of nonlinear PDEs. This includes a complete linearization to an equivalent linear PDE (-system) if that is possible. Infinite parameter conservation laws can be computed, for example, with the computer algebra package {\sc ConLaw}.

Beschreibung: Motivated by recent work on integrable flows of curves and 1+1 dimensional sigma models, several $O(N)$-invariant classes of hyperbolic equations $Utx=f(U,Ut,Ux)$ for an $N$-component vector $U(t,x)$ are considered. In each class we find all scaling-homogeneous equations admitting a higher symmetry of least possible scaling weight. Sigma model interpretations of these equations are presented.

Beschreibung: Quadratic Hamiltonians with a linear Lie-Poisson bracket have a number of applications in mechanics. For example, the Lie-Poisson bracket $e(3)$ includes the Euler-Poinsot model describing motion of a rigid body around a fixed point under gravity and the Kirchhoff model describes the motion of a rigid body in ideal fluid. Advances in computer algebra algorithms, in implementations and hardware, together allow the computation of Hamiltonians with higher degree first integrals providing new results in the search for integrable models. A computer algebra module enabling related computations in a 3-dimensional vector formalism is described.

Beschreibung: We give an algorithm to compute $N$ steps of a convolution quadrature approximation to a continuous temporal convolution using only $O(N\, \log N)$ multiplications and $O(\log N)$ active memory. The method does not require evaluations of the convolution kernel, but instead $O(\log N)$ evaluations of its Laplace transform, which is assumed sectorial. The algorithm can be used for the stable numerical solution with quasi-optimal complexity of linear and nonlinear integral and integro-differential equations of convolution type. In a numerical example we apply it to solve a subdiffusion equation with transparent boundary conditions.

Beschreibung: We describe a prototypical framework that further automates system management by composing complex management tasks from elementary actions, and executing composite tasks with feedback-awareness. {\sl FEEDBACKFLOW} implements a general closed control loop of \emph{planning - execution - result validation - replanning}, and generates workflows of system management actions in an adaptive manner. System-dependent behaviour of the loop is specified by declarative description of the domain (essentially descriptions of available actions), and statement of the goal. We evaluate the design of this framework on examples taken from resource construction in Utility Computing environments, and discuss the challenges we have encountered. Our implementation utilizes external components such as \emph{MBP}, a \emph{PDDL}-conform planner, and \emph{Triana}, a workflow specification and execution framework. An alternative approach involving \emph{BPEL4WS} is discussed.

Beschreibung: For a real world problem --- transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand --- we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost function that is based on minimizing the expected number of pallets that still need transportation. For speed, the convex relaxation is solved approximately by a bundle approach yielding an online schedule in 5 to 12 minutes for up to 3 warehouses and 40000 articles; in contrast, computation times of state of the art LP-solvers are prohibitive for online application. In extensive numerical experiments on a real world data stream, the approximate solutions exhibit negligible loss in quality; in long term simulations the proposed method reduces the average number of pallets needing transportation due to short term demand to less than half the number observed in the data stream.

Beschreibung: This paper introduces a new algorithm of conformational analysis based on mesh-free methods as described in [M. Weber. Mehless methods in Conformation Dynamics.(2005)]. The adaptive decomposition of the conformational space by softly limiting functions avoids trapping effects and allows adaptive refinement strategies. These properties of the algorithm makes ZIBgridfree particularly suitable for the complete exploration of high-dimensional conformational space. The adaptive control of the algorithm benefits from the tight integration of molecular simulation and conformational analysis. An emphasized part of the analysis is the Robust Perron Cluster Analysis (PCCA+) based on the work of Peter Deuflhard and Marcus Weber. PCCA+ supports an almost-characteristic cluster definition with an outstanding mapping of transition states. The outcome is expressed by the metastable sets of conformations, their thermodynamic weights and flexibility.

Beschreibung: This paper reports on the fourth version of the Mixed Integer Programming Library. Since ({\sc miplib}) is to provide a concise set of challenging problems, it became necessary to purge instances that became too easy. We present an overview of the 27 new problems and statistical data for all 60 instances.

Beschreibung: Der Artikel beschreibt ein mathematisches Optimierungssystem zur Betriebsplanung in großen Wassernetzen, das bei den Berliner Wasserbetrieben eingesetzt wird. Für das Berliner Versorgungsnetz werden Optimierungsergebnisse vorgestellt.

Beschreibung: \\ Zusammenfassung: Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) betreibt für das KOBV-Portal einen Austausch von Beschreibungen zu elektronischen Ressourcen (Metadaten), der zwisc zwischen verschiedenen Informationsportalen in der Region durchgeführt wird. Die unterschiedlichen Informationsportale verwenden verschiedene Metadaten-Schemata und Austausch-Formate für ihre Ressourcebeschreibungen. Um die Heterogenität der Metadaten zu überwinden, wurde der KOBV-Metadaten-Austausch-Parser (KMA-Parser) entwickelt. Andere Metadaten-Schemata werden auf das KOBV-Metadaten-Schema abgebildet. Der KMA-Parser führt gegebenenfalls eine Format-Transformation durch, konvertiert die Inhalte einzelner Elemente über Konkordanzen und erzeugt neue Metadaten-Elemente aus vorhandenen Feldern. Er validiert den Inhalt auf Vollständigkeit und steuert den Austausch der Metadaten zwischen den Portalen. Der Umwandlungsprozess funktioniert jedoch nicht nur in die Richtung des KOBV-Portals, sondern auch in die entgegengesetzte Richtung. Der Artikel beschreibt die einzelnen Vorgänge im KMA-Parser und schildert die Erfahrungen im Umgang mit der Heterogenität von Metadaten. Die gewonnenen Erfahrungen verweisen auf grundlegende Perspektiven in der universellen Zusammenarbeit von Informationsanbietern und -providern.The Kooperativer Bibliotheksverbund Berlin-Brandenburg (KOBV) has built a framework for a bi-directional exchange workflow of electronic resourcesÆ descriptions (metadata) between the KOBV Portal and other Information Portals in the region. The Information Portals use different exchange formats, metadata schemata and controlled vocabularies for their descriptions of resources. In order to overcome this metadata heterogeneity, an application, the KOBV Metadata Exchange Parser (KMA-Parser), has been developed. The KMA-Parser maps the local portalsÆ metadata schemata into the metadata schema of the KOBV Portal. If necessary, it transforms the exchange format, converts contents of individual elements by means roduces new metadata elements on the basis of existent elements. It checks elementsÆ contents on completeness and controls the metadata exchange between the portals. However, the transformation process takes place not only towards the KOBV Portal, but al so vice versa. The article describes the individual processes in the KMA Parser and depicts the experiences in handling the metadataÆs heterogeneity. The experiences gathered give an idea of the prospects for a universal cooperation between information suppliers and providers.

Beschreibung: \newcommand{\chordsharp}{Chord$^\##$} Data lookup is a fundamental problem in peer-to-peer systems: Given a key, find the node that stores the associated object. Chord and other P2P algorithms use distributed hash tables (DHTs) to distribute the keys and nodes evenly across a logical ring. Using an efficient routing strategy, DHTs provide a routing performance of $O (\log N)$ in networks of $N$ nodes. While the routing performance has been shown to be optimal, the uniform key distribution makes it impossible for DHTs to support range queries. For range queries, consecutive keys must be stored on lo gically neighboring nodes. In this paper, we present an enhancement of Chord that eliminates the hash function while keeping the same routing performance. The resulting algorithm, named \chordsharp{}, provides a richer function ality while maintaining the same complexity. In addition to Chord, \chordsharp{} adapts to load imbalance.

Beschreibung: This paper is concerned with the sensitivities of function space oriented interior point approximations in parameter dependent problems. For an abstract setting that covers control constrained optimal control problems, the convergence of interior point sensitivities to the sensitivities of the optimal solution is shown. Error bounds for $L_q$ norms are derived and illustrated with numerical examples.

Beschreibung: We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity.

Beschreibung: Das Travelling-Salesman-Problem (TSP) ist das am intensivsten untersuchte kombinatorische Optimierungsproblem. In diesem Abschnitt wird eine Einführung in das TSP gegeben. Es werden Problemstellungen erläutert, Anwendungen skizziert und einige Schwierigkeiten bei der korrekten Modellierung der Zielfunktion dargelegt. Es ist gar nicht so klar, was in einem konkreten Problem die wirkliche Entfernung ist. Exakte und approximative Lösungsverfahren werden an Beispielen skizziert, und es wird angedeutet, dass man, obwohl TSPs zu den theoretisch schweren Problemen zählen, in der Praxis TSPs von atemberaubender Größe lösen kann.

Beschreibung: Mit der Installation des neuen Hochleistungsrechners für die norddeutschen Länder (HLRN) steht den Wissenschaftlern ein außergewöhnlich leistungsfähiges System zur Verfügung. Durch die Verteilung der Rechenelemente auf zwei verschiedene Standorte in Berlin (ZIB) und Hannover (RRZN) entstehen jedoch auch neue Herausforderungen für den Betrieb und die effiziente Nutzung des Rechners. Inhalt dieses Projektes ist die Erforschung und Lösung der durch die Verteilung des Systems hervorgerufenen Probleme (z.B. Scheduling, Kommunikation, I/O). Es werden effiziente Lösungen zur Bereitstellung eines virtuellen, hoch-performanten und transparenten Systems entwickelt, die auf vergleichbare Installationen übertragbar sind.

Beschreibung: We study the complexity of two Inverse Shortest Paths (ISP) problems with integer arc lengths and the requirement for uniquely determined shortest paths. Given a collection of paths in a directed graph, the task is to find positive integer arc lengths such that the given paths are uniquely determined shortest paths between their respective terminals. The first problem seeks for arc lengths that minimize the length of the longest of the prescribed paths. In the second problem, the length of the longest arc is to be minimized. We show that it is $np-hard$ to approximate the minimal longest path length within a factor less than $8/7$ or the minimal longest arc length within a factor less than $9/8$. This answers the (previously) open question whether these problems are $np-hard$ or not. We also present a simple algorithm that achieves an $\mathcal{O}(|V|)$-approximation guarantee for both variants. Both ISP problems arise in the planning of telecommunication networks with shortest path routing protocols. Our results imply that it is $\mathcal{NP}$-hard to decide whether a given path set can be realized with a real shortest path routing protocol such as OSPF, IS-IS, or RIP.

Beschreibung: We perform a classification of integrable systems of mixed scalar and vector evolution equations with respect to higher symmetries. We consider polynomial systems that are homogeneous under a suitable weighting of variables. This paper deals with the KdV weighting, the Burgers (or potential KdV or modified KdV) weighting, the Ibragimov--Shabat weighting and two unfamiliar weightings. The case of other weightings will be studied in a subsequent paper. Making an ansatz for undetermined coefficients and using a computer package for solving bilinear algebraic systems, we give the complete lists of $2^{\mbox{\scriptsize nd }}$order systems with a $3^{\mbox{\scriptsize rd }}$order or a $4^{\mbox{\scriptsize th }}$order symmetry and $3^{\mbox{\scriptsize rd }}$order systems with a $5^{\mbox{\scriptsize th }}$order symmetry. For all but a few systems in the lists, we show that the system (or, at least a subsystem of it) admits either a Lax representation or a linearizing transformation. A thorough comparison with recent work of Foursov and Olver is made.

Beschreibung: The result after $N$ steps of an implicit Runge-Kutta time discretization of an inhomogeneous linear parabolic differential equation is computed, up to accuracy $\varepsilon$, by solving only $$O\Big(\log N\, \log \frac1\varepsilon \Big) $$ linear systems of equations. We derive, analyse, and numerically illustrate this fast algorithm.

Beschreibung: In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results for stars are also of interest for general meshed topologies. We show that wavelength assignment with at most two links per lightpath can be modeled as a generalized edge coloring problem. By this relation, we show that for a network with an even number of fibers at all links and at most two links per lightpath, all lightpaths can be assigned a wavelength without conversion. Moreover, we derive a lower bound on the number of lightpaths to be converted for networks with arbitrary numbers of fibers at the links. A comparison with linear programming lower bounds reveals that the bounds coincide for problems with at most two links per lightpath. For meshed topologies, the cumulative lower bound over all star subnetworks equals the best known solution value for all realistic wavelength assignment instances available, by this proving optimality.

Beschreibung: We prove that the Random-Edge simplex algorithm requires an expected number of at most $13n/sqrt(d)$ pivot steps on any simple d-polytope with n vertices. This is the first nontrivial upper bound for general polytopes. We also describe a refined analysis that potentially yields much better bounds for specific classes of polytopes. As one application, we show that for combinatorial d-cubes, the trivial upper bound of $2^d$ on the performance of Random-Edge can asymptotically be improved by any desired polynomial factor in d.

Beschreibung: In diesem Artikel werden die Optimierungsmodelle und -verfahren beschrieben, die bei der Planung des Kernnetzes und der Zugangsinfrastruktur des X-WiN verwendet wurden.

Beschreibung: Die Anwendung mathematischer Methoden und Verfahren wird immer mehr zur Voraussetzung innovativer Produkte und Dienstleistungen. Um neue Produkte und Dienstleistungen zu entwickeln, müssen die Produktions- und technologischen Prozesse mathematisch modelliert, beschrieben und optimiert werden. Diesen Umstand Rechnung tragend, hat das Bundesministerium für Bildung und Forschung (BMBF) 1993 begonnen, den Einsatz mathematischer Verfahren und Methoden in der Mathematik über ein spezielles Mathematikprogramm zu fördern. Inzwischen hat die vierte Förderperiode des Mathematikprogramms begonnen. \par Das Medium Internet und insbesondere das WWW sind für die Sichtbarkeit und Transparenz wissenschaftlicher Resultate in den letzten zehn Jahren immer wichtiger geworden. Wer nicht im Web "'sichtbar"' ist, läuft Gefahr, nicht wahrgenommen zu werden. Intention und Ziel des durchgeführten Projekts war es, ein Konzept für eine qualitativ hochwertige und umfassende Darstellung des BMBF Mathematikprogramms, insbesondere der in den Projekten erzielten Ergebnisse, zu entwickeln und zu realisieren und damit den Stellenwert und die Akzeptanz mathematischer Forschung in der Gesellschaft zu festigen und den Wissenstransfer zwischen mathematischer Forschung sowie Forschung und Entwicklung in der Wirtschaft und dem Dienstleistungsbereich zu fördern.

Beschreibung: Die KOBV-Zentrale betreibt mit dem KOBV-Portal neben der Metasuche in freien Online-Katalogen und Datenbanken ein Nachweisinstrument für elektronische Ressourcen, die von den Bibliotheken Berlin-Brandenburgs lizenziert sind und darüber hinaus diejenigen, die frei zugänglich sowie wissenschaftlich relevant sind. Die Erschließung der freien Ressourcen übernimmt eine kooperative Fachredaktion, die sich aus FachreferentInnen und -lektorInnen aus der Region rekrutiert. Dabei übernimmt jede beteiligte Person die Betreuung einer oder mehrerer Fachgruppen der Dewey Decimal-Classification (DDC) eigenverantwortlich. Die Aufgabe aller FachredakteurInnen besteht in der inhaltlichen Beschreibung, der Klassifizierung, der Vergabe von Schlagworten und der regelmäßigen Reevaluation der einzelnen Ressourcen. Die KOBV-Zentrale hat hierfür einen Kriterienkatalog entwickelt, der als Grundlage für die Beurteilung von elektronischen Ressourcen dient. Erschlossen werden die Ressourcen schließlich über ein webbasierte Eingabe-Tool, dem Metadata-Tool der KOBV-Zentrale. Über eine Mailingliste wird der Abstimmungsbedarf untereinander gedeckt und Diskussionen geführt, die das Projekt weiterführen sollen. Der Artikel beschreibt das Konzept der kooperativen Fachredaktion für freie Ressourcen, die Vorgänge und die Arbeiten, die für die Initiierung notwendig waren.

Beschreibung: We present a new algorithm for fairing of space curves with respect spatial constraints based on a vector valued curvature function. Smoothing with the vector valued curvature function is superior to standard Frenet techniques since the individual scalar components can be modeled similar to curvature-based curve smoothing techniques in 2d. This paper describes a curve smoothing flow that satisfies strict spatial constraints and allows simultaneous control of both curvature functions.

Beschreibung: Scattering problems in integrated optics can be modeled in simple cases by the Helmholtz equation. The computational domain is truncated by a non-reflecting boundary condition. We investigate Schwarz algorithms with a sort of DtN operator, realized by the PML-method, at the interfaces of the sub-domains as an iterative solver.

Beschreibung: Adaptive numerical methods in space and time are introduced and studied for multiscale cardiac reaction-diffusion models in three dimensions. The evolution of a complete heartbeat, from the excitation to the recovery phase, is simulated with both the anisotropic Bidomain and Monodomain models, coupled with either a variant of the simple FitzHugh-Nagumo model or the more complex phase-I Luo-Rudy ionic model. The simulations are performed with the {\sc kardos} library, that employs adaptive finite elements in space and adaptive linearly implicit methods in time. The numerical results show that this adaptive method successfully solves these complex cardiac reaction-diffusion models on three-dimensional domains of moderate sizes. By automatically adapting the spatial meshes and time steps to the proper scales in each phase of the heartbeat, the method accurately resolves the evolution of the intra- and extra-cellular potentials, gating variables and ion concentrations during the excitation, plateau and recovery phases.

Beschreibung: Mathematical decision support for operative planning in water supply systems is highly desirable but leads to very difficult optimization problems. We propose a nonlinear programming approach that yields practically satisfactory operating schedules in acceptable computing time even for large networks. Based on a carefully designed model supporting gradient-based optimization algorithms, this approach employs a special initialization strategy for convergence acceleration, special minimum up and down time constraints together with pump aggregation to handle switching decisions, and several network reduction techniques for further speed-up. Results for selected application scenarios at Berliner Wasserbetriebe demonstrate the success of the approach.

Beschreibung: The theory of hierarchical Boolean satisfiability (SAT) solving proposed in this paper is based on a strict axiomatic system and introduces a new important notion of implicativity. The theory makes evident that increasing implicativity is the core of SAT-solving. We provide a theoretical basis for increasing the implicativity of a given SAT instance and for organizing SAT-solving in a hierarchical way. The theory opens a new domain of research: SAT-model construction. Now quite different mathematical models can be used within practical SAT-solvers. The theory covers many advanced techniques such as circuit-oriented SAT-solving, mixed BDD/CNF SAT-solving, merging gates, using pseudo-Boolean constraints, using state machines for representation of Boolean functions, arithmetic reasoning, and managing don t cares. We believe that hierarchical SAT-solving is a cardinal direction of research in practical SAT-solving.

Beschreibung: The \emph{fare planning problem} for public transport is to design a system of fares that maximize the revenue. We introduce a nonlinear optimization model to approach this problem. It is based on a d iscrete choice logit model that expresses demand as a function of the fares. We illustrate our approach by computing and comparing two different fare systems for the intercity network of the Netherlands.

Beschreibung: The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a network such that a giv en demand can be satisfied. There are two objectives. Passengers want to minimize travel times, the transport company wishes to minimize operating costs. We investigate three variants of a multi-commo dity flow model for line planning that differ with respect to passenger routings. The first model allows arbitrary routings, the second only unsplittable routings, and the third only shortest path rou tings with respect to the network. We compare these models theoretically and computationally on data for the city of Potsdam.

Beschreibung: \documentclass[12pt]{article} \usepackage{german} \parindent=0pt \begin{document} Im KOBV wird für die Online-Fernleihe der Zentrale-Fernleihserver (ZFL-Server) der Firma Sisis eingesetzt. Die Software ist in der KOBV-Zentrale installiert. Der ZFL-Server dient im KOBV sowohl für die Bestellung von Monographien als auch für die Bestellung von Aufsatzkopien aus Zeitschriften. Prinzipiell gibt es zwei Verfahren, mit denen sich Bibliotheken an der Online-Fernleihe beteiligen können: das E-Mail-Verfahren und das SLNP-Verfahren. Auf beide wird im Handbuch eingegangen. Die Online-Fernleihe wurde im KOBV eingeführt, um die Fernleihe für die Benutzer zu beschleunigen, das Verfahren für die Bibliotheksmitarbeiter zu vereinfachen und den Arbeitsaufwand zu reduzieren. Sie basiert darauf, dass eine Bestellung anhand eines gefundenen Treffers ausgelöst wird - d.h. die bibliographischen Daten sind bereits verifiziert und in einem Katalog nachgewiesen. Anschlie\"send werden die Fernleihbestellungen über den ZFL-Server automatisch ausgeführt und verwaltet - sowohl in der regionalen KOBV-Fernleihe als auch in der verbundübergreifenden Fernleihe mit den deutschen Bibliotheksverbünden. Der ZFL-Server besteht aus verschiedenen technischen Komponenten. Eine dieser Komponenten ist das Bibliothekskonto, eine Internetanwendung, in der die Bestellverwaltung des ZFL-Servers im Internet für die Bibliotheksbediensteten transparent gemacht wird. Sowohl für die aktive als auch für die passive Fernleihe ist im Bibliothekskonto der Status der Bearbeitung zu jedem Zeitpunkt ersichtlich, z.B. in welcher Bibliothek sich die Bestellung gerade befindet, wann sie dort eingegangen ist und wann sie weggeschickt wurde, ob mit positivem oder negativem Ergebnis. Das Bibliothekskonto ist damit für die Bibliothek ein komfortables Instrument zum Überwachen der Fernleihbestellungen, in dem sie zudem - falls notwendig - in den Bestellvorgang eingreifen kann. Dazu hat jede Bibliothek im Bibliothekskonto eine eigene, Passwort-geschützte Dienstoberfläche. Das vorliegende Handbuch beschreibt die Vorgänge der Bestellverwaltung im Bibliothekskonto. Es richtet sich an Bibliotheksmitarbeiter, die sich mit den einzelnen Arbeitsschritten der Online-Fernleihe vertraut machen wollen. Darüber hinaus ist es zum Nachschlagen gedacht, wenn sich in der täglichen Arbeit Unklarheiten ergeben. \end{document}

Beschreibung: The Feasibility Pump of Fischetti, Glover, Lodi, and Bertacco has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, tends to be poor. This paper proposes a slight modification of the algorithm in order to find better solutions. Extensive computational results show the success of this variant: in 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original Feasibility Pump.

Beschreibung: In this letter we report on a numerical investigation of the Aoki phase in the case of finite temperature which continues our former study at zero temperature. We have performed simulations with Wilson fermions at $\beta=4.6$ using lattices with temporal extension $N_{\tau}=4$. In contrast to the zero temperature case, the existence of an Aoki phase can be confirmed for a small range in $\kappa$ at $\beta=4.6$, however, shifted slightly to lower $\kappa$. Despite fine-tuning $\kappa$ we could not separate the thermal transition line from the Aoki phase.

Beschreibung: The dynamics of pressurized water distribution networks are naturally modeled by differential algebraic equations (DAE). This paper investigates fundamental structural properties of such a DAE model under weak regularity assumptions. The usual partial derivative-based index-1 condition is shown to be necessary and sufficient for several index concepts, as well as sufficient for solvability in a strong sense. Using the physical properties of nonlinear network elements and the inherent saddle point structure of network hydraulics, we then derive purely topological index criteria based on the network graph and the choice of control variables. Several examples illustrate the theoretical results and explore different non-index-1 situations. A brief discussion of the implications for operative planning by discrete time DAE boundary value problems concludes the paper.

Beschreibung: Using the popular puzzle game of Sudoku, this article highlights some of the ideas and topics covered in ZR-04-58.

Beschreibung: Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs $G$ where the stable set polytope $STAB(G)$ coincides with the fractional stable set polytope $QSTAB(G)$. For all imperfect graphs $G$ it holds that $STAB(G) \subset QSTAB(G)$. It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect; we discuss three different concepts, involving the facet set of $STAB( G)$, the disjunctive index of $QSTAB(G)$, and the dilation ratio of the two polytopes. Including only certain types of facets for $STAB(G)$, we obtain graphs that are in some sense close to perfect graphs, for example minimally immperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by (Gerke and McDiarmid, 2001) as the dilation ratio of $STAB(G)$ and $QSTAB(G)$, whereas (Aguilera et al., 2003) suggest to take the disjunctive index of $Q STAB(G)$ as the imperfection index of $G$. For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graph classes (Coulonges et al. 2005, Gerke and McDiarmid, 2001). Outgoing from a graph-theoretical interpretation of the imperfection index, we conclude that the imperfection index is NP-hard to compute and we prove that there exists no upper bound on the imperfect ion index for those graph classes with a known bounded imperfection ratio. Comparing the two invariants on those classes, it seems that the imperfection index measures imperfection much more roughly than the imperfection ratio; therefoe, discuss possible directions for refinements.

Beschreibung: Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later. We introduce the novel concept of an \emph{Online Target Date Assignment Problem} (\textsc{OnlineTDAP}) as a general framework for online problems with this nature. Requests for the \textsc{OnlineTDAP} become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.\,g., an appointment with a customer for a washing machine repair). The cost at a target date is given by the \emph{downstream cost}, the optimal cost of processing all requests at that date w.\,r.\,t.\ some fixed downstream offline optimization problem (e.\,g., the cost of an optimal dispatch for service technicians). We provide general competitive algorithms for the \textsc{OnlineTDAP} independently of the particular downstream problem, when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the par ticular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.

Beschreibung: Inhalt dieser Diplomarbeit ist ein Beleuchtungs- und Visualisierungsmodell für Pflanzen im interaktiven Landschaftsrendering. Ziel ist die qualitativ hochwertige Darstellung von einzelnen Individuen nahe des Betrachters, der seine Position in einer ansonsten statischen Szene frei wählen kann. Um dies zu erreichen wird zunächst vorgestellt, wie ausgehend von einfachen 3D-Modellen und Materialien ein physikalisch basiertes Reflexionsmodell parametrisiert werden kann. Grund hierfür ist der oftmals vorhandene umfangreiche Datenbestand, der auf die OpenGL-Materialien oder ähnliche Shader optimiert ist. Anschließend wird gezeigt, wie die Echtzeit-Renderingtechniken Shadow Mapping und Precomputed Radiance Transfer kombiniert werden können, um sowohl exakte hochfrequente direkte Beleuchtung als auch niederfrequentes indirektes Streulicht zu berücksichtigen. Diese Kombination wird an Hand der Pfad-Notation des Monte-Carlo-Path-Tracing eingeführt und begründet.

Beschreibung: Die hierarchische Organisation von Dateien beherrscht Computersysteme seit vielen Jahren und wird sich vermutlich auch in Zukunft weiterhin durchsetzen. Dennoch stößt diese Verwaltungsmethode in einem klassischen hierarchischen Dateisystem bei dem jährlichen rasanten Zuwachs an neuen Daten an ihre Grenzen, auch wenn Nutzer eine ausgefeilte Verzeichnisstruktur mit einer disziplinierten Namensgebung konsequent auf- und ausbauen. Um den Überblick über die Dateien zu behalten, werden in dieser Arbeit neue Verwaltungsmethoden vorgestellt und in die hierarchische Dateisystemsicht eingebettet. Auf der Basis des hierarchischen Dateisystems bietet ein metadatenbasiertes Dateisystem neben dem hierarchischen Zugriff noch einen flexiblen, assoziativen Zugriff auf Dateien über virtuelle Objekte, indem Suchmethoden in Form einer Anfrage auf in einer Datenbank gespeicherte Index- und Metadaten angewendet werden. Das Ergebnis dieser Abfrage wird mit Hilfe von virtuellen Verzeichnissen und virtuellen Dateien in einer übersichtlichen Form dargestellt, so dass eine Nutzung der hierarchischen Sicht weiterhin intuitiv fortgesetzt wird. Das Datenmanagementsystem ZIBDMS, welches einen verteilten Metadatenkatalog und einen Dateireplikationskatalog beinhaltet, ermöglicht es, die oben genannten Verwaltungsmethoden für die NFS-Schnittstelle, CORBA-Middleware und Web Services transparent zu implementieren. Zudem stellt ZIBDMS weitere neue Dateiverwaltungsmethoden zur Verfügung, die sich in die hierarchische Dateisystemsicht integrieren lassen. Metadaten in Form von Attribut-Wert-Paaren lassen sich als virtuelle Datei darstellen und editieren. Eine Collection bietet die Möglichkeit, Dateien in einem logischen virtuellen Ordner zu organisieren. Mit einem Dependency-Graph lassen sich Dateien zueinander in Relation stellen, so dass eine Linkstruktur zwischen Dateien ausgedrückt werden kann. Das Verweiskonzept eines klassischen hierarchischen Dateisystems wird im ZIBDMS um eine neue Verweisart Weak-Link erweitert, um einen aktualisierbaren, konsistenten und zyklenfreien symbolischen Link anzubieten. In einer hierarchischen Sicht lässt sich durch Verweise ein Baum bilden, in dem eine Navigation und Verweisauflistung möglich sind, was außer ZIBDMS noch kein anderes System bietet.

Beschreibung: The hierarchical organization of files has dominated computer systems for many years and this will probably not change in the near future. However, with the rapid annual growth of new data this classical hierarchical file system management method reaches its limitations, even when the user consistently sets up and continually expands an elaborated directory structure with well-disciplined naming. This paper introduces new management methods to maintain an overview of all files which can be embedded in the hierarchical file system. A metadata-based file system, which is based on the hierarchical file system, offers, in addition to hierarchical access, a more flexible and associative access to files via virtual objects by providing query capabilities of index- and metadata which are stored in a database. The query results are presented in a clearly-arranged form of virtual directories and virtual files so that the intuitive hierarchical view continues to be maintained. The data management system ZIBDMS, which contains a distributed metadata catalog and a file replication catalog, permits a transparent implementation of these management methods for the NFS interface, CORBA-middleware or web services. Furthermore, ZIBDMS provides other new file management methods that can be integrated into the hierarchical file system view. Metadata in form of attribute-value-pairs can be presented and edited with a virtual file. A Collection makes it possible to organize files in logical virtual folders. Using a Dependency graph, files can be related to each other and expressed through a link structure between these files. In the ZIBDMS the reference concept of a classical hierarchal file system is extended with a new kind of reference called Weak Link in order to provide up-to-date, consistent and cycle-free symbolic links. With the references a tree can be established in a hierarchical view in which navigation and listing of references are possible; this capability is only possible in the ZIBDMS system.

Beschreibung: Die hierarchische Organisation von Dateien beherrscht Computersysteme seit vielen Jahren und wird sich vermutlich auch in Zukunft weiterhin durchsetzen. Dennoch stößt diese Verwaltungsmethode in einem klassischen hierarchischen Dateisystem bei dem jährlichen rasanten Zuwachs an neuen Daten an ihre Grenzen, auch wenn Nutzer eine ausgefeilte Verzeichnisstruktur mit einer disziplinierten Namensgebung konsequent auf- und ausbauen. Um den Überblick über die Dateien zu behalten, werden in dieser Arbeit neue Verwaltungsmethoden vorgestellt und in die hierarchische Dateisystemsicht eingebettet. Auf der Basis des hierarchischen Dateisystems bietet ein metadatenbasiertes Dateisystem neben dem hierarchischen Zugriff noch einen flexiblen, assoziativen Zugriff auf Dateien über virtuelle Objekte, indem Suchmethoden in Form einer Anfrage auf in einer Datenbank gespeicherte Index- und Metadaten angewendet werden. Das Ergebnis dieser Abfrage wird mit Hilfe von virtuellen Verzeichnissen und virtuellen Dateien in einer übersichtlichen Form dargestellt, so dass eine Nutzung der hierarchischen Sicht weiterhin intuitiv fortgesetzt wird. Das Datenmanagementsystem ZIBDMS, welches einen verteilten Metadatenkatalog und einen Dateireplikationskatalog beinhaltet, ermöglicht es, die oben genannten Verwaltungsmethoden für die NFS-Schnittstelle, CORBA-Middleware und Web Services transparent zu implementieren. Zudem stellt ZIBDMS weitere neue Dateiverwaltungsmethoden zur Verfügung, die sich in die hierarchische Dateisystemsicht integrieren lassen. Metadaten in Form von Attribut-Wert-Paaren lassen sich als virtuelle Datei darstellen und editieren. Eine Collection bietet die Möglichkeit, Dateien in einem logischen virtuellen Ordner zu organisieren. Mit einem Dependency-Graph lassen sich Dateien zueinander in Relation stellen, so dass eine Linkstruktur zwischen Dateien ausgedrückt werden kann. Das Verweiskonzept eines klassischen hierarchischen Dateisystems wird im ZIBDMS um eine neue Verweisart Weak-Link erweitert, um einen aktualisierbaren, konsistenten und zyklenfreien symbolischen Link anzubieten. In einer hierarchischen Sicht lässt sich durch Verweise ein Baum bilden, in dem eine Navigation und Verweisauflistung möglich sind, was außer ZIBDMS noch kein anderes System bietet.

Beschreibung: The hierarchical organization of files has dominated computer systems for many years and this will probably not change in the near future. However, with the rapid annual growth of new data this classical hierarchical file system management method reaches its limitations, even when the user consistently sets up and continually expands an elaborated directory structure with well-disciplined naming. This paper introduces new management methods to maintain an overview of all files which can be embedded in the hierarchical file system. A metadata-based file system, which is based on the hierarchical file system, offers, in addition to hierarchical access, a more flexible and associative access to files via virtual objects by providing query capabilities of index- and metadata which are stored in a database. The query results are presented in a clearly-arranged form of virtual directories and virtual files so that the intuitive hierarchical view continues to be maintained. The data management system ZIBDMS, which contains a distributed metadata catalog and a file replication catalog, permits a transparent implementation of these management methods for the NFS interface, CORBA-middleware or web services. Furthermore, ZIBDMS provides other new file management methods that can be integrated into the hierarchical file system view. Metadata in form of attribute-value-pairs can be presented and edited with a virtual file. A Collection makes it possible to organize files in logical virtual folders. Using a Dependency graph, files can be related to each other and expressed through a link structure between these files. In the ZIBDMS the reference concept of a classical hierarchal file system is extended with a new kind of reference called Weak Link in order to provide up-to-date, consistent and cycle-free symbolic links. With the references a tree can be established in a hierarchical view in which navigation and listing of references are possible; this capability is only possible in the ZIBDMS system.

Beschreibung: One important step in the fabrication of silicon-based integrated circuits is the creation of semiconducting areas by diffusion of dopant impurities into silicon. Complex models have been developed to investigate the redistribution of dopants and point defects. In general, numerical analysis of the resulting PDEs is the central tool to assess the modelling process. We present an adaptive approach which is able to judge the quality of the numerical approximation and which provides an automatic mesh improvement. Using linearly implicit methods in time and multilevel finite elements in space, we are able to integrate efficiently the arising reaction-drift-diffusion equations with high accuracy. Two different diffusion processes of practical interest are simulated.

Beschreibung: Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. By determining almost invariant sets of the associated Markov operator, the Monte Carlo sampling splits by a hierarchical annealing process into the essential regions of the state space; therefore UCMC aims at avoiding the typical metastable behavior of Monte Carlo techniques. From the viewpoint of Monte Carlo, a slowly converging long-time Markov chain is replaced by a limited number of rapidly mixing short-time ones. The correct weighting factors for the various Markov chains are obtained via a coupling matrix, that connects the samplings from the different almost invariant sets. The underlying mathematical structure of this approach is given by a general examination of the uncoupling-coupling procedure. Furthermore, the overall algorithmic scheme of UCMC is applied to the $n$-pentane molecule, a well-known example from molecular dynamics.

Beschreibung: The traveling repairman problem (TRP) is a variant of the famous traveling salesman problem (TSP). The objective for the TRP is to minimize the latency, that is the the weighted sum of completion times of the cities, where the completion time of a city is defined to be the time in the tour before the city is reached. In the online traveling repairman problem (OLTRP) requests for visits to cities (points in a metric space) arrive online while the repairman is traveling. We analyze the performance of algorithms using competitive analysis, where the cost of an online algorithm is compared to that of an optimal offline algorithm. An optimal offline algorithm knows the entire request sequence in advance and can serve it with minimum cost. Recently, Feuerstein and Stougie presented a $9$-competitive algorithm for the OLTRP on the real line. In this paper we show how to use techniques from online-scheduling to obtain an $8$-competitive deterministic algorithm which works for any metric space. We also present a randomized algorithm which has a competitive ratio of $\frac{4}{\ln 2}\approx 5.7708$ against an oblivious adversary. All of our results also hold for the ``dial-a-ride'' generalization of the OLTRP, where objects have to be picked up and delivered by a server.

Beschreibung: In the online traveling salesman problem requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman which finishes as early as possible. Performance of algorithms is measured through their competitive ratio, comparing the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline solution. Objections against such omnipotent adversaries have lead us to devise an adversary that is in a natural way, in the context of routing problems, more restricted in power. For the exposition we consider the online traveling salesman problem on the metric space given by the non-negative part of the real line. We show that a very natural strategy is~$3/2$-competitive against the conventional adversary, which matches the lower bound on competitive ratios achievable for algorithms for this problem. Against the more ``\emph{fair adversary}'', that we propose, we show that there exists an algorithm with competitive ratio $\frac{1+\sqrt{17}}{4}\approx 1.28$ and provide a matching lower bound. We also show competitiveness results for a special class of algorithms (called zealous algorithms) that do not allow waiting time for the server as long as there are requests unserved.

Beschreibung: Regional hyperthermia, a clinical cancer therapy, is the main topic of the Sonderforschungsbereich Hyperthermia: Scientific Methods and Clinical Applications'' at Berlin. In recent years, technological improvements towards a better concentration of heat to the desired target region have been achieved. These include a rather sophisticated integrated software environment for therapy planning and a new hyperthermia applicator. In a next step, a detailed closed loop monitoring of the actual treatment is to be developed. For this purpose the hyperthermia applicator is combined with an MRI system, which will allow to check the positioning of the patients and to measure individual blood perfusion as well as the 3D temperature distribution. The measurements will then be employed for an on-line control of the whole treatment. In this intended setting, new fast feedback control algorithms will come into play.

Beschreibung: In diesem Artikel wird der Status des Projekts Kooperativer Bibliotheksverbund Berlin-Brandenburg beschrieben, der im November 1999 mit der KOBV-Suchmaschine seinen produktiven Betrieb aufgenommen hat. Die Recherchemöglichkeiten im WWW werden erläutert, Zugriffszahlen genannt und Entwicklungsperspektiven skizziert. Dieser Bericht entspricht der schriftlichen Fassung eines gleichnamigen Vortrages, der auf dem 1. Gemeinsamen Kongreß der Bundesvereinigung Deutscher Bibliotheksverbände e.V. und der Deutschen Gesellschaft für Informationswissenschaft und Informationspraxis e.V. Information und Öffentlichkeit gehalten wurde, der vom 20. bis 23. März 2000 in Leipzig stattfand.

Beschreibung: In this paper for the $M(n)/M(n)/s+GI$ system, i.e.\ for a $s$-server queueing system where the calls in the queue may leave the system due to impatience, we present new asymptotic results for the intensities of calls leaving the system due to impatience and a Markovian system approximation where these results are applied. Furthermore, we present a new proof for the formulae of the conditional density of the virtual waiting time distributions, recently given by Movaghar for the less general $M(n)/M/s+GI$ system. Also we obtain new explicit expressions for refined virtual waiting time characteristics as a byproduct.

Beschreibung: Several practical instances of network design problems require the network to satisfy multiple constraints. In this paper, we address the \emph{Budget Constrained Connected Median Problem}: We are given an undirected graph $G = (V,E)$ with two different edge-weight functions $c$ (modeling the construction or communication cost) and $d$ (modeling the service distance), and a bound~$B$ on the total service distance. The goal is to find a subtree~$T$ of $G$ with minimum $c$-cost $c(T)$ subject to the constraint that the sum of the service distances of all the remaining nodes $v \in V\setminus T$ to their closest neighbor in~$T$ does not exceed the specified budget~$B$. This problem has applications in optical network design and the efficient maintenance of distributed databases. We formulate this problem as bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem that demonstrate that our performance ratios are close to best possible

Beschreibung: Network loading problems occur in the design of telecommunication networks, in many different settings. The polyhedral structure of this problem is important in developing solution methods for the problem. In this paper we investigate the polytope of the problem restricted to one edge of the network (the edge capacity problem). We describe classes of strong valid inequalities for the edge capacity polytope, and we derive conditions under which these constraints define facets. As the edge capacity problem is a relaxation of the network loading problem, their polytopes are intimately related. We, therefore, also give conditions under which the inequalities of the edge capacity polytope define facets of the network loading polytope. Furthermore, some structural properties are derived, such as the relation of the edge capacity polytope to the knapsack polytope. We conclude the theoretical part of this paper with some lifting theorems, where we show that this problem is polynomially solvable for most of our classes of valid inequalities. In a computational study the quality of the constraints is investigated. Here, we show that the valid inequalities of the edge capacity polytope are not only important for solving the edge capacity problem, but also for the network loading problem, showing that the edge capacity problem is an important subproblem.

Beschreibung: Die Entwicklung einer bibliothekarischen Suchmaschine ist das technisch-organisatorische Herztück des Kooperativen Bibliotheksverbundes Berlin-Brandenburg (KOBV). Auf dem Wege über diese Innovation verfolgen die Länder Berlin und Brandenburg und ihre Bibliotheken das Ziel, ihr Bibliothekswesen zu erneuern und zu reorganisieren. Die Entwicklung der Suchmaschine ist für die Partner im KOBV-Projekt kein Selbstzweck, sondern nur Mittel zum Zweck - insbesondere, um die heterogene Welt der in Berlin und in Brandenburg eingesetzten integrierten Bibliotheksinformationssysteme harmonisch miteinender zu verbinden. Mit der KOBV-Suchmaschine sind informationstechnische Sichtweisen und Methoden entstanden, die sich potentiell auch auf die überregionale Arbeit des KOBV auswirken können und in Kooperation mit den Bibliotheksverbänden auf die Zusammenarbeit der Verbünde insgesamt. Der Artikel konzentriert sich am Beispiel der KOBV-Such¡ma¡schine auch auf diesen Aspekt. Auf die Bibliotheken kommen mit dem Internet und dem World Wide Web für sie neuartige Medien, Mittel und Aufgaben zu, in erster Linie aus dem Bereich der Wissenschaften und der wissenschaftlichen Fachgesellschaften. Die Herausforderung besteht darin, die neuen elektronischen Informationen und Angebote zu integrieren. Das Stichwort hierzu lautet digitale Bibliothek bzw. virtuelle Fachbibliothek. Auch zu der Diskussion um diese aktuelle Entwicklung will der Artikel einen Beitrag leisten.

Beschreibung: The improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering is studied on $10^4$ and $12^4$ lattices. As an indicator for decorrelation the topological charge is used.

Beschreibung: In this paper we describe the results of a computational study towards the (re)optimization of signaling transfer points (STPs) in telecommunication networks. The best performance of an STP is achieved whenever the traffic load is evenly distributed among the internal components. Due to the continuously changing traffic pattern, the load of the components has to be re-optimized on a regular basis. Besides the balancing objective also the number of rearrangements have to be taken into account. In this paper we present two alternative formulations to deal with both requirements. Computational results show that for both formulations (near) optimal solutions can be obtained within reasonable time limits.

Beschreibung: The structures and interaction energies of guanine and uracil quartets have been determined by B3LYP hybrid density functional calculations. The total interaction energy $\Delta$E$^{T}$ of the $\it{C}$$_{4h}$-symmetric guanine quartet consisting of Hoogsteen type base pairs with two hydrogen bonds between two neighbour bases is -66.07 kcal/mol at the highest level. The uracil quartet with C6-H6...O4 interactions between the individual bases has only a small interaction energy of -20.92 kcal/mol and the interaction energy of -24.63 kcal/mol for the alternative structure with N3-H3...O4 hydrogen bonds is only slightly more negative. Cooperative effects contribute between 10 and 25 \% to all interaction energies. Complexes of metal ions with G-quartets can be classified into different structure types. The one with Ca$^{2+}$ in the central cavity adopts a $\it{C}$$_{4h}$-symmetric structure with coplanar bases, whereas the energies of the planar and non-planar Na$^{+}$ complexes are almost identical. The small ions Li$^{+}$, Be$^{2+}$, Cu$^{+}$ and Zn$^{2+}$ prefer a non-planar $\it{S}$$_{4}$-symmetric structure. The lack of co-planarity prevents probably a stacking of these base quartets. The central cavity is too small for K$^{+}$ ions and therefore this ion favours in contrast to all other investigated ions a $\it{C}$$_{4}$-symmetric complex, which is 4.73 kcal/mol more stable than the $\it{C}$$_{4h}$-symmetric one. The distance 1.665 {\AA} between K$^{+}$ and the root mean squares plane of the guanine bases is approximately half of the distance between two stacked G-quartets. The total interaction energy of alkaline earth ion complexes exceeds the ones with alkali ions. Within both groups of ions the interaction energy decreases with an increasing row position in the periodic table. The B3LYP and BLYP methods lead to similar structures and energies. Both methods are suitable for hydrogen-bonded biological systems. Compared with the before mentioned methods the HCTH functional leads to longer hydrogen bonds and different relative energies for two U-quartets. Finally we calculated also structures and relative energies with the MMFF94 forcefield. Contrary to all DFT methods, MMFF94 predicts bifurcated C-H...O contacts in the uracil quartet. In the G-quartet the MMFF94 hydrogen bond distances N2-H22...N7 are shorter than the DFT distances, whereas the N1-H1...O6 distances are longer.

Beschreibung: Das vorliegende Skript bietet eine Einf{ü}hrung in die Graphentheorie und graphentheoretische Algorithmen. Im zweiten Kapitel werden Grundbegriffe der Graphentheorie vorgestellt. Das dritte Kapitel besch{ä}ftigt sich mit der Existenz von Wegen in Graphen. Hier wird auch die L{ö}suung des ber{ü}hmten K{ö}nigsberger Br{ü}ckenproblems aufgezeigt und der Satz von Euler bewiesen. Im vierten Kapitel wird gezeigt, wie man auf einfache Weise die Zusammenhangskomponenten eines Graphen bestimmen kann. Im Kapitel sechs wird dann sp{ä}ter mit der Tiefensuche ein Verfahren vorgestellt, das schneller arbeitet und mit dessen Hilfe man noch mehr Informationen {ü}ber die Struktur eines Graphen gewinnen kann. In den folgenden Kapiteln werden Algorithmen vorgestellt, um minimale aufspannenden B{ä}ume, k{ü}rzeste Wege und maximale Fl{ü}sse in Graphen zu bestimmen. Am Ende des Skripts wird ein kurzer Einblick in die planaren Graphen und Graphhomomorphismen geboten.

Beschreibung: Pyridinochelin, a novel catecholate type siderophore, has been designed on the basis of the active analog enterobactin. Growth promotion tests indicate that this synthetic siderophore feeds various pathogenic bacteria effectively with iron even though it lacks one catecholate group compared to enterobactin. The superposition of the siderophore structures suggests that the structure of the skeleton connecting the catecholate groups might be an important factor for the iron transport.

Beschreibung: Dynamical process simulation of complex real-life problems often requires the use of modern algorithms, which automatically adapt both the time and space discretization in order to get error-controlled approximations of the solution. In this paper, a combination of linearly implicit time integrators of Rosenbrock type and adaptive multilevel finite elements based on a posteriori error estimates is presented. This approach has proven to work quite satisfactorily for a wide range of challenging practical problems. We show the performance of our adaptive method for two applications that arise in the study of flame balls and brine transport in porous media.

Beschreibung: The statistical behavior of deterministic and stochastic dynamical systems may be described using transfer operators, which generalize the notion of Frobenius Perron and Koopman operators. Since numerical techniques to analyze dynamical systems based on eigenvalues problems for the corresponding transfer operator have emerged, bounds on its essential spectral radius became of interest. This article shows that they are also of great theoretical interest. We give an analytical representation of the essential spectral radius in $L^{1}\!(\mu)$, which then is exploited to analyze the asymptotical properties of transfer operators by combining results from functional analysis, Markov operators and Markov chain theory. In particular, it is shown, that an essential spectral radius less than $1$, constrictiveness and some weak form'' of the so--called Doeblin condition are equivalent. Finally, we apply the results to study three main problem classes: deterministic systems, stochastically perturbed deterministic systems and stochastic systems.

Beschreibung: We focus on two new types of extremal graphs with respect to perfectness: critically and anticritically perfect graphs that lose their perfectness by simply deleting and adding an arbitrary edge, respectively. We present examples and study properties in order to compare critically and anticritically perfect graphs with minimally imperfect graphs, another type of extremal graphs with respect to perfectness. We discuss two attempts to characterize the classes of all critically and anticritically perfect graphs and give a brief overview on classes of perfect graphs which contain critically or anticritically perfect graphs.

Beschreibung: A path following algorithm for linear complementarity problems is presented. Given a point $z$ that approximates a point $z(\tau)$ on the central path with complementarity gap $\tau$, one determines a parameter $\theta\in (0,1)$ so that this point satisfies the hypothesis of the affine invariant Kantorovich Theorem for the equation defining $z((1-\theta)\tau)$. It is shown that $\theta$ is bounded below by a multiple of $n^{-1/2}$, where $n$ is the dimension of the problem. Since the hypothesis of of the Kantorovich Theorem is satisfied the sequence generated by Newton's method, or by the simplified Newton method, will converge to $z((1-\theta)\tau)$. We show that the number of steps required to obtain an acceptable approximation of $z((1-\theta)\tau)$ is bounded above by a number independent of $n$. Therefore the algorithm has $O(\sqrt{n}L)$-iteration complexity. The parameters of the algorithm can be determined in such a way that only one Newton step is needed each time the complementarity gap is decreased.

Beschreibung: The polynomial differential system modelling the behavior of a chemical reaction is given by graphtheoretic structures. The concepts from toric geometry are applied to study the steady states and stable steady states. Deformed toric varieties give some insight and enable graph theoretic interpretations. The importance of the circuits in the directed graph are emphazised. The counting of positive solutions of a sparse polynomial system by B.\ Sturmfels is generalized to the counting of stable positive solutions in case of a polynomial differential equation. The generalization is based on a method by sparse resultants to detect whether a system may have a Hopf bifurcation. Special examples from chemistry are used to illustrate the theoretical results.

Beschreibung: The increasing demand for distributed solutions in computing technology does not stop when it comes to visualization techniques. However, the capabilities of todays applications to perform remote rendering are limited by historical design legacys. Especially the popular X11 protokoll, which has been proven to be extremely flexible and usefull for remote 2D graphics applications, breaks down for the case of remote 3D rendering. In this white paper, we give a short overview of generic remote rendering technologies available today, and compare their performance to the recently released vizserver by SGI: a network extension to the SGI OpenGL rendering engines.

Beschreibung: This book offers a self-contained introduction to the field of semidefinite programming, its applications in combinatorial optimization, and its computational methods. We equip the reader with the basic results from linear algebra on positive semidefinite matrices and the cone spanned by them. Starting from linear programming, we introduce semidefinite programs and discuss the associated duality theory. We then turn to semidefinite relaxations of combinatorial optimization and illustrate their interrelation. In the second half we deal with computational methods for solving semidefinite programs. First, the interior point approach, its iteration complexity, and implementational issues are discussed. Next, we explain in great detail the spectral bundle method, which is particularly suited for large scale semidefinite programming. One of the most successful techniques in integer linear programming is the cutting plane approach which improves an initial relaxation by adding violated inequalities. We explore possibilities to combine the two solution methods with the cutting plane approach in order to strengthen semidefinite relaxations of combinatorial optimization problems.

Beschreibung: \\{\bf Zusammenfassung:} Kostenmodelle dienen der Ermittlung von Programmlaufzeiten, zum Vergleich der Effizienz von Algorithmen und zur Analyse des Verhaltens von Speicherhierarchien. Ein neuartiges Kostenmodell ist das Latency-of-Data-Access (LDA) Modell, das mehrere hierarchische Speicherebenen mit unterschiedlichen Latenzzeiten berü{}cksichtigt. In dieser Diplomarbeit wird ein Simulator fü{}r Speicherhierarchien prä{}sentiert, der die Berechnung von Programmausfü{}hrungszeiten nach dem LDA-Modell erlaubt. Mit Hilfe des Simulators wird die These geprü{}ft, da\ss{} mit diesem Modell die Ausfü{}hrungszeit eines Programms adä{}quat abgeschä{}tzt werden kann. Mit dem Simulator ist es erstmals praktikabel mö{}glich, Programmausfü{}hrungszeiten nach dem LDA-Modell zu bestimmen. Der Simulator kann fü{}r Systeme mit unterschiedlichen Speicherarchitekturen konfiguriert werden und unterstü{}tzt Mehrprozessorsysteme mit gemeinsamem Speicher (SMP-Systeme) mit verschiedenen Kohä{}renzprotokollen. Der Simulator kann mit den Ergebnissen von Microbenchmarks konfiguriert werden, die die Architekturparameter einer Speicherhierarchie messen. Die Ergebnisse bestä{}tigen die These nicht nur fü{}r Einzelprozessorsysteme, sondern auch fü{}r SMP-Systeme, wo gleichzeitig interagierende Prozessoren gegenseitig ihre Zugriffssequenz auf Zwischenspeicher beeinflussen. Zusä{}tzlich wurde eine neue Einsatzmö{}glichkeit des LDA-Modells entwickelt, um die Ausfü{}hrungszeit von Programmteilen zu bestimmen. Einzelne Zugriffskosten kö{}nnen einem mehrerer parallel laufender Modelle zugeordnet werden. Dadurch kö{}nnen Kosten, die Zugriffe auf einzelne Speicherbereiche verursachen, separat bestimmt werden. Diese Profiling-Technik erlaubt Optimierungen an Datenstrukturen und Speicherzugriffsmustern durch prä{}zise und gezielte Informationsproduktion.Cost models are used to determine the execution time of programs, to compare the efficiency of algorithms, and to analyse the behaviour of memory hierarchies. The Latency-of-Data-Access (LDA) model that takes into account multiple hierarchical memory levels with different latencies, is a newly proposed, innovative cost model. In this diploma-thesis, a simulator for memory hierarchies is presented that allows the calculation of execution times using the LDA-model. The simulator is used to prove the claim that the execution time of a program can be accurately estimated with the LDA-model. With the simulator, it is for the first time possible to determine the execution time of programs with this model in a practical way. The simulator can be configured for systems with various cache architectures and supports shared memory (SMP) multiprocessor systems with different cache coherence protocols. The simulator can be configured with the results from microbenchmarks which measure the architectural properties of a memory hierarchy. The results confirm the claim not only for single processor systems, but also for SMP systems, where concurrently interacting processors influence each others cache access sequence. Additionally, a new field of usage of the LDA-model was developed to determine execution times of program parts. Single access costs can be assigned to one of several parallel running models. As an example the costs of accesses to different memory areas can be split and determined separately. This profiling technique allows to optimise data structures and memory access patterns of sequential and parallel SMP programs by precise production of information.

Beschreibung: \texttt{SBmethod}, Version 1.1, is an implementation of the spectral bundle method for eigenvalue optimization problems of the form \begin{displaymath} \min_{y\in \mathbf{R}^m}\;\; a\;\lambda_{\max}(C-\sum_{i=1}^{m} A_i y_i)+b^Ty. \end{displaymath} The design variables $y_i$ may be sign constrained, $C$ and and $A_i$ are given real symmetric matrices, $b\in\mathbf{R}^m$ allows to specify a linear cost term, and $a〉0$ is a constant multiplier for the maximum eigenvalue function $\lambda_{\max}(\cdot)$. The code is intended for large scale problems and allows to exploit structural properties of the matrices such as sparsity and low rank structure. The manual contains instructions for installation and use of the program. It describes in detail input format, options, and output. The meaning of the variables and parameters is made precise by relating them to a mathematical description of the algorithm in pseudocode.

Beschreibung: In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets. For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined. The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks.

Beschreibung: In this paper we present the {\em SteinLib}, a library of data sets for the Steiner tree problem in graphs. This library extends former libraries on Steiner tree problems by many new interesting and difficult instances, most of them arising from real-world applications. We give a survey on the difficulty of these problem instances by giving references to state-of-the-art software packages that were the first or are currently among the best to solve these instances.

Beschreibung: Workstation clusters are often not only used for high-throughput computing in time-sharing mode but also for running complex parallel jobs in space-sharing mode. This poses several difficulties to the resource management system, which must be able to reserve computing resources for exclusive use and also to determine an optimal process mapping for a given system topology. On the basis of our CCS software, we describe the anatomy of a modern resource management system. Like Codine, Condor, and LSF, CCS provides mechanisms for the user-friendly system access and management of clusters. But unlike them, CCS is targeted at the effective support of space-sharing parallel and even metacomputers. Among other features, CCS provides a versatile resource description facility, topology-based process mapping, pluggable schedulers, and hooks to metacomputer management.

Beschreibung: Das aus den Medien bekannte umstrittene Ziegenproblem (auch Drei-Türen-Problem genannt) wird vollständig analysiert und gelöst. In der Streitfrage spielen sprachliche Mehrdeutigkeiten der Problemformulierung eine wesentliche Rolle; zudem werden Zufallsereignisse mit willkürlicher Information über deren Ergebnisse verwechselt. Tatsächlich erweisen sich beide strittigen Lösungen als teilweise richtige Bestandteile der Gesamtlösung. Die Argumentation wird in allgemeinverständlicher Sprache geführt und anschliessend durch eine formale mathematische Betrachtung ergänzt.

Beschreibung: Der Aufsatz ist die ausgearbeitete Fassung eines Vortrages, gehalten auf dem 2. BSZ-Kolloquium des Bibliotheksservice-Zentrums Baden-Württemberg (BSZ) am 10. Oktober 2000 in Konstanz. Der Kooperative Bibliotheksverbund Berlin-Brandenburg, kurz KOBV, ist ein sehr junger Verbund - genauer gesagt, befindet er sich im Oktober 2000 immer noch in der Aufbauphase. Das KOBV-Projekt hat am 1. April 1997 begonnen und wird am 31. Dezember 2000 enden. Ab 2001 wird der KOBV in eine institutionalisierte Form überführt, die - wie bereits das Projekt - am Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) - angesiedelt wird. Mit dem KOBV wurde ein in technischer wie auch in organisatorischer Hinsicht neuartiger Bibliotheksverbund aufgebaut, der auf der \glqq Internetphilosophie\grqq basiert: Den technischen Kern bildet eine eigens entwickelte Suchmaschine; die Organisation ist dezentral ausgerichtet und gründet sich auf der Kooperation der KOBV-Partner. In dem Vortrag werden das technische und das organisatorische Verbundkonzept vorgestellt, über die Erfahrungen nach einjähriger Betriebsdauer berichtet und ein kurzer Ausblick darüber gegeben, wie es mit dem KOBV weitergeht.

Beschreibung: Die Kommunikation zwischen der KOBV-Suchmaschine und entfernten Bibliotheksinformationssystemen unterschiedlicher Hersteller wird über das Standardprotokoll Z39.50 abgewickelt. Die Suchmaschine ermöglicht Online-Recherchen in lokalen Bibliotheksinformationssystemen, die dazu ein Z39.50 Target (Server) zur Verfügung stellen müssen. Die Suchmaschine liefert ihre Daten ebenfalls über Z39.50 aus. Ein Lokalsystem benötigt hierfür einen Z39.50 Origin (Client). In dem Papier wird die Schnittstelle zwischen der KOBV-Suchmaschine und lokalen Bibliothekssystemen spezifiziert: Es werden die grundlegenden Anforderungen an Lokalsysteme definiert und die Konfigurationsparameter für die Z39.50-Kommunikation zwischen KOBV-Suchmaschine und Lokalsystemen beschrieben.

Beschreibung: Die zunehmende Verfügbarkeit von mobilen Geräten, die mit einem Internetanschluß ausgerüstet sind, bringt auch eine steigende Nachfrage nach Informationsdiensten für diese Art von Clients mit sich. Das ZIB stellt mit seinem Höchstleistungsrechner vom Typ SGI/CRAY T3E Wissenschaftlern große Rechenkapazitäten zur Verfügung. Im Rahmen dieser Studienarbeit wurde ein WAP-Interface zur T3E entwickelt, das es den Nutzern ermöglicht, über ein mobiles, WAP-fähiges Gerät Informationen zur Betriebsbereitschaft und zur Auslastung des Höchstleistungsrechners, sowie Informationen zu den von ihnen in Auftrag gegebenen Rechenjobs abzurufen. Die Untersuchung der aktuellen Möglichkeiten in der mobilen Kommunikation brachte einige Einschränkungen für das geplante Informationsangebot mit sich. So mußte auf Grund von Sicherheitsbedenken auf eine tatsächliche Interaktionsmöglichkeit (z.B. neue Rechenjobs zu starten) verzichtet werden. Demgegenüber konnte gezeigt werden, daß die Bereitstellung der gleichen Informationen für unterschiedliche Arten von Clients (WWW-Browser $\rightarrow$ HTML, WAP-Browser $\rightarrow$ WML) durch die Verwendung von XML als internes Datenformat problemlos möglich ist. Es hat sich gezeigt, daß die Bereitstellung eines WAP-Informationsdienstes auf Grund verschiedener Inkompatibilitätsprobleme (verschiedene Gateways, verschiedene WAP-Browser) mit erheblichem Aufwand verbunden sein kann. An dieser Stelle besteht noch Handlungsbedarf seitens der Hersteller dieser Softwarepakete.

Beschreibung: Anwendungen der Mathematik in der Verkehrs- und Transporttechnologie haben eine große und bedeutende Tradition. Natürlich wurden die ersten Fahrzeuge mit der ingenieurmäßigen Methode von Versuch, Irrtum und Verbesserung entworfen. Aber schon sehr bald kamen mathematische Berechnungen hinzu, mit denen mechanische Eigenschaften von Fahrzeugteilen ermittelt und zum Teil optimiert wurden. Die hierzu erforderliche Mathematik wurde in diesem Jahrhundert zu einem mächtigen Werkzeugkasten ausgebaut. Mit diesem kann man heute z.B. hocheffiziente Motoren mit geringem Schadstoffausstoß entwerfen, aerodynamisch günstige Fahrzeugprofile ermitteln und Flugzeugflügel berechnen, die die gewünschte Last sicher und mit geringem Treibstoffaufwand tragen. Die Mathematik unterstützt die Technologie des Verkehrs beginnend bei globalen Designfragen bis hin zur Spezifizierung von Materialeigenschaften kleinster Bauteile; sie berechnet mit hoher Präzision energieoptimale Bahnen von Raumflugkörpern oder zeitoptimale Trajektorien für Flugzeuge, steuert automatische Roboteranlagen oder innerbetriebliche Transportsysteme.