Bibliothek

Beschreibung: Die harmonische Integration der Navigation und Suche in lizenzierten Journalen und gleichzeitig in freien digitalen Dokumenten unter einer einheitlichen konsistenten Nutzeroberflache ist eines der ungelösten F&E-Probleme der Fachinformation. Hierfür sollen Elemente des Invisible Web und des Visible Web unter Berücksichtigung offener Standards nahtlos #I miteinander verbunden werden. Dem Projekt liegt ein Modell mit Internet-Index, Metasuche und Open Linking über verteilten heterogenen Speichern #I zu Grunde: Verschiedenste Server, digitale Referenzen in Artikeln und Dokumenten, Links in Datenbanken und auf Bestelldienste sollen unter Berücksichtigung von Standort-, Studien- und Lernbedingungen kooperativ miteinander vernetzt werden. Die Leistungsfähigkeit des Modells soll in Pilotimplementierungen getestet und für eine breite Anwendung vorbereitet werden. Auf dieser Basis soll das Vorhaben Verteilter Zeitschriftenserver der AG der Verbundsysteme in eigenen Teilprojekten kooperativ initiiert werden, das jetzt in das Vorhaben Verteilter Dokumentenserver von vascoda integriert ist.

Beschreibung: The mathematical modeling of a special modular catalytic reactor kit leads to a system of partial differential equation in two space dimensions. As customary, this model contains unconfident physical parameters, which may be adapted to fit experimental data. To solve this nonlinear least squares problem we apply a damped Gauss-Newton method. A method of lines approach is used to evaluate the associated model equations. By an a priori spatial discretization a large DAE system is derived and integrated with an adaptive, linearly-implicit extrapolation method. For sensitivity evaluation we apply an internal numerical differentiation technique, which reuses linear algebra information from the model integration. In order not to interfere the control of the Gauss-Newton iteration these computations are done usually very accurately and, therefore, very costly. To overcome this difficulty, we discuss several accuracy adaptation strategies, e.g., a master-slave mode. Finally, we present some numerical experiments.

Beschreibung: Many real world problems can be mapped onto graphs and solved with well-established efficient algorithms studied in graph theory. One such problem is to find large sets of points satisfying some mutual relationship. This problem can be transformed to the problem of finding all cliques of an undirected graph by mapping each point onto a vertex of the graph and connecting any two vertices by an edge whose corresponding points satisfy our desired relationship. Clique detection has been widely studied and there exist efficient algorithms. In this paper we study a related problem, where all points have a set of binary attributes, each of which is either 0 or 1. This is only a small limitation, since all discrete properties can be mapped onto binary attributes. In our case, we want to find large sets of points not only satisfying some mutual relationship; but, in addition, all points of a set also need to have at least one common attribute with value 1. The problem we described can be mapped onto a set of induced subgraphs, where each subgraph represents a single attribute. For attribute $i$, its associated subgraph contains those vertices corresponding to the points with attribute $i$ set to 1. We introduce the notion of a maximal clique of a family, $\mathcal{G}$, of induced subgraphs of an undirected graph, and show that determining all maximal cliques of $\mathcal{G}$ solves our problem. Furthermore, we present an efficient algorithm to compute all maximal cliques of $\mathcal{G}$. The algorithm we propose is an extension of the widely used Bron-Kerbosch algorithm.

Beschreibung: We present an integer linear programming model for the design of multi-layer telecommunication networks. The formulation integrates hardware, capacity, routing, and grooming decisions in \emph{any} n umber of network layers. Practical hardware restrictions and cost can accurately be taken into account for technologies based on connection-oriented routing protocols.

Beschreibung: We introduce FreeLence, a lossless single-rate connectivity compression algorithm for triangle surface meshes. Based upon a geometry-driven traversal scheme we present two novel and simple concepts: free-valence connectivity encoding and entropy coding based on geometric context. Together these techniques yield significantly smaller rates for connectivity compression than current state of the art approaches - valence-based algorithms and Angle- Analyzer, with an average of $36\%$ improvement over the former and an average of $18\%$ over the latter on benchmark 3D models, combined with the ability to well adapt to the regularity of meshes. We also prove that our algorithm exhibits a smaller worst case entropy for a class of "'well-behaved"' triangle meshes than valence-driven connectivity encoding approaches.

Beschreibung: In this article, we present a mathematical model and an algorithm to support one of the central strategic planning decisions of network operators: How to organize a large number of locations into a hierarchical network? We propose a solution approach that is based on mixed-integer programming and Lagrangian relaxation techniques. As major advantage, our approach provides not only solutions but also worst-case quality guarantees. Real-world scenarios with more than 750 locations have been solved within 30 minutes to less than 1\% off optimality.

Beschreibung: This paper is concerned with UMTS radio network design. Our task is to reconfigure antennas and the related cells as to improve network quality. In contrast to second generation GSM networks, \emph{interference} plays a paramount role when designing third generation radio networks. A known compact formulation for assessing the interference characteristics of a radio network as coupling relations between cells based on user snapshots is generalized to statistical average load. This enables us to overcome the notorious difficulties of snapshot-based network optimization approaches. We recall a mixed-integer programming model for the network design problem that is based on user snapshots and contrast it with a new network design model based on the average coupling formulation. Exemplarily focusing on the important problem of optimizing antenna tilts, we give computational results for a fast local search algorithm and the application of a MIP solver to both models. These results demonstrate that our new average-based approaches outperform state-of-the-art snapshot models for UMTS radio network optimization.

Beschreibung: Constraint Programs and Mixed Integer Programs are closely related optimization problems originating from different scientific areas. Today's state-of-the-art algorithms of both fields have several strategies in common, in particular the branch-and-bound process to recursively divide the problem into smaller sub problems. On the other hand, the main techniques to process each sub problem are different, and it was observed that they have complementary strenghts. We propose a programming framework {\sffamily SCIP} that integrates techniques from both fields in order to exploit the strenghts of both, Constraint Programming and Mixed Integer Programming. In contrast to other proposals of recent years to combine both fields, {\sffamily SCIP} does not focus on easy implementation and rapid prototyping, but is tailored towards expert users in need of full, in-depth control and high performance.

Beschreibung: In this paper we describe the semantic analysis of differential equations given in the ubiquitous semi-structured formats MathML and OpenMath. The analysis is integrated in a deployed Web indexing framework. Starting from basic classifications for differential equations the proposed system architecture is amenable to extensions for further reconstruction of mathematical content on the Web. The syntactic analysis of mathematical formulae given in the considered formats must overcome ambiguities that stem from the fact that formula particles may have different encodings, which are in principle completely arbitrary. However, it turns out that the syntactic analysis can be done straightforward given some natural heuristic assumptions.

Beschreibung: A new method for noise removal of arbitrary surfaces meshes is presented which focuses on the preservation and sharpening of non-linear geometric features such as curved surface regions and feature lines. Our method uses a prescribed mean curvature flow (PMC) for simplicial surfaces which is based on three new contributions: 1. the definition and efficient calculation of a discrete shape operator and principal curvature properties on simplicial surfaces that is fully consistent with the well-known discrete mean curvature formula, 2. an anisotropic discrete mean curvature vector that combines the advantages of the mean curvature normal with the special anisotropic behaviour along feature lines of a surface, and 3. an anisotropic prescribed mean curvature flow which converges to surfaces with an estimated mean curvature distribution and with preserved non-linear features. Additionally, the PMC flow prevents boundary shrinkage at constrained and free boundary segments.

Beschreibung: A primal-dual interior point method for optimal control problems with PDE constraints is considered. The algorithm is directly applied to the infinite dimensional problem. Existence and convergence of the central path are analyzed. Numerical results from an inexact continuation method applied to a model problem are shown.

