@article{KossickSchulteFotosKuiperFotos2010, author = {Kossick, Regine and Schulte (Fotos), Philip and Kuiper (Fotos), Jens-Hendrik}, title = {Die Bibliothek des Konrad-Zuse-Zentrums f{\"u}r Informationstechnik "{\"U}berall ist Mathematik drin"}, journal = {One Person Libraries Berlin. 10 Jahre Arbeitskreis OPL Berlin/Brandenburg}, pages = {18 -- 23}, year = {2010}, language = {de} } @misc{OPUS4-5284, title = {Annual Report 2013}, volume = {2013}, organization = {Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52848}, pages = {124}, year = {2014}, language = {en} } @misc{OPUS4-6433, title = {Annual Report 2016}, volume = {2016}, organization = {Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64339}, pages = {122}, year = {2017}, language = {en} } @misc{Rusch1999, author = {Rusch, Beate}, title = {Normierungen von Zeichenfolgen als erster Schritt des Match - Zur Dublettenbehandlung im Kooperativen BibliotheksverbundBerlin-Brandenburg -}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4010}, number = {SC-99-13}, year = {1999}, abstract = {Im Kooperativen Bibliotheksverbund Berlin-Brandenburg (KOBV) wird die verteilte Suche in heterogenen Datenbank mit einer integrierten Dublettenerkennung und -zusammenfuehrung realisiert. Beschrieben werden die einzelnen attributspezifischen Normierungsschritte, die dem eigentlichen Vergleich (MATCH) zweier Datens{\"a}tze vorangehen.}, language = {de} } @misc{Kuberek1999, author = {Kuberek, Monika}, title = {Gemeinsamer KOBV-Standard}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4027}, number = {SC-99-14}, year = {1999}, abstract = {Der neue ''verteilte'' Bibliotheksverbund KOBV erfordert neue Arbeitsweisen und neue Formen der Zusammenarbeit der Bibliotheken untereinander. Im KOBV wird es keine zentrale Erschließung geben, sondern die Erschließung wird lokal, in den Bibliotheken durchgef{\"u}hrt. Entsprechend ihren Nutzerbed{\"u}rfnissen bestimmen die Bibliotheken die Erschließungsart, den Erschließungsumfang und die Erschließungstiefe selbst. Als gemeinsamer regionaler Standard wird lediglich ein ''Mindeststandard'' auf der Basis von RAK-WB definiert. Dieser Gemeinsame KOBV-Standard ber{\"u}cksichtigt vor allem suchrelevante Elemente, um den Nutzern im KOBV m{\"o}glichst einheitliche Sucheinstiege zu bieten. Der Gemeinsame KOBV-Standard wird in diesem Papier vorgestellt.}, language = {de} } @misc{Kuberek1999, author = {Kuberek, Monika}, title = {Umgang mit hierarchischen Strukturen des MAB2-Datenformates in der KOBV-Suchmaschine}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4030}, number = {SC-99-15}, year = {1999}, abstract = {Die KOBV-Suchmaschine verarbeitet Daten im bibliographischen Datenformat MAB2 (Maschinelles Austauschformat f{\"u}r Bibliotheken, Ausgabe 2), das in deutschsprachigen L{\"a}ndern angewandt wird. Im MAB2-Format sind f{\"u}r mehrb{\"a}ndige begrenzte Werke und fortlaufende Sammelwerke hierarchische Strukturen realisiert - mit bis zu drei Hierarchiestufen und unterschiedlichem Aufbau, je nachdem, ob es sich um ein begrenztes Werk oder um ein Werk ohne geplanten Abschluß handelt. Jede hierarchische Stufe entspricht einem Datensatz, die zusammengeh{\"o}rigen Datens{\"a}tze sind miteinander verkn{\"u}pft. Inhaltlich enth{\"a}lt eine Stufe oft nur Teilinformationen des Werkes; erst die Stufen zusammen ergeben die vollst{\"a}ndige Information. In der KOBV-Suchmaschine werden Dokumente aus verschiedenen Bibliotheken zusammengef{\"u}hrt. Hierarchische Strukturen potenzieren gewissermaßen die mit der Dublettenbehandlung (Match- und Merge-Verfahren) verbundene Problematik: Es m{\"u}ssen nicht nur Datens{\"a}tze aus verschiedenen Bibliotheken zusammengef{\"u}hrt werden, sondern dar{\"u}ber hinaus die zusammengeh{\"o}rigen Datens{\"a}tze der unterschiedlichen Hierarchiestufen. Der Artikel enth{\"a}lt eine ausf{\"u}hrliche Analyse der in MAB2 vorkommenden hierarchischen Strukturen, beschreibt die Anforderungen f{\"u}r die Lieferung hierarchischer Datens{\"a}tze aus den lokalen Systemen und stellt das Verfahren vor, wie in der KOBV-Suchmaschine mit diesen hierarchischen Datenstrukturen bei der Dublettenbehandlung umgegangen wird. Anhand von Fallbeispielen wird die Problematik der Verkn{\"u}pfung zusammengef{\"u}hrter h-S{\"a}tze er{\"o}rtert. Die KOBV-Suchmaschine verarbeitet Daten im bibliographischen Datenformat MAB2 (Maschinelles Austauschformat f{\"u}r Bibliotheken, Ausgabe 2), das in deutschsprachigen L{\"a}ndern angewandt wird. Im MAB2-Format sind f{\"u}r mehrb{\"a}ndige begrenzte Werke und fortlaufende Sammelwerke hierarchische Strukturen realisiert - mit bis zu drei Hierarchiestufen und unterschiedlichem Aufbau, je nachdem, ob es sich um ein begrenztes Werk oder um ein Werk ohne geplanten Abschluß handelt. Jede hierarchische Stufe entspricht einem Datensatz, die zusammengeh{\"o}rigen Datens{\"a}tze sind miteinander verkn{\"u}pft. Inhaltlich enth{\"a}lt eine Stufe oft nur Teilinformationen des Werkes; erst die Stufen zusammen ergeben die vollst{\"a}ndige Information. In der KOBV-Suchmaschine werden Dokumente aus verschiedenen Bibliotheken zusammengef{\"u}hrt. Hierarchische Strukturen potenzieren gewissermaßen die mit der Dublettenbehandlung (Match- und Merge-Verfahren) verbundene Problematik: Es m{\"u}ssen nicht nur Datens{\"a}tze aus verschiedenen Bibliotheken zusammengef{\"u}hrt werden, sondern dar{\"u}ber hinaus die zusammengeh{\"o}rigen Datens{\"a}tze der unterschiedlichen Hierarchiestufen. Der Artikel enth{\"a}lt eine ausf{\"u}hrliche Analyse der in MAB2 vorkommenden hierarchischen Strukturen, beschreibt die Anforderungen f{\"u}r die Lieferung hierarchischer Datens{\"a}tze aus den lokalen Systemen und stellt das Verfahren vor, wie in der KOBV-Suchmaschine mit diesen hierarchischen Datenstrukturen bei der Dublettenbehandlung umgegangen wird. Anhand von Fallbeispielen wird die Problematik der Verkn{\"u}pfung zusammengef{\"u}hrter h-S{\"a}tze er{\"o}rtert.}, language = {de} } @misc{Kuberek1999, author = {Kuberek, Monika}, title = {Dublettenbehandlung (Match- und Merge-Verfahren) in der KOBV-Suchmaschine - Grundlagen -}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4042}, number = {SC-99-16}, year = {1999}, abstract = {Die Recherche {\"u}ber die KOBV-Suchmaschine liefert Datens{\"a}tze aus unterschiedlichen Bibliotheken. Damit der Nutzer nicht viele, unter Umst{\"a}nden lange Listen f{\"u}r jede Bibliothek durchbl{\"a}ttern muss werden die Datens{\"a}tze in der KOBV-Suchmaschine einer Dublettenbehandlung (Match- und Merge-Verfahren) unterzogen. Ziel dieses Verfahrens ist es, dem Nutzer m{\"o}glichst nur einen einzigen Datensatz mit allen zugeh{\"o}rigen Bestandsnachweisen aus den Bibliotheken anzuzeigen. In dem vorliegenden Papier steht das Match-Verfahren, das von der KOBV-Projektgruppe eigens f{\"u}r den Einsatz in der KOBV-Suchmaschine entwickelt wurde, im Vordergrund. Das Merge-Verfahren, das auf Konzepte von Ex Libris zur{\"u}ckgeht, ist lediglich am Rande erw{\"a}hnt. Ziel bei der Entwicklung des Match- und Merge-Verfahrens war es, in der KOBV-Suchmaschine ein Verfahren zu implementieren, das vollkommen automatisiert, ohne Zuhilfenahme manueller und intellektueller Eingriffe, abl{\"a}uft. In diesem Papier sind die Grundlagen zum Match- und Merge-Verfahren in der KOBV-Suchmaschine zusammengefaßt. Zun{\"a}chst wird definiert, was unter einer Dublette {\"u}berhaupt zu verstehen ist. Die Begriffe Dokument und Werk werden analysiert, die wesentlich sind f{\"u}r die Entscheidung, welche Datens{\"a}tze in der KOBV-Suchmaschine letztendlich zusammengef{\"u}hrt werden. Anhand umfassender Literaturrecherchen werden die zur Dublettenbehandlung herangezogenen bibliographischen Beschreibungselemente (Attribute) in verschiedenen MARC- und MAB-Datenbanken ermittelt und grunds{\"a}tzliche Probleme beim Erkennen dubletter bibliographischer Datens{\"a}tze aufgezeigt. Schließlich werden Verfahren vorgestellt und diskutiert, wie die Attribute in das Match- und Merge-Verfahren eingebunden werden: bei nur einer Gewichtung (positiver Wert) und bei zwei Gewichtungen (positiver und negativer Wert). Auf dieser Basis werden Tabellen mit Werten f{\"u}r zwei unterschiedliche Gewichtungsverfahren in der KOBV-Suchmaschine entwickelt, die als Ausgangswerte f{\"u}r erste Testverfahren in den Match- und Merge-Algorithmus in der KOBV-Suchmaschine implementiert werden.}, language = {de} } @misc{Groetschel1999, author = {Gr{\"o}tschel, Martin}, title = {My Favorite Theorem: Characterizations of Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4053}, number = {SC-99-17}, year = {1999}, abstract = {This paper summarizes and discusses various characterizations of perfect graphs and mentions some open problems in this area.}, language = {en} } @phdthesis{Schuette1999, author = {Sch{\"u}tte, Christof}, title = {Conformational Dynamics: Modelling, Theory, Algorithm, and Application to Biomolecules}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4063}, number = {SC-99-18}, year = {1999}, abstract = {The function of many important biomolecules comes from their dynamic properties and their ability to switch between different {\em conformations}. In a conformation, the large scale geometric structure of the molecule is understood to be conserved, whereas on smaller scales the system may well rotate, oscillate or fluctuate. In a recent article [J. Comp. Phys., 151,1 (1999)], the present author and coworkers demonstrated that (a) conformations can be understood as almost invariant sets of some Markov chain being defined via the Hamiltonian system governing the molecular dynamics and that (b) these sets can efficiently be computed via eigenvectors of the corresponding Markov operator. The persent manuscript reviews the mathematical modelling steps behind the novel concept, includes a rigorous analytical justification of this approach and especially of the numerical details of the algorithm, and illustrates its performance when applied to realistic molecular systems.}, language = {en} } @misc{DeuflhardKleinReinefeldetal.1999, author = {Deuflhard, Peter and Klein, Rupert and Reinefeld, Alexander and St{\"u}ben, Hinnerk}, title = {Power-User und Supercomputer}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4070}, number = {SC-99-19}, year = {1999}, abstract = {Abstract-Sammlung zum gleichnamigen Workshop am ZIB vom 19.--20. Mai 1999}, language = {de} } @phdthesis{Lang1999, author = {Lang, Jens}, title = {Adaptive Multilevel Solution of Nonlinear Parabolic PDE Systems. Theory, Algorithm, and Applications}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4089}, number = {SC-99-20}, year = {1999}, abstract = {This monograph has been written to illustrate the interlocking of theory, algorithm, and application in developing solution techniques for complex PDE systems. A deep theoretical understanding is necessary to produce a powerful idea leading to a successful algorithm. Efficient and robust implementation is the key to make the algorithm perform satisfactorily. The extra insight obtained by solving real--life problems brings out the structure of the method more clearly and suggests often ways to improve the numerical algorithm. It is my intention to impart the beauty and complexity found in both the theoretical investigation of the adaptive algorithm proposed here, i.e., the coupling of Rosenbrock methods in time and multilevel finite elements in space, and its realization. I hope that this method will find many more interesting applications.}, language = {en} } @misc{Schneider1999, author = {Schneider, Wolfram}, title = {Ein verteiltes Bibliotheks-Informationssystem auf Basis des Z39.50 Protokolls}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4092}, number = {SC-99-21}, year = {1999}, abstract = {\\{\bf Zusammenfassung: }Diese Diplomarbeit beschreibt ein verteiltes Bibliotheks-Informationssystem f{\"u}r bibliographische Datenbanken im Internet. Der Name des Systems ist ZACK. Der Benutzer kann mit ZACK in einer oder mehreren bibliographischen Datenbanken nach einem Dokument suchen und die Treffer in die eigene lokale Datenbank {\"u}bernehmen. Mit der {\"U}bernahme der Datens{\"a}tze aus einer fremden Datenbank wird die Erfassung neuer Dokumente wesentlich erleichtert, da die Eigenkatalogisierung auf ein Minimum beschr{\"a}nkt werden kann. Es wird doppelte Arbeit vermieden, und die Datens{\"a}tze haben eine gleichbleibend hohe Qualit{\"a}t. Bei der verteilten Suche mit ZACK wird parallel in mehreren Datenbanken gesucht. Dubletten werden als solche erkannt. Dem Benutzer wird eine {\"u}bersichtliche Kurztrefferliste ohne doppelte Eintr{\"a}ge angeboten. Er kann dann selbst entscheiden, aus welcher Datenbank er die Datens{\"a}tze {\"u}bernimmt. Die verteilte Suche hat in der Praxis eine deutlich bessere Trefferquote gebracht als die Suche in nur einer Datenbank. Dabei bleibt die Antwortzeit in einem f{\"u}r den Benutzer akzeptablen Rahmen. Die Kurztrefferliste wird durch die Dublettenkontrolle k{\"u}rzer und {\"u}bersichtlicher. English Title: A Distributed Library Information System on the Basis of the Z39.50 Protocol This diploma thesis desribes a distributed library information system for bibliographic databases in the Internet. The name of the system is ZACK. With ZACK the user is able to search for a particular document in several databases and to include the matches in his/her own local database. The inclusion of data records from an external database makes the capture of new documents much easier, as internal cataloging is reduced to a minimum. Double work is eliminated and a continuously high quality of data record is ensured. The distributed search by means of ZACK is carried out in several databases in parallel. Duplicates are recognized; and a short list of matches without double entries is offered. The user can then decide for himself from which database to include data records. In practice, a distributed search has produced far better results than the search in one particular database. Response times are within an acceptable limit for the user. The short list of hits is made clearer and more concise by the duplicate check. The diploma thesis is also available in PDF, HTML, and ASCII format: http://wolfram.schneider.org/lv/diplom/ .}, language = {de} } @misc{Beck1999, author = {Beck, Rudolf}, title = {Graph-Based Algebraic Multigrid for Lagrange-Type Finite Elements on Simplicial Meshes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4100}, number = {SC-99-22}, year = {1999}, abstract = {We present an algebraic multigrid preconditioner which uses only the graphs of system matrices. Some elementary coarsening rules are stated, from which an advancing front algorithm for the selection of coarse grid nodes is derived. This technique can be applied to linear Lagrange-type finite element discretizations; for higher-order elements an extension of the multigrid algorithm is provided. Both two- and three-dimensional second order elliptic problems can be handled. Numerical experiments show that the resulting convergence acceleration is comparable to classical geometric multigrid.}, language = {en} } @misc{GalliatDeuflhard2000, author = {Galliat, Tobias and Deuflhard, Peter}, title = {Adaptive hierarchical cluster analysis by Self-Organizing Box Maps}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5815}, number = {00-13}, year = {2000}, abstract = {The present paper aims at an extension of {\sc Kohonen's} Self-Organizing Map (SOM) algorithm to be called Self-Organizing Box Map (SOBM) algorithm; it generates box codebooks in lieu of point codebooks. Box codebooks just like point codebooks indirectly define a Voronoi tessellation of the input space, so that each codebook vector represents a unique set of points. Each box codebook vector comprises a multi-dimensional interval that approximates the related partition of the Voronoi tessellation. Upon using the automated cluster identification method that has recently been developed by the authors, the codebook vectors can be grouped in such a way that each group represents a point cluster in the input space. Since the clustering usually depends on the size of the SOM, one cannot be sure, whether the clustering comes out to be optimal. Refinement of part of the identified clusters would often improve the results. This paper presents the concept of an adaptive multilevel cluster algorithm that performs such refinements automatically. Moreover the paper introduces a concept of essential dimensions and suggests a method for their identification based on our herein suggested box codebooks. Applications of the algorithm to molecular dynamics will be described in a forthcoming paper.}, language = {en} } @misc{BienstockBley2000, author = {Bienstock, Daniel and Bley, Andreas}, title = {Capacitated Network Design with Multicast Commodities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5823}, number = {00-14}, year = {2000}, abstract = {This paper addresses the problem of designing a minimum cost network whose capacities are sufficiently large to allow a feasible routing of a given set of multicast commodities. A multicast commodity consists of a set of two or mo re terminals that need to be connected by a so called broadcast tree, which consumes on all of its edges a capacity as large as the demand value associated with that commodity. We model the network design problem with multicast commodities as the problem of packing capacitated Steiner trees in a graph. In the first part of the paper we present three mixed-integer programming formulations for this problem. The first natural formulation uses only one integer capacity variable for each edge and and one binary tree variable for each commodity-edge pair. Applying well-known techniques from the Steiner tree problem, we then develop a stronger directed and a multicommodity flow based mixed-integer programming formulation. In the second part of the paper we study the associated polyhedra and derive valid and even facet defining inequalities for the natural formulation. Finally, we describe separation algorithms for these inequalities and present computational results that demonstrate the strength of our extended formulations.}, language = {en} } @misc{Steinbach2000, author = {Steinbach, Marc}, title = {Hierarchical Sparsity in Multistage Convex Stochastic Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5837}, number = {00-15}, year = {2000}, abstract = {Interior point methods for multistage stochastic programs involve KKT systems with a characteristic global block structure induced by dynamic equations on the scenario tree. We generalize the recursive solution algorithm proposed in an earlier paper so that its linear complexity extends to a refined tree-sparse KKT structure. Then we analyze how the block operations can be specialized to take advantage of problem-specific sparse substructures. Savings of memory and operations for a financial engineering application are discussed in detail.}, language = {en} } @misc{MeyerSteinkeBrandletal.2000, author = {Meyer, Michael and Steinke, Thomas and Brandl, Maria and S{\"u}hnel, J{\"u}rgen}, title = {Density functional study of guanine and uracil quartets and of guanine quartet metal/ion complexes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5842}, number = {00-16}, year = {2000}, abstract = {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.}, language = {en} } @misc{OevermannKleinBergeretal.2000, author = {Oevermann, Michael and Klein, Rupert and Berger, Marsha and Goodman, Jonathan}, title = {A Projection Method for Two-Phase Incompressible Flow with Surface Tension and Sharp Interface Resolution}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5851}, number = {00-17}, year = {2000}, abstract = {We present a fully second order projection method for the simulation of two-phase incompressible flow with surface tension. The Navier-Stokes equations are solved with a projection method on a fixed Cartesian grid. The free interface between the two fluids is tracked with a level set approach. The conditions at the interface for the pressure, the pressure gradient, and the velocity are explicitly incorporated into the scheme leading to a sharp representation of the pressure discontinuity and the interfacial force. The scheme in the presented form does not introduce additional points in the standard finite difference stencils. Computational results are compared with analytic solutions for a static round bubble, damped surface waves, and Rayleigh-Taylor instabilities.}, language = {en} } @misc{Koster2000, author = {Koster, Arie M.C.A.}, title = {Re-Optimization of Signaling Transfer Points}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5863}, number = {00-18}, year = {2000}, abstract = {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.}, language = {en} } @misc{KrumkeNoltemeierWirth2000, author = {Krumke, Sven and Noltemeier, Hartmut and Wirth, Hans-Christoph}, title = {Graphentheoretische Konzepte und Algorithmen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5873}, number = {00-19}, year = {2000}, abstract = {Das vorliegende Skript bietet eine Einf{{\"u}}hrung in die Graphentheorie und graphentheoretische Algorithmen. Im zweiten Kapitel werden Grundbegriffe der Graphentheorie vorgestellt. Das dritte Kapitel besch{{\"a}}ftigt sich mit der Existenz von Wegen in Graphen. Hier wird auch die L{{\"o}}suung des ber{{\"u}}hmten K{{\"o}}nigsberger Br{{\"u}}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{{\"a}}ter mit der Tiefensuche ein Verfahren vorgestellt, das schneller arbeitet und mit dessen Hilfe man noch mehr Informationen {{\"u}}ber die Struktur eines Graphen gewinnen kann. In den folgenden Kapiteln werden Algorithmen vorgestellt, um minimale aufspannenden B{{\"a}}ume, k{{\"u}}rzeste Wege und maximale Fl{{\"u}}sse in Graphen zu bestimmen. Am Ende des Skripts wird ein kurzer Einblick in die planaren Graphen und Graphhomomorphismen geboten.}, language = {de} } @misc{MeyerSchnurreReissbrodtetal.2000, author = {Meyer, Michael and Schnurre, R{\"u}diger and Reissbrodt, Rolf and Trowitzsch-Kienast, Wolfram}, title = {Computer-aided design of novel siderophores: Pyridinochelin}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5887}, number = {00-20}, year = {2000}, abstract = {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.}, language = {en} } @misc{LangErdmann2000, author = {Lang, Jens and Erdmann, Bodo}, title = {Adaptive Linearly Implicit Methods for Heat and Mass Transfer Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5892}, number = {00-21}, year = {2000}, abstract = {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.}, language = {en} } @misc{HoeselKosterLeenseletal.2000, author = {Hoesel, Stan P.M. van and Koster, Arie M.C.A. and Leensel, Robert L.M.J. van de and Savelsbergh, Martin W.P.}, title = {Polyhedral Results for the Edge Capacity Polytope}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5907}, number = {00-22}, year = {2000}, abstract = {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.}, language = {en} } @misc{KrumkeRambauWeider2000, author = {Krumke, Sven and Rambau, J{\"o}rg and Weider, Steffen}, title = {An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6217}, number = {00-53}, year = {2000}, abstract = {In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most \$C\$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation.}, language = {en} } @misc{SchmidtFrieseZschiedrichetal.2000, author = {Schmidt, Frank and Friese, Tilmann and Zschiedrich, Lin and Deuflhard, Peter}, title = {Adaptive Multigrid Methods for the Vectorial Maxwell Eigenvalue Problem for Optical Waveguide Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6228}, number = {00-54}, year = {2000}, abstract = {This paper has been motivated by the need for a fast robust adaptive multigrid method to solve the vectorial Maxwell eigenvalue problem arising from the design of optical chips. Our nonlinear multigrid methods are based on a previous method for the scalar Helmholtz equation, which must be modified to cope with the null space of the Maxwell operator due to the divergence condition. We present two different approaches. First, we present a multigrid algorithm based on an edge element discretization of time-harmonic Maxwell's equations, including the divergence condition. Second, an explicit elimination of longitudinal magnetic components leads to a nodal discretization known to avoid discrete \emph{spurious modes} also and a vectorial eigenvalue problem, for which we present a multigrid solver. Numerical examples show that the edge element discretization clearly outperforms the nodal element approach.}, language = {en} } @misc{KrumkeRambau2000, author = {Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6238}, number = {00-55}, year = {2000}, abstract = {Wie soll man einen Aufzug steuern, wenn man keine Informationen {\"u}ber zuk{\"u}nftige Fahrauftr{\"a}ge besitzt? Soll man eine Bahncard kaufen, wenn die n{\"a}chsten Bahnreisen noch unbekannt sind? In der klassischen kombinatorischen Optimierung geht man davon aus, daß die Daten jeder Probleminstanz vollst{\"a}ndig gegeben sind. In vielen F{\"a}llen modelliert diese \emph{Offline-Optimierung} jedoch die Situationen aus Anwendungen nur ungen{\"u}gend. Zahlreiche Problemstellungen in der Praxis sind in nat{\"u}rlicher Weise \emph{online}: Sie erfordern Entscheidungen, die unmittelbar und ohne Wissen zuk{\"u}nftiger Ereignisse getroffen werden m{\"u}ssen. Als ein Standardmittel zur Beurteilung von Online-Algorithmen hat sich die \emph{kompetitive Analyse} durchgesetzt. Dabei vergleicht man den Zielfunktionswert einer vom Online-Algorithmus generierten L{\"o}sung mit dem Wert einer optimalen Offline-L{\"o}sung. Mit Hilfe der kompetitiven Analyse werden im Skript Algorithmen zum Caching, Netzwerk-Routing, Scheduling und zu Transportaufgaben untersucht. Auch die Schw{\"a}chen der kompetitiven Analyse werden aufgezeigt und alternative Analysekonzepte vorgestellt. Neben der theoretischen Seite werden auch die Anwendungen der Online-Optimierung in der Praxis, vor allem bei Problemen der innerbetrieblichen Logistik, beleuchtet. Bei der Steuerung automatischer Transportsysteme tritt eine F{\"u}lle von Online-Problemen auf. Hierbei werden an die Algorithmen oftmals weitere Anforderungen gestellt. So m{\"u}ssen Entscheidungen unter strikten Zeitbeschr{\"a}nkungen gef{\"a}llt werden (Echtzeit-Anforderungen). Dieses Skript ist aus dem Online-Teil der Vorlesung -Ausgew{\"a}hlte Kapitel aus der ganzzahligen Optimierung- (Wintersemester~1999/2000) und der Vorlesung -Online Optimierung- (Sommersemester~2000) an der Technischen Universit{\"a}t Berlin entstanden.}, language = {de} } @misc{GroetschelFonsecaDavis2001, author = {Gr{\"o}tschel, Martin and Fonseca, Irene and Davis, Mark}, title = {Round Table: The Impact of Mathematical Research on Industry and Vice Versa}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6259}, number = {00-57}, year = {2001}, abstract = {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.}, language = {en} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Frequency Assignment in Mobile Phone Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6265}, number = {00-58}, year = {2001}, abstract = {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.}, language = {en} } @misc{HohageSchmidtZschiedrich2001, author = {Hohage, Thorsten and Schmidt, Frank and Zschiedrich, Lin}, title = {Solving time-harmonic scattering problems based on the condition: Theory}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6279}, number = {01-01}, year = {2001}, abstract = {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.}, language = {en} } @misc{BorndoerferGroetschelLoebel2001, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Duty Scheduling in Public Transit}, doi = {10.1007/978-3-642-55753-8_50}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6286}, number = {01-02}, year = {2001}, abstract = {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.}, language = {en} } @misc{FischerSchuetteDeuflhardetal.2001, author = {Fischer, Alexander and Sch{\"u}tte, Christof and Deuflhard, Peter and Cordes, Frank}, title = {Hierarchical Uncoupling-Coupling of Metastable Conformations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6296}, number = {01-03}, year = {2001}, abstract = {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.}, language = {en} } @misc{HenrionLiMoelleretal.2001, author = {Henrion, Rene and Li, Pu and M{\"o}ller, Andris and Steinbach, Marc and Wendt, Moritz and Wozny, G{\"u}nter}, title = {Stochastic Optimization for Operating Chemical Processes Under Uncertainty}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6304}, number = {01-04}, year = {2001}, abstract = {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.}, language = {en} } @misc{EhrigOfenlochSchaberetal.2001, author = {Ehrig, Rainald and Ofenloch, Oliver and Schaber, Karlheinz and Deuflhard, Peter}, title = {Modelling and Simulation of Aerosol Formation by Heterogeneous Nucleation in Gas-Liquid Contact Devices}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6416}, number = {01-15}, year = {2001}, abstract = {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.}, language = {en} } @misc{GroetschelKrumkeRambauetal.2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Winter, Thomas and Zimmermann, Uwe}, title = {Combinatorial Online Optimization in Real Time}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6424}, number = {01-16}, year = {2001}, abstract = {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.}, language = {en} } @misc{GroetschelKrumkeRambau2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimization of Complex Transportation Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6438}, number = {01-17}, year = {2001}, abstract = {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.}, language = {en} } @misc{Wagler2001, author = {Wagler, Annegret}, title = {Rank-Perfect and Weakly Rank-Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6448}, number = {01-18}, year = {2001}, abstract = {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.}, language = {en} } @misc{JeltschStrangDeuflhard2001, author = {Jeltsch, Rolf and Strang, Gilbert and Deuflhard, Peter}, title = {First SIAM-EMS Conference "Applied Mathematics in our Changing World" Berlin 2001 - Collection of Abstracts}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6452}, number = {01-19}, year = {2001}, abstract = {Collection of abstracts of the first SIAM-EMS conference Applied Mathematics in our Changing World'' in Berlin, September 2-6, 2001.}, language = {en} } @misc{Koch2001, author = {Koch, Thorsten}, title = {ZIMPL User Guide}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6466}, number = {01-20}, year = {2001}, abstract = {{\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.}, language = {en} } @misc{Otto2001, author = {Otto, Dagmar}, title = {Informationsportale und Digitale Bibliotheken}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6479}, number = {01-21}, year = {2001}, abstract = {Im ersten Teil des folgenden Aufsatzes werden allgemeine {\"U}berlegungen zur Entwicklung von Bibliotheken hin zu Informationsvermittlungsstellen f{\"u}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{\"u}r ein Verbund-Informationsportal f{\"u}r den Kooperativen Bibliotheksverbund Berlin-Brandenburg entwickelt. Im Anhang befindet sich der Statusbericht {\"u}ber Informationsportale und digitale Bibliotheken in Deutschland. Dazu wurden sieben digitale Bibliotheken auf Verbundebene und 21 Bibliotheken nach Bundesl{\"a}ndern evaluiert.}, language = {de} } @misc{KrumkeRambauTorres2001, author = {Krumke, Sven and Rambau, J{\"o}rg and Torres, Luis Miguel}, title = {Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6484}, number = {01-22}, year = {2001}, abstract = {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.}, language = {en} } @misc{HohageSchmidtZschiedrich2001, author = {Hohage, Thorsten and Schmidt, Frank and Zschiedrich, Lin}, title = {Solving time-harmonic scattering problems based on the pole condition: Convergence of the PML method}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6494}, number = {01-23}, year = {2001}, abstract = {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.}, language = {en} } @misc{Steinbach2001, author = {Steinbach, Marc}, title = {General Information Constraints in Stochastic Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6502}, number = {01-24}, year = {2001}, abstract = {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.}, language = {en} } @misc{GarridoSteinbach2001, author = {Garrido, Izaskun and Steinbach, Marc}, title = {A Multistage Stochastic Programming Approach in Real-Time Process Control}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6317}, number = {01-05}, year = {2001}, abstract = {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.}, language = {en} } @misc{Byun2001, author = {Byun, Chul-Young}, title = {Lower Bounds for Large-Scale Set Partitioning Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6321}, number = {01-06}, year = {2001}, abstract = {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.}, language = {en} } @misc{KrumkePaepeRambauetal.2001, author = {Krumke, Sven and Paepe, Willem de and Rambau, J{\"o}rg and Stougie, Leen}, title = {Online Bin-Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6338}, number = {01-07}, year = {2001}, abstract = {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.}, language = {en} } @misc{Steinbach2001, author = {Steinbach, Marc}, title = {Tree-Sparse Convex Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6340}, number = {01-08}, year = {2001}, abstract = {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.}, language = {en} } @misc{BrandtBrandt2001, author = {Brandt, Andreas and Brandt, Manfred}, title = {On the Moments of the Overflow and Freed Carried Traffic for the GI/M/C/0 System}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6355}, number = {01-09}, year = {2001}, abstract = {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.}, language = {en} } @misc{Kuberek2001, author = {Kuberek, Monika}, title = {KOBV: institutionalisiert}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6360}, number = {01-10}, year = {2001}, abstract = {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{\"u}r Informationstechnik Berlin (ZIB) aufgebaut worden. Nachdem das Projekt erfolgreich abgeschlossen ist, wird der KOBV 2001 institutionalisiert. In dem Vortrag hat die Verfasserin einen {\"U}berblick {\"u}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{\"a}nden. Mittel- bis langfristig sollen Bibliotheken aller Sparten und Gr{\"o}ßen in den KOBV integriert werden, seien es wissenschaftliche Universalbibliotheken, universit{\"a}re Bibliothekssysteme, Spezialbibliotheken, Beh{\"o}rden- und Parlamentsbibliotheken oder {\"o}ffentliche Bibliotheken. Auch regionale Bibliotheksverb{\"u}nde k{\"o}nnen als Subverb{\"u}nde am KOBV teilnehmen. Mit der KOBV-Suchmaschine ist eine offene Plattform geschaffen worden, auf der weitere Entwicklungen aufsetzen k{\"o}nnen. Der Aufbau einer virtuellen Regionalbibliothek mit Bestell- und Lieferkomponenten ist eines der Ziele. Dar{\"u}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.}, language = {de} } @misc{ReinefeldLindenstruth2001, author = {Reinefeld, Alexander and Lindenstruth, Volker}, title = {How to Build a High-Performance Compute Cluster for the Grid}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6374}, number = {01-11}, year = {2001}, abstract = {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.}, language = {en} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Copyright und elektronisches Publizieren: Auf dem Weg zu vern{\"u}nftigen Regelungen?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6395}, number = {01-13}, year = {2001}, abstract = {Das \emph{Committee on Electronic Information and Communication} (CEIC) der \emph{International Mathematical Union} (IMU) hat die Aufgabe, sich {\"u}ber die langfristige Informationsversorgung in der Mathematik Gedanken zu machen und L{\"o}sungsvorschl{\"a}ge hierf{\"u}r zu erarbeiten. Das Kernthema ist nat{\"u}rlich "`Elektronisches Publizieren"'. Dazu geh{\"o}ren auch Copyright-Regelungen. \% Sie sind -- \% neben einer Andeutung der weiteren CEIC-Pl{\"a}ne -- der Fokus dieses \% kurzen Artikels. Er schließt mit einem von der IMU verabschiedeten \% Aufruf zu vern{\"u}nftigem Verhalten bei Copyright-Vereinbarungen. Eine \% nachhaltige Befolgung dieses Aufrufs -- verbunden mit weiteren \% Aktivit{\"a}ten -- k{\"o}nnte die (derzeit kaum noch bezahlbare und \% dadurch gef{\"a}hrdete) Literaturversorgung nachhaltig zum Positiven \% ver{\"a}ndern. Mit diesem Artikel beginnt eine kleine Serie von Aufs{\"a}tzen, in denen ich (in meiner Funktion als eines von elf CEIC-Mitgliedern) die Empfehlungen des CEIC erl{\"a}utern werde. \% Das heutige Thema sind die \% CEIC-Vorschl{\"a}ge zum Copyright}, language = {de} } @misc{SperberDalitz2000, author = {Sperber, Wolfram and Dalitz, Wolfgang}, title = {Portale, Search Engines und Math-Net}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5923}, number = {00-24}, year = {2000}, abstract = {Wie sucht ein Wissenschaftler im Internet die ben"otigten Informationen f{\"u}r seine Arbeit? Welche relevanten Informationen gibt es {\"u}berhaupt im Web? Sind daf{\"u}r solche Suchmaschinen wie AltaVista, Google oder HotBot die richtigen Werkzeuge? Die Antwort der Mathematiker heisst Math-Net, ein Informations- und Kommunikationssystem f{\"u}r die Mathematik. Math-Net besteht zun{\"a}chst aus den Informationen von Personen und Institutionen, die ihre f{\"u}r die Mathematik relevanten Informationen dort bereitstellen wollen. Das soll i.a. auf den Web-Servern der Personen oder Institutionen geschehen. Hierin unterscheidet sich die Situation im Math-Net nicht von der im WWW insgesamt. Im Math-Net sollen aber die Informationen in einheitlicher Weise erschlossen werden. Dazu gibt es sowohl f{\"u}r Server als auch f{\"u}r die Dokumente Empfehlungen f{\"u}r deren Strukturierung. Die lokalen Informationen werden dann im Math-Net durch automatische Verfahren gesammelt, ausgewertet und indexiert. Diese Indexe sind die Basis f{\"u}r die Math-Net Dienste. Das sind Search Engines und Portale, die einen qualifizierten und effizienten Zugang zu den Informationen im Math-Net bieten. Die Math-Net Dienste sind auf die Mathematik spezialisiert. Im Gegensatz zu den oben erw{\"a}hnten universellen Suchmaschinen decken sie nur einen winzigen Bruchteil des Web ab, aber daf{\"u}r den f{\"u}r die Mathematik relevanten Teil. Math-Net ist mehr als nur Search Engine oder Portal zu Informationen in der Mathematik. Es ist auch ein Informations- und Kommunikationssystem sowie ein Publikationsmedium f{\"u}r die Mathematik. Die mathematische Community hat sich in der Math-Net Initiative organisiert. Diese Initiative wird von der International Mathematical Union (IMU), der weltweiten Dachorganisation der mathematischen Gesellschaften, koordiniert. Die Entwicklung des Math-Net wird von dem breiten Konsens der Mathematiker getragen, den Zugang zu der f{\"u}r die Mathematik relevanten Information zu erleichtern und zu verbessern.}, language = {de} } @misc{IlgenfritzKerlerMuellerPreusskeretal.2000, author = {Ilgenfritz, Ernst-Michael and Kerler, Werner and M{\"u}ller-Preussker, Michael and St{\"u}ben, Hinnerk}, title = {Parallel tempering and decorrelation of topological charge in full QCD}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5930}, number = {00-25}, year = {2000}, abstract = {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.}, language = {en} } @misc{Huisinga2000, author = {Huisinga, Wilhelm}, title = {The Essential Spectral Radius and Asymptotic Properties of Transfer Operators}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5942}, number = {00-26}, year = {2000}, abstract = {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.}, language = {en} }