Beschreibung: Die in der Arbeitsgemeinschaft der Verbundsysteme zusammengeschlossenen deutschen Verbundsysteme kooperieren zur Realisierung eines die Länder und Verbundregionen übergreifenden offenen Netzwerkes einer offenen digitalen Bibliothek, dem Verteilten Dokumentenserver (VDS). Wesentliche Bestandteile des VDS sind die in den lokalen Bibliotheken und Verbundsystemen verteilten Dokumentenspeicher. Beim Aufbau des VDS verfolgen die deutschen Verbundsysteme für ihre digitalen Ressourcen, Zeitschriften und Dokumente, folgende Ziele [AGV03]: \begin{itemize} \item{Erhalt und dauerhafte Sicherung einmal erworbener Rechte} \item{Bessere Erschließung und Integration in das eigene Angebot} \item{Nahtlose Navigation in lokalen Zeitschriften- und Dokumentenservern und zwischen digitalen Artikeln und Zeitschriften, Dokumenten und Servern} \item{Dauerhafte Sicherung des Zugriffs und perspektivisch Langzeitverfügbarkeit} \end{itemize} Die Verbundsysteme streben an, die Speicherung, Erschließung und das Angebot ihrer digitalen Materialien in einer nationalen Kooperation durchzuführen. Sie entwickeln und betreiben zu diesem Zweck Portal- und Querschnittstechnologien zur Integration ihrer dezentral gespeicherten digitalen Ressourcen mittels Internet-Technologien.

Beschreibung: In this paper, we present a novel approach to the congestion control and resource allocation problem of elastic and real-time traffic in telecommunication networks. With the concept of utility functions, where each source uses a utility function to evaluate the benefit from achieving a transmission rate, we interpret the resource allocation problem as a global optimization problem. The solution to this problem is characterized by a new fairness criterion, \e{utility proportional fairness}. We argue that it is an application level performance measure, i.e. the utility that should be shared fairly among users. As a result of our analysis, we obtain congestion control laws at links and sources that are globally stable and provide a utility proportional fair resource allocation in equilibrium. We show that a utility proportional fair resource allocation also ensures utility max-min fairness for all users sharing a single path in the network. As a special case of our framework, we incorporate utility max-min fairness for the entire network. To implement our approach, neither per-flow state at the routers nor explicit feedback beside ECN (Explicit Congestion Notification) from the routers to the end-systems is required.

Beschreibung: Wie findet man den optimalen Weg im U-Bahnnetz? Das Problem wird als Graph modelliert und dann eine Breitensuche durchgeführt. Will man Weglängen oder Fahrzeiten mitberücksichtigen, so braucht man den Algorithmus von Dijkstra für gewichtige Graphen. Beim Nachdenken über diese Algorithmen werden auch Fragestellungen der Graphentheorie berührt. In einem zweiten Abschnitt werden methodische Hinweise für den Unterricht in der Sekundarstufe I und II gegeben, insbesondere, wie man Lernende dazu bringen kann, ihre Ideen für Algorithmen präzise zu analysieren und zu Papier zu bringen.

Beschreibung: The problem of clustering data can be formulated as a graph partitioning problem. Spectral methods for obtaining optimal solutions have reveceived a lot of attention recently. We describe Perron Cluster Cluster Analysis (PCCA) and, for the first time, establish a connection to spectral graph partitioning. We show that in our approach a clustering can be efficiently computed using a simple linear map of the eigenvector data. To deal with the prevalent problem of noisy and possibly overlapping data we introduce the min Chi indicator which helps in selecting the number of clusters and confirming the existence of a partition of the data. This gives a non-probabilistic alternative to statistical mixture-models. We close with showing favorable results on the analysis of gene expressi on data for two different cancer types.

Beschreibung: In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of the most promising formulation. In many cases, a non-zero lower bound on the number of required converters is generated this way. For several instances, we in fact prove optimality since the lower bound equals the best known solution value.

Beschreibung: Operative planning in gas distribution networks leads to large-scale mixed-integer optimization problems involving a hyperbolic PDE defined on a graph. We consider the NLP obtained under prescribed combinatorial decisions---or as relaxation in a branch and bound framework, addressing in particular the KKT systems arising in primal-dual interior methods. We propose a custom solution algorithm using sparse local projections, based on the KKT systems' structual properties induced by the discretized gas flow equations in combination with the underlying network topology. The numerical efficiency and accuracy of the algorithm are investigated, and detailed computational comparisons with a control space method and with the multifrontal solver MA27 are provided.

Beschreibung: The topic of this paper is minimum cost operative planning of pressurized water supply networks over a finite horizon and under reliable demand forecast. Since this is a very hard problem, it is desirable to employ sophisticated mathematical algorithms, which in turn calls for carefully designed models with suitable properties. The paper develops a nonlinear mixed integer model and a nonlinear programming model with favorable properties for gradient-based optimization methods, based on smooth component models for the network elements. In combination with further nonlinear programming techniques (to be reported elsewhere), practically satisfactory near-optimum solutions even for large networks can be generated in acceptable time using standard optimization software on a PC workstation. Such an optimization system is in operation at Berliner Wasserbetriebe.

Beschreibung: Im Rahmen von Problemstellungen der kombinatorischen Optimierung können Schülerinnen und Schüler lernen, Algorithmen selber zu entwickeln. Gleichzeitig lernen sie dabei moderne Mathematik in ihren Anwendungen kennen und erleben die Mathematik als lebendige Wissenschaft.

Beschreibung: Morse matchings capture the essential structural information of discrete Morse functions. We show that computing optimal Morse matchings is NP-hard and give an integer programming formulation for the problem. Then we present polyhedral results for the corresponding polytope and report on computational results.

Beschreibung: In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formula tion by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation approach. Computational experiments show that the value of the linear relaxation states a good lower bound and can often prove optimality of the best solution generated heuristically.

Beschreibung: The parameter contraction degeneracy -- the maximum minimum degree over all minors of a graph -- is a treewidth lower bound and was first defined in (Bodlaender, Koster, Wolle, 2004). In experiments it was shown that this lower bound improves upon other treewidth lower bounds. In this note, we examine some relationships between the contraction degeneracy and connected components of a graph, block s of a graph and the genus of a graph. We also look at chordal graphs, and we study an upper bound on the contraction degeneracy and another lower bound for treewidth. A data structure that can be used for algorithms computing the degeneracy and similar parameters, is also described.

Beschreibung: The Maximum Cardinality Search algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbors becomes visited. An MCS-ordering of a graph is an ordering of the vertices that can be generated by the Maximum Cardinality Search algorithm. The visited degree of a vertex $v$ in an MCS-ordering is the number of neighbors of $v$ that are before $v$ in the ordering. The visited degree of an MCS-ordering $\psi$ of $G$ is the maximum visited degree over all vertices $v$ in $\psi$. The maximum visited degree over all MCS-orderings of graph $G$ is called its {\em maximum visited degree}. Lucena (2003) showed that the treewidth of a graph $G$ is at least its maximum visited degree. We show that the maximum visited degree is of size $O(\log n)$ for planar graphs, and give examples of planar graphs $G$ with maximum visited degree $k$ with $O(k!)$ vertices, for all $k\in \Bbb{N}$. Given a graph $G$, it is NP-complete to determine if its maximum visited degree is at least $k$, for any fixed $k\geq 7$. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete. We also propose and experimentally analyses some heuristics for the problem. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.

Beschreibung: A new and time efficient model to evaluate the free energy of solvation has been developed. The solvation free energy is separated into an electrostatic term, a hydrogen bond term, and a rest-term, combining both entropic and van der Waals effects. The electrostatic contribution is evaluated with a simplified boundary element method using the partial charges of the MMFF94 force field. The number of hydrogen bonds and the solvent excluded surface area over the surface atoms are used in a linear model to estimate the non-electrostatic contribution. This model is applied to a set of 213 small and mostly organic molecules, yielding an rmsd of 0.87kcal/mol and a correlation with experimental data of r=0.951. The model is applied as a supplementary component of the free energy of binding to estimate binding constants of protein ligand complexes. The intermolecular interaction energy is evaluated by using the MMFF94 force field.

Beschreibung: In this paper we describe a new algorithm for multiple semi-flexible superpositioning of drug-sized molecules. The algorithm identifies structural similarities of two or more molecules. When comparing a set of molecules on the basis of their three-dimensional structures, one is faced with two main problems. (1) Molecular structures are not fixed but flexible, i.e., a molecule adopts different forms. To address this problem, we consider a set of conformers per molecule. As conformers we use representatives of conformational ensembles, generated by the program ZIBMol. (2) The degree of similarity may vary considerably among the molecules. This problem is addressed by searching for similar substructures present in arbitrary subsets of the given set of molecules. The algorithm requires to preselect a reference molecule. All molecules are compared to this reference molecule. For this pairwise comparison we use a two-step approach. Clique detection on the correspondence graph of the molecular structures is used to generate start transformations, which are then iteratively improved to compute large common substructures. The results of the pairwise comparisons are efficiently merged using binary matching trees. All common substructures that were found, whether they are common to all or only a few molecules, are ranked according to different criteria, such as number of molecules containing the substructure, size of substructure, and geometric fit. For evaluating the geometric fit, we extend a known scoring function by introducing weights which allow to favor potential pharmacophore points. Despite considering the full atomic information for identifying multiple structural similarities, our algorithm is quite fast. Thus it is well suited as an interactive tool for the exploration of structural similarities of drug-sized molecules.

Beschreibung: Molecular dynamics simulations of possible ligands for proteins yield large amounts of data in the form of trajectories which are further processed in order to find metastable conformations. These conformations can then be used for docking between ligand and protein. Around this core computation procedure lots of other data have to be managed. It should also be possible for external users not involved in program development to perform computations. As a paradigm for other fields where a similar constitution of program usage and data processing is found we present a software architecture for data generation, access and management. Requirements for this system include: Ease of use, graphical user interface, persistent storage of data concerning molecules, users, programs, program parameters, metadata, and results. A mere storage in the file system would render a quick overview of data more or less impossible. On the other hand, storing large amounts of binary data in a database doesn't yield any advantage concerning speed of access. Therefore, a hybrid approach combining file system and database is appropriate. The system should be easily extensible by inserting new applications which can be controlled and whose results can be collected and stored. The software system described here consists of different components, the presentation layer (graphical user interface), the business logic, the persistence layer (relational database plus file system), and an interface to the compute cluster (batch system for parallel processing). We will discuss the alternatives and take a closer look at the components.

Beschreibung: We propose an approach for transforming the sampling of a molecular conformation distribution into an analytical model based on Hidden Markov Models. The model describes the sampled shape density as a mixture of multivariate unimodal densities. Thus, it delivers an interpretation of the sampled density as a set of typical shapes that appear with different probabilities and are characterized by their geometry, their variability and transition probabilities between the shapes. The gained model is used to identify atom groups of constant shape that are connected by metastable torsion angles. Based on this description an alignment for the original sampling is computed. As it takes into account the different shapes contained in the sampled set, this alignment allows to compute reasonable average shapes and meaningful shape density plots. Furthermore, it enables us to visualize typical conformations.

Beschreibung: We present publicly available data sets related to research on wireless networks. The scenarios contain a wide range of data and are detailed in all aspects. To our knowledge, this is the most realistic, comprehensive, and detailed \emph{public} data collection on mobile networking. We indicate example uses of this data collection in applications related tu UMTS.

Beschreibung: The \emph{line planning problem} is one of the fundamental problems in strategic planning of public and rail transport. It consists of finding lines and corresponding frequencies in a public transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize its operating cost; the passengers request short travel times. We propose two new multi-commodity flow models for line planning. Their main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically.

Beschreibung: The aim of this paper is to give a survey of the known results concerning centrally symmetric polytopes, spheres, and manifolds. We further enumerate nearly neighborly centrally symmetric spheres and centrally symmetric products of spheres with dihedral or cyclic symmetry on few vertices, and we present an infinite series of vertex-transitive nearly neighborly centrally symmetric 3-spheres.

Beschreibung: We focus on the role of anisotropic elasticity in the simulation of the load distribution in a human mandible due to a lateral bite on the leftmost premolar. Based on experimental evidence, we adopt ``local''" orthotropy of the elastic properties of the bone tissue. Since the trajectories of anisotropic elasticity are not accessible from Computer Tomographic (CT) data, they will be reconstructed from (i) the organ's geometry and (ii) from coherent structures which can be recognized from the spatial distribution of the CT values. A sensitivity analysis comprising various 3D FE simulations reveals the relevance of elastic anisotropy for the load carrying behavior of a human mandible: Comparison of the load distributions in isotropic and anisotropic simulations indicates that anisotropy seems to ``spare''" the mandible from loading. Moreover, a maximum degree of anisotropy leads to kind of an load minimization of the mandible, expressed by a minimum of different norms of local strain, evaluated throughout the organ. Thus, we may suggest that anisotropy is not only relevant, but also in some sense ``optimal''.

Beschreibung: The paper extends affine conjugate Newton methods from convex to nonconvex minimization, with particular emphasis on PDE problems originating from compressible hyperelasticity. Based on well-known schemes from finite dimensional nonlinear optimization, three different algorithmic variants are worked out in a function space setting, which permits an adaptive multilevel finite element implementation. These algorithms are tested on two well-known 3D test problems and a real-life example from surgical operation planning.

Beschreibung: We present formulae for the corner points of the multidimensional Hausdorff and Dale Polytopes and show how these results can be used to improve linear programming models for computing e.\,g.\ moments of exit distribution of diffusion processes. Specifically, we compute the mean exit time of twodimensional Brownian motion from the unit square and the unit triangle, as well as higher moments of the exit time of time space Brownian motion from a triangle.

Beschreibung: Normal graphs are defined in terms of cross-intersecting set families: a graph is normal if it admits a clique cover $\cal Q$ and a stable set cover $\cal S$ s.t.~every clique in $\cal Q$ intersects every stable set in $\cal S$. Normal graphs can be considered as closure of perfect graphs by means of co-normal products (Körner 1973) and graph entropy (Czisz\'ar et al. 1990). Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs (Strong Perfect Graph Theorem, Chudnovsky et al. 2002). Körner and de Simone observed that $C_5$, $C_7$, and $\overline C_7$ are minimal not normal and conjectured, as generalization of the Strong Perfect Graph Theorem, that every $C_5$, $C_7$, $\overline C_7$- free graph is normal (Normal Graph Conjecture, Körner and de Simone 1999). We prove this conjecture for a first class of graphs that generalize both odd holes and odd antiholes, the circulants, by characterizing all the normal circulants.

Beschreibung: It is known that the suspension of a simplicial complex can be realized with only one additional point. Suitable iterations of this construction generate highly symmetric simplicial complexes with a various interesting combinatorial and topological properties. In particular, infinitely many non-PL spheres as well as contactible simplicial complexes with a vertex-transitive group of automorphisms cab be contained in this way.

Beschreibung: This paper presents an automatic approach for segmentation of the liver from computer tomography (CT) images based on a 3D statistical shape model. Segmentation of the liver is an important prerequisite in liver surgery planning. One of the major challenges in building a 3D shape model from a training set of segmented instances of an object is the determination of the correspondence between different surfaces. We propose to use a geometric approach that is based on minimizing the distortion of the correspondence mapping between two different surfaces. For the adaption of the shape model to the image data a profile model based on the grey value appearance of the liver and its surrounding tissues in contrast enhanced CT data was developed. The robustness of this method results from a previous nonlinear diffusion filtering of the image data. Special focus is turned to the quantitative evaluation of the segmentation process. Several different error measures are discussed and implemented in a study involving more than 30 livers.

Beschreibung: Mixed integer programs are commonly solved with linear programming based branch-and-bound algorithms. The success of the algorithm strongly depends on the strategy used to select the variable to branch on. We present a new generalization called {\sl reliability branching} of today's state-of-the-art {\sl strong branching} and {\sl pseudocost branching} strategies for linear programming based branch-and-bound algorithms. After reviewing commonly used branching strategies and performing extensive computational studies we compare different parameter settings and show the superiority of our proposed newstrategy.

Beschreibung: This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction.

Beschreibung: Structural mechanics simulation of bony organs is of general medical and biomechanical interest, because of the interdependence of the inner architecture of bone and its functional loading already stated by Wolff in 1892. This work is part of a detailed research project concerning the human mandible. By adaptive finite element techniques, stress/strain profiles occurring in the bony structure under biting were simulated. Estimates of the discretization errors, local grid refinement, and multilevel techniques guarantee the reliability and efficiency of the method. In general, our simulation requires a representation of the organ's geometry, an appropriate material description, and the load case due to teeth, muscle, or joint forces. In this paper, we want to focus on the influence of the masticatory system. Our goal is to capture the physiological situation as far as possible. By means of visualization techniques developed by the group, we are able to extract individual muscle fibres from computed tomography data. By a special algorithm, the fibres are expanded to fanlike (esp. for the musc. temporalis) coherent vector fields similar to the anatomical reality. The activity of the fibres can be adapted according to compartmentalisation of the muscles as measured by electromyological experiments. A refined sensitivity analysis proved remarkable impact of the presented approach on the simulation results.

Beschreibung: Operative planning in gas networks with prescribed binary decisions yields large scale nonlinear programs defined on graphs. We study the structure of the KKT systems arising in interior methods and present a customized direct solution algorithm. Computational results indicate that the algorithm is suitable for optimization in small and medium-sized gas networks.

Beschreibung: Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) verzichtet auf eine einheitliche zentrale Verbunddatenbank zugunsten einer dezentralen, verteilten Struktur. In dieser Architektur erhält die Art der Indexierung der angesprochenen Online-Kataloge eine besondere Bedeutung. So werden sowohl Bibliotheksmitarbeiter als auch Bibliotheksbenutzer immer wieder mit der Recherche in fremden Katalogen konfrontiert, in denen unterschiedliche Indexierungsverfahren realisiert sein können. Ein abgestimmtes Indexierungskonzept verfolgt zwei grundsätzliche Ziele. Einerseits soll durch eine vereinheitlichte Indexierung die Qualität und Zuverlässigkeit der Rechercheergebnisse in der parallelen Suche in mehreren Katalogen über die KOBV-Suchmaschine erhöht werden. Gleichzeitig soll durch eine vereinheitlichte Indexierung die Akzeptanz von Suchen in entfernten Katalogen prinzipiell gesteigert und damit die Bedingungen für die gegenseitige Übernahme von Titeldaten erleichtert werden. Für die Indexierung muss zunächst die Art und der Umfang der im OPAC aufzubauenden Indices festgelegt werden. Aus Sicht des Nutzers entspricht diese Definition den möglichen Sucheinstiegen. Hat man dann entschieden, welche Indexterme aus welchen Feldern in die jeweiligen Indices einfließen sollen, muss bestimmt werden, nach welchen Regeln die Terme behandelt werden. Hier stellt sich insbesondere das Problem der Sonderzeichen wie Bindestriche, Apostrophe und Punkte oder Ziffern in Zeichenketten. Das vorliegende Konzept entstand in Zusammenarbeit der großen Universitätsbibliotheken in Berlin (der Freien Universität, der Humboldt-Universität, der Technischen Universität, der Universität der Künste) mit der KOBV-Verbundzentrale am ZIB.

Beschreibung: We investigate a special class of quadratic Hamiltonians on $so(4)$ and $so(3,1)$ and describe Hamiltonians that have additional polynomial integrals. One of the main results is a new integrable case with an integral of sixth degree.

Beschreibung: We present a graph theoretical model for scheduling trains on a single unidirectional track between two stations. The set of departures of all possible train types at all possible (discrete) points of time is turned into an undirected graph $\Gneu$ by joining two nodes if the corresponding departures are in conflict. This graph $\Gneu$ has no odd antiholes and no $k$-holes for any integer $k\geq 5$. In particular, any finite, node induced subgraph of $\Gneu$ is perfect. For any integer $r\geq 2$ we construct minimal headways for $r$ train types so that the resulting graph $\Gneu$ has $2r$-antiholes and $4$-holes at the same time. Hence, $\Gneu$ is neither a chordal graph nor the complement of a chordal graph, in general. At the end we analyse the maximal cliques in $G$.

Beschreibung: Unnecessarily conservative behavior of standard process control techniques can be avoided by stochastic programming models when the distribution of random disturbances is known. In an earlier study we have investigated such an approach for tank level constraints of a distillation process. Here we address techniques that have accelerated the numerical solution of the large and expensive stochastic programs by a factor of six, and then present a refined optimization model for the same application.

Beschreibung: We investigate the impact of hop-limited routing paths on the total cost of a telecommunication network. For different survivability settings (dedicated protection, link and path restoration), the optimal network cost without restrictions on the admissible path set is compared to the results obtained with two strategies to impose hop limits on routing paths. In a thorough computational study on optimal solutions for nine real-world based problem instances, we show that hop limits should be avoided if the technology allows it and network cost is a major planning issue. In this case, column generation should be employed to deal with all routing paths. If hop-limits are required, these should be defined for each demand individually and as large as possible.

Beschreibung: Under high load, the automated dispatching of service vehicles for the German Automobile Association (ADAC) must reoptimize a dispatch for 100--150 vehicles and 400 requests in about ten seconds to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within ten seconds. One way-out are simplified reoptimization models. These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new model ZIBDIP{\footnotesize dummy} can keep up with ZIBDIP.

Beschreibung: Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the minimum degree. The degeneracy is polynomial time computable. We introduce the notion of contraction degeneracy: the maximum over all minors of the minimum degree. We show that the contraction degeneracy problem is NP-complete, even for bipartite graphs, but for fixed $k$, it is polynomial time decidable if a given graph $G$ has contraction degeneracy at least $k$. Heuristics for computing the contraction degeneracy are proposed and evaluated. It is shown that these can lead in practice to considerable improvements of the lower bound for treewidth, but can perform arbitrarily bad on some examples. A study is also made for the combination of contraction with Lucena's lower bound based on Maximum Cardinality Search (Lucena, 2003). Finally, heuristics for the treewidth are proposed and! evaluated that combine contraction with a treewidth lower bound technique by Clautiaux et al (2003).

Beschreibung: \documentclass[12pt]{article} \usepackage{german} \parindent=0pt \begin{document} Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) hat in den Jahren 2001 bis 2003 im Rahmen des Entwicklungsprojektes ''KOBV-Informationsportal`` ein regionales Portal aufgebaut, in dem integrierte Informationsdienste fr die regionalen Bibliotheken zur Verfügung gestellt werden. Das ''KOBV-Portal - Digitale Bibliothek Berlin-Brandenburg`` wurde im Dezember 2003 in Betrieb genommen. Das KOBV-Portal bietet in seiner ersten Ausbaustufe den Nachweis über die in den großen Bibliotheken lizenzierten Ressourcen und elektronischen Zeitschriften, zudem die nahtlose Navigation mittels des Reference-Linking-Werkzeuges SFX zu verschiedenen Diensten wie Fernleihe, Subito und freien Volltexten im Internet sowie zu frei zugänglichen elektronischen Zeitschriften. Realisiert wurden ferner die Remote-Authentifizierung, mit der sich ein Nutzer, der online eine Fernleih-Bestellung aufgeben möchte, über das Internet in seiner Heimatbibliothek authentifizieren kann. Des weiteren ist der Zugriff auf lizenzierte Bestände im Campus einer Hochschule mittels IP-Checking möglich. Als weiteren wesentlichen Bestandteil des KOBV-Portals hat die KOBV-Zentrale mit den Bibliotheken einen Workflow für ein Metadata-Sharing abgestimmt und für die Adaption und Normalisierung lokaler Metadaten aus lokalen Bibliothekssystemen und -Portalen den KOBV-Metadaten-Austausch-Parser (KMA-Parser) entwickelt. Damit Bibliotheken, deren Metadaten bislang lediglich in unstrukturierter Form vorliegen, strukturierte Metadaten anlegen, liefern und nachnutzen können, hat die KOBV-Zentrale das mit einer Web-Katalogisierungsschnittstelle ausgestattete ''Metadata-Tool`` entwickelt. Die für das Metadata-Sharing entwickelten Komponenten und Module sollen den Bibliotheken die Mehrfacherfassung ersparen und ihnen die Möglichkeit der wechselseitigen Nachnutzung der Metadaten eröffnen. Der vorliegende Projekt-Abschlussbericht gibt einen Überblick über die während der Projektlaufzeit realisierten Dienste des KOBV-Portals. \end{document}

Beschreibung: Kürzeste Wege tauchen fast überall im Alltag auf. Daher eignet sich dieses Optimierungsproblem gut für den Unterricht. Modellierung und heuristische Vorgehensweisen werden geübt, um schließlich die klassischen kürzesten Wege-Algorithmen selbst zu erfinden. In diesem Artikel werden die Inhalte vorgestellt und konkrete Hinweise zum Unterricht in der Schule gegeben.

Beschreibung: A primal interior point method for control constrained optimal control problems with PDE constraints is considered. Pointwise elimination of the control leads to a homotopy in the remaining state and dual variables, which is addressed by a short step pathfollowing method. The algorithm is applied to the continuous, infinite dimensional problem, where discretization is performed only in the innermost loop when solving linear equations. The a priori elimination of the least regular control permits to obtain the required accuracy with comparable coarse meshes. Convergence of the method and discretization errors are studied, and the method is illustrated at two numerical examples.

Beschreibung: In this article, strategical infrastructure planning problems in the design of large-scale telecommunication networks are discussed based on experiences from three projects with industrial partners: The access network planning of the German Gigabit-Wissenschaftsnetz (G-WiN) for DFN (Verein zur Förderung eines Deutschen Forschungsnetzes e.V.), the mobile network switching center location planning project for E-Plus Mobilfunk, and the fixed network switching center location planning project for TELEKOM AUSTRIA. We introduce a mathematical model for a hierarchical multi-commodity capacitated facility location problem, present adaptions of this basic model to the specific requirements within the different projects and discuss the individual peculiarities and model decisions made. Eventually, we present and discuss computational results of three associated case studies, illustrating '"how we did the job`` with mathematical methods.

Beschreibung: Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving treewidth lower bounds. In this paper, we investigate a total of nine graph parameters, providing lower bounds for treewidth. The parameters have in common that they all are the vertex-degree of some vertex in a subgra ph or minor of the input graph. We show relations between these graph parameters and study their computational complexity. To allow a practical comparison of the bounds, we developed heuristic algorithms for those parameters that are NP-hard to compute. Computational experiments show that combining the treewidth lower bounds with minors can considerably improve the lower bounds.

Beschreibung: The paper addresses primal interior point method for state constrained PDE optimal control problems. By a Lavrentiev regularization, the state constraint is transformed to a mixed control-state constraint with bounded Lagrange multiplier. Existence and convergence of the central path are established, and linear convergence of a short-step pathfollowing method is shown. The behaviour of the regularizations are demonstrated by numerical examples.

Beschreibung: In [7,8,12] homogenization techniques are applied to derive an anisotropic variant of the bio-heat transfer equation as asymptotic result of boundary value problems providing a microscopic description for microvascular tissue. In view of a future application on treatment planning in hyperthermia, we investigate here the homogenization limit for a coupling model, which takes additionally into account the influence of convective heat transfer in medium size blood vessels. This leads to second order elliptic boundary value problems with nonlocal boundary conditions on parts of the boundary. Moreover, we present asymptotic estimates for first order correctors.

Beschreibung: Our main result is that every $n$-dimensional polytope can be described by at most $2n-1$ polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an $n$-dimensional pointed polyhedral cone we prove the bound $2n-2$ and for arbitrary polyhedra we get a constructible representation by $2n$ polynomial inequalities.

Beschreibung: Das KOBV-Metadaten-Schema ist von der KOBV-Zentrale entwickelt worden, um Ressourcen im Sinn von Informationskollektionen wie Datenbanken oder Fachportale zu beschreiben. Es ist ein wichtiger Bestandteil des KOBV-Portals, das die in der Region verf"ugbaren Ressourcen nachweist. Das KOBV-Metadaten-Schema dient den Bibliotheken zur Handreichung, um dem KOBV-Portal die Ressourcen mit den standardisierten und individuellen Angaben zu melden, so dass die Ressourcebeschreibungen einem austauschbaren Format entsprechen. Auf diese Weise k"onnen Ressourcebeschreibungen von anderen Bibliotheken mitgenutzt werden und ein Metadata-Sharing in der Region Berlin-Brandenburg praktiziert werden, um in diesem Bereich doppelte Arbeiten zu sparen.

Beschreibung: An edge of a perfect graph $G$ is critical if $G-e$ is imperfect. We would like to decide whether $G - e$ is still {\sl almost perfect} or already {\sl very imperfect}. Via relaxations of the stable set polytope of a graph, we define two superclasses of perfect graphs: rank-perfect and weakly rank-perfect graphs. Membership in those two classes indicates how far an imperfect graph is away from being perfect. We study the cases, when a critical edge is removed from the line graph of a bipartite graph or from the complement of such a graph.

Beschreibung: Collection of abstracts of the first SIAM-EMS conference Applied Mathematics in our Changing World'' in Berlin, September 2-6, 2001.

Beschreibung: {\sc Zimpl} is a little language to translate the mathematical model of a problem into a linear or (mixed-)integer mathematical program expressed in {\tt lp} or {\tt mps} file format which can be read by a LP or MIP solver.

Beschreibung: Im ersten Teil des folgenden Aufsatzes werden allgemeine Überlegungen zur Entwicklung von Bibliotheken hin zu Informationsvermittlungsstellen für sowohl elektronische wie auch gedruckte Medien angestellt. Basierend auf den Ergebnissen der Evaluation digitaler Bibliotheken und Informationsportale in Deutschland wird ein erster Kriterienkatalog für ein Verbund-Informationsportal für den Kooperativen Bibliotheksverbund Berlin-Brandenburg entwickelt. Im Anhang befindet sich der Statusbericht über Informationsportale und digitale Bibliotheken in Deutschland. Dazu wurden sieben digitale Bibliotheken auf Verbundebene und 21 Bibliotheken nach Bundesländern evaluiert.

Beschreibung: Given a set of service requests (events), a set of guided servers (units), and a set of unguided service contractors (conts), the vehicle dispatching problem {\sl vdp} is the task to find an assignment of events to units and conts as well as tours for all units starting at their current positions and ending at their home positions (dispatch) such that the total cost of the dispatch is minimized. The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit costs consist of driving costs, service costs and overtime costs; cont costs consist of a fixed cost per service; event costs consist of late costs linear in the late time, which occur whenever the service of the event starts later than its deadline. The program \textsf{ZIBDIP} based on dynamic column generation and set partitioning yields solutions on heavy-load real-world instances (215 events, 95 units) in less than a minute that are no worse than 1\% from optimum on state-of-the-art personal computers.

Beschreibung: Scenario tree models of stochastic programs arise naturally under standard nonanticipativity assumptions. We demonstrate how tree-sparse programs cover the general case, with \emph{arbitrary} information constraints. Detailed examples and intuitive interpretations illuminate the basic thoughts behind the abstract but elementary construction.

Beschreibung: In this paper we present an algorithm that accelerates 3D texture-based volume rendering of large and sparse data sets. A hierarchical data structure (known as AMR tree) consisting of nested uniform grids is employed in order to efficiently encode regions of interest. The hierarchies resulting from this kind of space partitioning yield a good balance between the amount of volume to render and the number of texture bricks -- a prerequisite for fast rendering. Comparing our approach to an octree based algorithm we show that our algorithm increases rendering performance significantly for sparse data. A further advantage is that less parameter tuning is necessary.

Beschreibung: Mathematical optimization techniques are on their way to becoming a standard tool in chemical process engineering. While such approaches are usually based on deterministic models, uncertainties such as external disturbances play a significant role in many real-life applications. The present article gives an introduction to practical issues of process operation and to basic mathematical concepts required for the explicit treatment of uncertainties by stochastic optimization.

Beschreibung: Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. UCMC aims at avoiding the typical metastable or trapping 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. Therefore, the state space of the chain has to be hierarchically decomposed into its metastable conformations. This is done by means of combining the technique of conformation analysis as recently introduced by the authors, and appropriate annealing strategies. We present a detailed examination of the uncoupling-coupling procedure which uncovers its theoretical background, and illustrates the hierarchical algorithmic approach. Furthermore, application of the UCMC algorithm to the $n$-pentane molecule allows us to discuss the effect of its crucial steps in a typical molecular scenario.

Beschreibung: Standard model predictive control for real-time operation of industrial production processes may be inefficient in the presence of substantial uncertainties. To avoid overly conservative disturbance corrections while ensuring safe operation, random influences should be taken into account explicitly. We propose a multistage stochastic programming approach within the model predictive control framework and apply it to a distillation process with a feed tank buffering external sources. A preliminary comparison to a probabilistic constraints approach is given and first computational results for the distillation process are presented.

Beschreibung: Dynamic stochastic programs are prototypical for optimization problems with an inherent tree structure inducing characteristic sparsity patterns in the KKT systems of interior methods. We propose an integrated modeling and solution approach for such tree-sparse programs. Three closely related natural formulations are theoretically analyzed from a control-theoretic viewpoint and compared to each other. Associated KKT solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.

Beschreibung: We introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly enviroment. The bin coloring problem is to pack unit size colored items into bins, such that the maximum number of different colors per bin is minimized. Each bin has size~$B\in\mathbb{N}$. The packing process is subject to the constraint that at any moment in time at most $q\in\mathbb{N}$ bins may be partially filled. Moreover, bins may only be closed if they are filled completely. An online algorithm must pack each item must be packed without knowledge of any future items. We investigate the existence of competitive online algorithms for the online uniform binpacking problem. We show upper bounds for the bin coloring problem. We prove an upper bound of $3q$ - 1 and a lower bound of $2q$ for the competitive ratio of a natural greedy-type algorithm, and show that surprisingly a trivial algorithm which uses only one open bin has a strictly better competitive ratio of $2q$ - 1. Morever, we show that any deterministic algorithm has a competitive ratio $\Omega (q)$ and that randomization does not improve this lower bound even when the adversary is oblivious.

Beschreibung: In circuit switching networks call streams are characterized by their mean and peakedness (two-moment method). The $GI/M/C/0$ system is used to model a single link, where the $GI$-stream is determined by fitting moments appropriately. For the moments of the overflow traffic of a $GI/M/C/0$ system there are efficient numerical algorithms available. However, for the moments of the freed carried traffic, defined as the moments of a virtual link of infinite capacity to which the process of calls accepted by the link (carried arrival process) is virtually directed and where the virtual calls get fresh exponential i.i.d.\ holding times, only complex numerical algorithms are available. This is the reason why the concept of the freed carried traffic is not used rigorously. The main result of this paper is an efficient algorithm for computing the moments of the freed carried traffic, in particular an explicit formula for its peakedness. This result offers a unified handling of both overflow and carried traffics in networks. Furthermore, some refined characteristics for the overflow and freed carried streams are derived.

Beschreibung: In this work we concentrate on developing methods which determine good lower bounds for set partitioning problems (SPP) in an appropriate amount of time. We found out that it makes sense to use the Lagrangian relaxation method for this task. The Lagrangian relaxed problem of SPP has a simple structure, which leads to algorithms and heuristics, whose total complexity per iteration depends linearly on the number of non-zeros of the problem matrix of SPP. In contrast, other methods like simplex methods or interior point methods have a complexity of higher order. Because the problem matrices of our tested instances are sparse, the linear dependence becomes an advantage for the algorithms and heuristics mentioned above. As a reference for the state-of-the-art we have applied the dual simplex method and the barrier function method, implemented in CPLEX. The methods, which we have developed and compared with those of CPLEX, are SBM, CAM, CCBM, and CBM. SBM is a subgradient bundle method derived from the basic subgradient method, which is a global convergent method for determining the maximum of concave functions. CAM is a coordinate ascent method, where the convex coordinate bundle method CCBM and the coordinate bundle method CBM are derivatives from CAM. We observed that the basic subgradient and the coordinate ascent method are improved if bundling techniques can be used. But the motivation for bundling differs for both approaches. In the former case bundling helps to approximate a minimum norm subgradient, which provides a steepest ascent direction, in order to speed up the performance. In the latter case bundling enables proceeding along directions, which are not restricted on the coordinate directions. By this the performance is accelerated. Among all used techniques stabilization is worth mentioning. Stabilization improves the performance especially at the beginning by avoiding too big steps during the proceeding. This leads to a more stabilized progression. Stabilization was successfully applied to SBM, CAM, CCBM, and CBM. As an overall result we conclude the following: \begin{enumerate} \item CPLEX computes the optimal objective values, whereas SBM and CBM has on average a gap of under $1.5\%$. \item In comparison to CPLEX baropt, SBM, CAM, and CBM the algorithm CCBM has a slow convergence because of the convex combination of ascent coordinate directions. An alternative is to relax the convex combination to a simple sum of the corresponding directions. This idea is realized in CBM. \item If we focus on the running time rather than on optimality then CBM is on average the fastest algorithm. \end{enumerate} Note that methods like SBM or CBM are applied on static SPP instances in order to determine a good lower bound. For solving SPP we need dynamical methods. Due to the complex topic of dynamical methods we will not discuss them, but a certain technique is worth mentioning. It is called column generation. We have indicated that this technique needs good Lagrangian multipliers of the corresponding SPP instances in order to generate further columns (in our case duties), which are added to the current SPP instance. Those multipliers are by-products of methods like our six considered methods. Due to the large number of such generation steps the running time depends on the computation time of these methods. Therefore, CBM fits more to this technique than CPLEX baropt or SBM. To sum it up it can be said that applications such as a duty scheduling can be described as set partitioning problems, whose lower bound can be solved by simplex, interior points, subgradient, or coordinate ascent methods. It turns out that the interior points method CPLEX baropt and the heuristic CBM have good performances. Furthermore, good Lagrangian multipliers, which are by-products of these methods, can be used by techniques like column generation. For this particular technique it also turns out that among our tested algorithms CBM is the most efficient one. In general we can state that real-world applications, which have to solve a large number of Lagrangian relaxed SPP instances can improve their performance by using CBM.

Beschreibung: The success of large-scale multi-national projects like the forthcoming analysis of the LHC particle collision data at CERN relies to a great extent on the ability to efficiently utilize computing a management software (Datagrid, Globus, etc.), while the effective integration of computing nodes has been largely neglected up to now. This is the focus of our work. We present a framework for a high-performance cluster that can be used as a reliable computing node in the Grid. We outline the cluster architecture, the management of distributed data and the seamless intergration of the cluster into the Grid environment.

Beschreibung: Der Aufsatz ist die ausgearbeitete Fassung eines Vortrages, gehalten am 05.04.2001 auf dem 91. Deutschen Bibliothekartag in Bielefeld. Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) ist im Rahmen eines wissenschaftlichen Projektes in den Jahren 1997 bis 2000 am Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) aufgebaut worden. Nachdem das Projekt erfolgreich abgeschlossen ist, wird der KOBV 2001 institutionalisiert. In dem Vortrag hat die Verfasserin einen Überblick über das bisher Erreichte, den derzeitigen Stand und die Perspektiven des neuen Verbundes gegeben. Der KOBV stellt eine neue Art von Bibliotheksverbund dar. Sein technisches Konzept und sein organisatorischer Aufbau basieren auf der {\sl Internetphilosophie}. Den informationstechnischen Kern bildet eine Suchmaschine, die die heterogenen lokalen Bibliothekssysteme miteinander verbindet. Die KOBV-Organisation ist dezentral. Sie wird getragen von der Kooperation der Bibliotheken in Berlin und Brandenburg. Eine kleine Verbundzentrale koordiniert dieses Geflecht vernetzter lokaler Einheiten, vertritt den KOBV nach außen und arbeitet - in Form von Projekten - an seiner Weiterentwicklung. Der Entwicklungsaspekt und die Nutzerorientierung sind zwei wesentliche Komponenten in der Verbundarbeit. Berlin und Brandenburg haben auf engem Raum zahlreiche Bibliotheken mit großen, reichhaltigen Medienbeständen. Mittel- bis langfristig sollen Bibliotheken aller Sparten und Größen in den KOBV integriert werden, seien es wissenschaftliche Universalbibliotheken, universitäre Bibliothekssysteme, Spezialbibliotheken, Behörden- und Parlamentsbibliotheken oder öffentliche Bibliotheken. Auch regionale Bibliotheksverbünde können als Subverbünde am KOBV teilnehmen. Mit der KOBV-Suchmaschine ist eine offene Plattform geschaffen worden, auf der weitere Entwicklungen aufsetzen können. Der Aufbau einer virtuellen Regionalbibliothek mit Bestell- und Lieferkomponenten ist eines der Ziele. Darüber hinaus ist es die Vision, in der Region ein virtuelles {\sl Wissensportal} aufzubauen, das dem Nutzer unter einer Adresse den umfassenden Zugang und die umfassende Bereitstellung von Informationen aller Art bietet.

Beschreibung: A new approach to the numerical solution of optimal control problems including control and state constraints is presented. Like hybrid methods, the approach aims at combining the advantages of direct and indirect methods. Unlike hybrid methods, however, our method is directly based on interior-point concepts in function space --- realized via an adaptive multilevel scheme applied to the complementarity formulation and numerical continuation along the central path. Existence of the central path and its continuation towards the solution point is analyzed in some theoretical detail. An adaptive stepsize control with respect to the duality gap parameter is worked out in the framework of affine invariant inexact Newton methods. Finally, the performance of a first version of our new type of algorithm is documented by the successful treatment of the well-known intricate windshear problem.

Beschreibung: Das \emph{Committee on Electronic Information and Communication} (CEIC) der \emph{International Mathematical Union} (IMU) hat die Aufgabe, sich über die langfristige Informationsversorgung in der Mathematik Gedanken zu machen und Lösungsvorschläge hierfür zu erarbeiten. Das Kernthema ist natürlich "`Elektronisches Publizieren"'. Dazu gehören auch Copyright-Regelungen. % Sie sind -- % neben einer Andeutung der weiteren CEIC-Pläne -- der Fokus dieses % kurzen Artikels. Er schließt mit einem von der IMU verabschiedeten % Aufruf zu vernünftigem Verhalten bei Copyright-Vereinbarungen. Eine % nachhaltige Befolgung dieses Aufrufs -- verbunden mit weiteren % Aktivitäten -- könnte die (derzeit kaum noch bezahlbare und % dadurch gefährdete) Literaturversorgung nachhaltig zum Positiven % verändern. Mit diesem Artikel beginnt eine kleine Serie von Aufsätzen, in denen ich (in meiner Funktion als eines von elf CEIC-Mitgliedern) die Empfehlungen des CEIC erläutern werde. % Das heutige Thema sind die % CEIC-Vorschläge zum Copyright

Beschreibung: By computed tomography data (CT), the individual geometry of the mandible is quite well reproduced, also the separation between cortical and trabecular bone. Using anatomical knowledge about the architecture and the functional potential of the masticatory muscles, realistic situations were approximated. The solution of the underlying partial differential equations describing linear elastic material behaviour is provided by an adaptive finite element method. Estimations of the discretization error, local grid refinement, and multilevel techniques guarantee the reliability and efficiency of the method.

Beschreibung: Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when decisions have to be made before all data of the problem are known. And we speak of a real-time online problem when online decisions have to be computed within very tight time bounds. This paper surveys the are of combinatorial online and real-time optimization, it discusses, in particular, the concepts with which online and real-time algorithms can be analyzed.

Beschreibung: This paper describes a new simulation tool for the prediction of aerosol formation and behavior in gas--liquid contact devices such as absorbers, scrubbers, quench coolers, and condensers as well as multistage gas cleaning processes, respectively. Aerosol formation can impact severely the separation efficiency of gas cleaning processes. Aerosol or fog formation can arise by spontaneous condensation or desublimation in supersaturated gas phases. The rigorous description of the mass and energy transfer between the gas phase, the liquid phase, and the growing aerosol droplets leads to a system of partial differential and algebraic equations. For the solution of these systems we have developed the plant simulation tool AerCoDe. This program bases upon the linearly--implicit Euler discretisation, which in combination with extrapolation permits an adaptive step size and order control. Typical simulation results of a multistage industrial flue gas scrubbing process are presented. It is shown, that experimental data can be confirmed if the number concentration of condensation nuclei as an input parameter is roughly known.

Beschreibung: This paper discusses online optimization of real-world transportation systems. We concentrate on transportation problems arising in production and manufacturing processes, in particular in company internal logistics. We describe basic techniques to design online optimization algorithms for such systems, but our main focus is decision support for the planner: which online algorithm is the most appropriate one in a particular setting? We show by means of several examples that traditional methods for the evaluation of online algorithms often do not suffice to judge the strengths and weaknesses of online algorithms. We present modifications of well-known evaluation techniques and some new methods, and we argue that the selection of an online algorithm to be employed in practice should be based on a sound combination of several theoretical and practical evaluation criteria, including simulation.

Beschreibung: Wireless communication networks employ radio frequencies to establish communication links. The available radio spectrum is very limited. To meet today's radio communication demand, this resource has to be administered and reused carefully in order to control mutual interference. The reuse can be organized via separation in space, time, or frequency, for example. The problem, therefore, arises to distribute frequencies to links in a ``reasonable manner''. This is the basic form of the frequency assignment problem. What ``reasonable'' means, how to quantify this measure of quality, which technical side constraints to consider cannot be answered in general. The exact specification of this task and its mathematical model depend heavily on the particular application considered. In this paper we discuss this issue with respect to the GSM standard for mobile communication.

Beschreibung: This paper is a summary of the Round Table: ``The Impact of Mathematical Research on Industry and Vice Versa'' held at 3ecm in Barcelona on July 11, 2000. The round table started with contributions of the three panelists. Irene Fonseca, the panel chair, opened the discussion by stating six questions addressing the main issues of the round table topic. She presented the panel's answers to these questions, drawing on many examples from her own academic experience. In the following additional presentations, the other two panel members added further points of view based on their personal involvement with industry. The round table ended with a lively discussion with members from the audience. This written summary of the oral presentations follows the structure of the round table indicated above.

Beschreibung: This article is about \emph{adaptive column generation techniques} for the solution of duty scheduling problems in public transit. The current optimization status is exploited in an adaptive approach to guide the subroutines for duty generation, LP resolution, and schedule construction toward relevant parts of a large problem. Computational results for three European scenarios are reported.

Beschreibung: The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges to the optimal solution under reasonable assumptions on the separation oracle and the feasible set. We have implemented a practical variant of the cutting plane algorithm for improving semidefinite relaxations of constrained quadratic 0-1 programming problems by odd-cycle inequalities. We also consider separating odd-cycle inequalities with respect to a larger support than given by the cost matrix and present a heuristic for selecting this support. Our preliminary computational results for max-cut instances on toroidal grid graphs and balanced bisection instances indicate that warm start is highly efficient and that enlarging the support may sometimes improve the quality of relaxations considerably.

Beschreibung: Der Wissenschaftsrat hat in seiner Juli-Sitzung 2001 \glqq Empfehlungen zur digitalen Informationsversorgung durch Hochschulbibliotheken \grqq verabschiedet. Einige der Vorschläge des Wissenschaftsrates können, falls sie von den angesprochenen Institutionen aufgenommen werden, zu einer nachhaltigen Veränderung der wissenschaftlichen Informationslandschaft führen. In meinem kurzen Kommentar zu diesem Papier möchte ich auf einige dieser Anregungen hinweisen.

Beschreibung: Von welcher "Informationsumwelt" träumt jemand, der für seine wissenschaftliche (und sonstige) Arbeit digitale Informationstechnologie intensiv einsetzt? In diesem Artikel beschreibe ich meinen "digitalen Traum". Er ist ganz einfach zu formulieren:"Ich will alles und zwar sofort, jederzeit, "überall" und kostenlos zur Verfügung haben." Ich schildere, was davon heute schon (fast) realisiert ist und was noch fehlt. Ich skizziere einige zentrale Schwierigkeiten der vollständigen Realisierung und skizziere mögliche Lösungen.

Beschreibung: Im Rahmen der biomechanischen Simulation knöcherner Organe ist die Frage nach einer befriedigenden Materialbeschreibung nach wie vor ungelöst. Computertomographische Datensätze liefern eine räumliche Verteilung der (Röntgen-)Dichte und ermöglichen damit eine gute Darstellung der individuellen Geometrie. Weiter können die verschiedenen Materialbestandteile des Knochens, Spongiosa und Kortikalis, voneinander getrennt werden. Aber die richtungsabängige Information der Materialanisotropie ist verloren. In dieser Arbeit wird ein Ansatz für eine anisotrope Materialbeschreibung vorgestellt, die es ermöglicht, den Einfluss der individuellen knöchernen Struktur auf das makroskopische Materialverhalten abzuschätzen.

Beschreibung: Many phenomena in nature and engineering happen simultaneously on rather diverse spatial and temporal scales, i.e.\ exhibit a multi-scale character. Therefore various hierarchical data structures and numerical schemes have been devised to represent quantitatively such phenomena. A special numerical multilevel technique, associated with a particular hierarchical data structure, is so-called Adaptive Mesh Refinement (AMR). This scheme achieves locally very high spatial and temporal resolutions. Due to its popularity, many scientists are in need of interactive visualization tools for AMR data. In this article we present a 3D texture-based volume rendering algorithm for AMR data, that directly utilizes the hierarchical structure. Thereby interactive rendering even for large data sets is achieved. In particular the problems of interpolation artifacts, opacity corrections, and texture memory limitations are addressed. The algorithm's value in practice is demonstrated with simulation and image data.

Beschreibung: By combining techniques of preparation, histology, confocal microscopy, data visualization and data processing, we have created and recently published a standard brain model for drosophila and honey bee brains. This report describes the algorithms and implementation of the corresponding software modules. At the same time it serves as a user's guide for scientist who want to reproduce the results for differerent species or mutants.

Beschreibung: Several classes of systems of evolution equations with one or two vector unknowns are considered. We investigate also systems with one vector and one scalar unknown. For these classes all equations having the simplest higher symmetry are listed.

Beschreibung: Two traffic streams $\Phi_1$, $\Phi_2$ are offered a link. The calls of $\Phi_i$ require exponential holding times with parameter $\mu$ and are accepted if less than $C_i$ trunks are occupied. Approximating the $\Phi_i$ by appropriate renewal processes meeting their first two moments, defined as the moments of the numbers of calls in virtual links of infinite capacity to which the traffic streams as freed traffics are virtually directed and where the calls get fresh exponential i.i.d.\ holding times with parameter $\mu$, stable recursive algorithms of complexity $O(\max(C_1,C_2))$ are derived for the first two defined as above moments of the individual overflow and freed carried traffics. The results offer a unified handling of both overflow and carried traffics in circuit switching networks with trunk reservation, providing a basis for new two-moment network dimensioning algorithms.

Beschreibung: We study the performance of QCD simulations with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering on $10^4$ and $12^4$ lattices. In order to compare tempered with standard simulations, covariance matrices between sub-ensembles have to be formulated and evaluated using the general properties of autocorrelations of the parallel tempering algorithm. We find that rendering the hopping parameter $\kappa$ dynamical does not lead to an essential improvement. We point out possible reasons for this observation and discuss more suitable ways of applying parallel tempering to QCD.

Beschreibung: Dem vorliegenden Aufsatz liegt ein Vortrag zugrunde, den die Verfasserin auf der Ersten Gemeinsamen Fachtagung der DBV-Landesverbände Berlin und Brandenburg "Wir machen den Weg frei : Fusionen - Kooperationen in Berlin und Brandenburg" am 17. Oktober 2001 gehalten hat, in der Vortragsreihe "Möglichkeiten und Grenzen von Ausleih- und bibliographischen Verbünden - VÖB Berlin, VÖB Brandenburg, KOBV". Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) ist angetreten, um auf der Basis neuer Technologien zeitgemäße, nutzerorientierte Dienstleistungen für den Informationsbereich zu entwickeln und die Informationsinfrastruktur in der Region Berlin-Brandenburg neu zu organisieren. Dabei setzt der KOBV insbesondere auf das Internet. Die Verfasserin beschreibt die einzelnen Stufen, in denen die Dienste des KOBV aufgebaut wurden und kontinuierlich weiter ausgebaut werden. Dabei zeigt sie Vorteile auf, die Nutzern und Bibliotheken durch den Verbund entstehen, und lotet gleichzeitig die Grenzen aus, die dem Verbund gesetzt sind.

Beschreibung: We report numerical results for SBmethod --- a publically available implementation of the spectral bundle method --- applied to the 7$^{th}$ DIMACS challenge test sets that are semidefinite relaxations of combinatorial optimization problems. The performance of the code is heavily influenced by parameters that control bundle update and eigenvalue computation. Unfortunately, no mathematically sound guidelines for setting them are known. Based on our experience with SBmethod, we propose heuristics for dynamically updating the parameters as well as a heuristc for improving the starting point. These are now the default settings of SBmethod Version 1.1. We compare their performance on the DIMACS instances to our previous best choices for Version 1.0. SBmethod Version 1.1 is also part of the independent DIMACS benchmark by H.~Mittelmann. Based on these results we try to analyze strengths and weaknesses of our approach in comparison to other codes for large scale semidefinite programming.

Beschreibung: Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed $k$, linear time algorithms exist to solve the decision problem ``treewidth $\leq k$'', their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.

Beschreibung: The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.

Beschreibung: {\begin{rawhtml} 〈a href="http://dx.doi.org/10.1007/s10479-007-0178-0"〉 Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0〈/a〉 \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.

Beschreibung: Telota ist ein Kunstwort, das für alle Aktivitäten der Berlin-Brandenburgischen Akademie der Wissenschaften steht, die der Förderung von Forschung, Kommunikation und Präsentation durch elektronische Medien dienen. In diesem Artikel werden die Entstehung des Telota-Projektes geschildert und die Ziele diskutiert, die mit diesem Projekt erreicht werden sollen. Es geht darum, moderne Informationstechnik bewusst, geplant und nachhaltig für alle Belange der {\rm BBAW} einzusetzen. Informationstechnische Werkzeuge sollen für die wissenschaftliche Arbeit effizient genutzt werden; die Information nach innen und nach außen soll deutlich verbessert werden; eine bessere Kommunikationsinfrastuktur soll die Zusammenarbeit fördern.

Beschreibung: The pole condition is a general concept for the theoretical analysis and the numerical solution of a variety of wave propagation problems. It says that the Laplace transform of the physical solution in radial direction has no poles in the lower complex half-plane. In the present paper we show that for the Helmholtz equation with a radially symmetric potential the pole condition is equivalent to Sommerfeld's radiation condition. Moreover, a new representation formula based on the pole condition is derived and used to prove existence, uniqueness and asymptotic properties of solutions. This lays the foundations of a promising new algorithm to solve time-harmonic scattering problems numerically and provides a new approach for analyzing existing algorithms such as the Perfectly Matched Layer (PML) method and the Bayliss-Gunzburger-Turkel (BGT) algorithm.

Beschreibung: In this paper we study the PML method for Helmholtz-type scattering problems with radially symmetric potential. The PML method consists in surrounding the computational domain by a \textbf{P}erfectly \textbf{M}atched sponge \textbf{L}ayer. We prove that the approximate solution obtained by the PML method converges exponentially fast to the true solution in the computational domain as the thickness of the sponge layer tends to infinity. This is a generalization of results by Lassas and Somersalo based on boundary integral eqaution techniques. Here we use techniques based on the pole condition instead. This makes it possible to treat problems without an explicitly known fundamental solution.