@misc{KonjevodKrumkeMarathe2000, author = {Konjevod, Goran and Krumke, Sven and Marathe, Madhav}, title = {Budget Constrained Minimum Cost Connected Medians}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5783}, number = {00-10}, year = {2000}, abstract = {Several practical instances of network design problems require the network to satisfy multiple constraints. In this paper, we address the \emph{Budget Constrained Connected Median Problem}: We are given an undirected graph \$G = (V,E)\$ with two different edge-weight functions \$c\$ (modeling the construction or communication cost) and \$d\$ (modeling the service distance), and a bound~\$B\$ on the total service distance. The goal is to find a subtree~\$T\$ of \$G\$ with minimum \$c\$-cost \$c(T)\$ subject to the constraint that the sum of the service distances of all the remaining nodes \$v \in V\setminus T\$ to their closest neighbor in~\$T\$ does not exceed the specified budget~\$B\$. This problem has applications in optical network design and the efficient maintenance of distributed databases. We formulate this problem as bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem that demonstrate that our performance ratios are close to best possible}, language = {en} } @misc{Krumke2000, author = {Krumke, Sven}, title = {News from the Online Traveling Repairman}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5767}, number = {00-08}, year = {2000}, abstract = {The traveling repairman problem (TRP) is a variant of the famous traveling salesman problem (TSP). The objective for the TRP is to minimize the latency, that is the the weighted sum of completion times of the cities, where the completion time of a city is defined to be the time in the tour before the city is reached. In the online traveling repairman problem (OLTRP) requests for visits to cities (points in a metric space) arrive online while the repairman is traveling. We analyze the performance of algorithms using competitive analysis, where the cost of an online algorithm is compared to that of an optimal offline algorithm. An optimal offline algorithm knows the entire request sequence in advance and can serve it with minimum cost. Recently, Feuerstein and Stougie presented a \$9\$-competitive algorithm for the OLTRP on the real line. In this paper we show how to use techniques from online-scheduling to obtain an \$8\$-competitive deterministic algorithm which works for any metric space. We also present a randomized algorithm which has a competitive ratio of \$\frac{4}{\ln 2}\approx 5.7708\$ against an oblivious adversary. All of our results also hold for the ``dial-a-ride'' generalization of the OLTRP, where objects have to be picked up and delivered by a server.}, language = {en} } @misc{BlomKrumkePaepeetal.2000, author = {Blom, Michiel and Krumke, Sven and Paepe, Willem de and Stougie, Leen}, title = {The Online-TSP Against Fair Adversaries}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5779}, number = {00-09}, year = {2000}, abstract = {In the online traveling salesman problem requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman which finishes as early as possible. Performance of algorithms is measured through their competitive ratio, comparing the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline solution. Objections against such omnipotent adversaries have lead us to devise an adversary that is in a natural way, in the context of routing problems, more restricted in power. For the exposition we consider the online traveling salesman problem on the metric space given by the non-negative part of the real line. We show that a very natural strategy is~\$3/2\$-competitive against the conventional adversary, which matches the lower bound on competitive ratios achievable for algorithms for this problem. Against the more ``\emph{fair adversary}'', that we propose, we show that there exists an algorithm with competitive ratio \$\frac{1+\sqrt{17}}{4}\approx 1.28\$ and provide a matching lower bound. We also show competitiveness results for a special class of algorithms (called zealous algorithms) that do not allow waiting time for the server as long as there are requests unserved.}, language = {en} } @misc{DeuflhardHegeSeebass2000, author = {Deuflhard, Peter and Hege, Hans-Christian and Seebass, Martin}, title = {Progress Towards a Combined MRI/Hyperthermia System}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5755}, number = {00-07}, year = {2000}, abstract = {Regional hyperthermia, a clinical cancer therapy, is the main topic of the Sonderforschungsbereich Hyperthermia: Scientific Methods and Clinical Applications'' at Berlin. In recent years, technological improvements towards a better concentration of heat to the desired target region have been achieved. These include a rather sophisticated integrated software environment for therapy planning and a new hyperthermia applicator. In a next step, a detailed closed loop monitoring of the actual treatment is to be developed. For this purpose the hyperthermia applicator is combined with an MRI system, which will allow to check the positioning of the patients and to measure individual blood perfusion as well as the 3D temperature distribution. The measurements will then be employed for an on-line control of the whole treatment. In this intended setting, new fast feedback control algorithms will come into play.}, language = {en} } @misc{YevickFrieseSchmidt2000, author = {Yevick, David and Friese, Tilmann and Schmidt, Frank}, title = {A Comparison of Transparent Boundary Conditions for the Fresnel Equation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5738}, number = {00-05}, year = {2000}, abstract = {We establish the relationship between the transparent boundary condition (BPP) of Baskakov and Popov [Wave Motion 14 (1991) 121-128] and Pakpadakis et. al. [J. Acoust. Soc. Am. 92 (1992) 2030-2038] and a second boundary condition (SDY) introduced by Schmidt and Deuflhard [Comp. Math. Appl. 29 (1995) 53-76] and Schmidt and Yevick [J. Compu. Phys. 134 (1997) 96-107], that is explicitly tailored to the form of the underlying numerical propagation scheme. Our analysis demonstrates that if the domain is first discretized in the propagation direction, the SDY expression can be obtained by applying the exact sequence of steps used to derive the BPP procedure. The BPP method is thus an approximate realization of the computationally far simpler and unconditionally stable SDY boundary condition.}, language = {en} } @misc{Schmidt2000, author = {Schmidt, Frank}, title = {Discrete Nonreflecting Boundary Conditions for the Helmholtz Equation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5744}, number = {00-06}, year = {2000}, abstract = {We derive exact discrete nonreflecting boundary conditions for time-harmonic scattering problems modeled by the Helmholtz equation. The main idea is to consider the exterior problem as an initial value problem with initial data given on the boundary of the computational domain. The solution of the exterior problem is obtained via Laplace transformation techniques which supply the boundary conditions in terms of discrete Dirichlet-to-Neumann operators.}, language = {en} } @misc{Fischer2000, author = {Fischer, Alexander}, title = {An Uncoupling-Coupling Technique for Markov Chain Monte Carlo Methods}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5720}, number = {00-04}, year = {2000}, abstract = {Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. By determining almost invariant sets of the associated Markov operator, the Monte Carlo sampling splits by a hierarchical annealing process into the essential regions of the state space; therefore UCMC aims at avoiding the typical metastable behavior of Monte Carlo techniques. From the viewpoint of Monte Carlo, a slowly converging long-time Markov chain is replaced by a limited number of rapidly mixing short-time ones. The correct weighting factors for the various Markov chains are obtained via a coupling matrix, that connects the samplings from the different almost invariant sets. The underlying mathematical structure of this approach is given by a general examination of the uncoupling-coupling procedure. Furthermore, the overall algorithmic scheme of UCMC is applied to the \$n\$-pentane molecule, a well-known example from molecular dynamics.}, language = {en} } @misc{Groetschel2000, author = {Gr{\"o}tschel, Martin}, title = {Verkehrsplanung: Bessere L{\"o}sungen mit Mathematik}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4439}, number = {SC-99-54}, year = {2000}, abstract = {Anwendungen der Mathematik in der Verkehrs- und Transporttechnologie haben eine große und bedeutende Tradition. Nat{\"u}rlich wurden die ersten Fahrzeuge mit der ingenieurm{\"a}ßigen Methode von Versuch, Irrtum und Verbesserung entworfen. Aber schon sehr bald kamen mathematische Berechnungen hinzu, mit denen mechanische Eigenschaften von Fahrzeugteilen ermittelt und zum Teil optimiert wurden. Die hierzu erforderliche Mathematik wurde in diesem Jahrhundert zu einem m{\"a}chtigen Werkzeugkasten ausgebaut. Mit diesem kann man heute z.B. hocheffiziente Motoren mit geringem Schadstoffausstoß entwerfen, aerodynamisch g{\"u}nstige Fahrzeugprofile ermitteln und Flugzeugfl{\"u}gel berechnen, die die gew{\"u}nschte Last sicher und mit geringem Treibstoffaufwand tragen. Die Mathematik unterst{\"u}tzt die Technologie des Verkehrs beginnend bei globalen Designfragen bis hin zur Spezifizierung von Materialeigenschaften kleinster Bauteile; sie berechnet mit hoher Pr{\"a}zision energieoptimale Bahnen von Raumflugk{\"o}rpern oder zeitoptimale Trajektorien f{\"u}r Flugzeuge, steuert automatische Roboteranlagen oder innerbetriebliche Transportsysteme.}, language = {de} } @misc{LangMerz2000, author = {Lang, Jens and Merz, Wilhelm}, title = {Two-Dimensional Adaptive Simulation of Dopant Diffusion in Silicon}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5716}, number = {00-03}, year = {2000}, abstract = {One important step in the fabrication of silicon-based integrated circuits is the creation of semiconducting areas by diffusion of dopant impurities into silicon. Complex models have been developed to investigate the redistribution of dopants and point defects. In general, numerical analysis of the resulting PDEs is the central tool to assess the modelling process. We present an adaptive approach which is able to judge the quality of the numerical approximation and which provides an automatic mesh improvement. Using linearly implicit methods in time and multilevel finite elements in space, we are able to integrate efficiently the arising reaction-drift-diffusion equations with high accuracy. Two different diffusion processes of practical interest are simulated.}, language = {en} } @misc{Wolf2000, author = {Wolf, Thomas}, title = {The Symbolic Integration of Exact PDEs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5702}, number = {00-02}, year = {2000}, abstract = {An algorithm is described to decide if a given polynomial differential expression \$\Delta\$ of multivariate functions is exact, i.e. whether there exists a first integral \$P\$ such that \$D_xP = \Delta\$ for any one of a set of variables \$x\$ and to provide the integral \$P\$. A generalization is given to allow integration in the case that the exactness is prohibited by terms which contain only functions of not all the independent variables.}, language = {en} } @misc{EhrigNowak2000, author = {Ehrig, Rainald and Nowak, Ulrich}, title = {Algorithmen- und Softwareoptimierung f{\"u}r die Satellitenbahn- und Schwerefeldmodellierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5694}, number = {00-01}, year = {2000}, abstract = {Dieser Report enth{\"a}lt die Ergebnisse der Untersuchungen, die gem{\"a}ss dem Forschungs-- und Entwicklungsvertrag Gravity zwischen dem GeoForschungsZentrum Potsdam und dem Konrad--Zuse--Zentrum Berlin vorgenommen wurden. Die damit vereinbarte wissenschaftliche Kooperation hat die folgenden Ziele: \item{die am GFZ vorhandenen Algorithmen und Softwaremodule auf ihre Effizienz hisichtlich Nutzung der Rechnerresourcen zu untersuchen und L{\"o}sungen f{\"u}r einen schnelleren Datendurchsatz zu entwickeln und zu implementieren,} \item{Methoden zur Regularisierung und L{\"o}sung schlecht konditionierter Normalgleichungssysteme (f{\"u}r Schwerefeldkoeffizienten) kritisch zu untersuchen und eine mathematisch objektive Strategie der Regularisierung zu entwickeln, und} \item{insbesondere im Hinblick auf die Anforderungen bei GRACE, verschiedene Bahnintegrationsverfahren hinsichtlich ihrer numerischen Genauigkeit und Einsatzm{\"o}glichkeiten zu untersuchen.}}, language = {de} } @misc{BengerHegeHeusler2000, author = {Benger, Werner and Hege, Hans-Christian and Heusler, Stefan}, title = {Visions of Numerical Relativity 1999}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4429}, number = {SC-99-53}, year = {2000}, abstract = {We present visualizations of recent supercomputer simulations from numerical relativity, exploiting the progress in visualization techniques and numerical methods also from an artistic point of view. The sequences have been compiled into a video tape, showing colliding black holes, orbiting and merging neutron stars as well as collapsing gravitational waves. In this paper we give some background information and provide a glance at the presented sequences.}, language = {en} } @misc{GroetschelKuberekLohrumetal.1999, author = {Gr{\"o}tschel, Martin and Kuberek, Monika and Lohrum, Stefan and L{\"u}gger, Joachim and Rusch, Beate}, title = {Der Kooperative Bibliotheksverbund Berlin-Brandenburg}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4418}, number = {SC-99-52}, year = {1999}, abstract = {Im Herbst 1999 ging der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) in Routinebetrieb. In technischer Hinsicht setzt der KOBV auf ein neuartiges, zukunftsweisendes Verbundkonzept, in dem die zentrale Datenbank mit dem Verbundkatalog ersetzt wird durch verteilte Datenbanken und lokale Kataloge, die durch das Netz (Internet) miteinander verbunden sind. Die zentrale Recherchefunktion wird ersetzt durch die KOBV-Suchmaschine. Beschrieben werden die Hintergr{\"u}nde, die zu diesem Konzept gef{\"u}hrt haben, die Kriterien, die die Architekturentscheidungen der Software bestimmt haben, sowie die einzelnen realisierten Komponenten.}, language = {de} } @misc{GroetschelKuberekLohrumetal.1999, author = {Gr{\"o}tschel, Martin and Kuberek, Monika and Lohrum, Stefan and L{\"u}gger, Joachim and Rusch, Beate}, title = {Die KOBV-Suchmaschine geht in Routinebetrieb}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4407}, number = {SC-99-51}, year = {1999}, abstract = {Im Herbst 1999 nimmt die KOBV-Suchmaschine, das technische "Herzst{\"u}ck" des KOBV, den Routinebetrieb auf. Nach einer kurzen Einf{\"u}hrung in die politischen und rechtlichen Grundlagen des KOBV-Projektes werden in diesem Aufsatz die Funktionalit{\"a}ten der KOBV-Suchmaschine, ihre Leistungen f{\"u}r Bibliotheksbenutzer und Bibliothekare, vorgestellt. Der Aufsatz schließt mit einem {\"U}berblick {\"u}ber den bisherigen Projektverlauf und der Erl{\"a}uterung der wichtigsten Prinzipien des KOBV - Offenheit, Dezentralit{\"a}t und Heterogenit{\"a}t.}, language = {de} } @misc{Kuberek1999, author = {Kuberek, Monika}, title = {Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) - Ein innovatives Verbundkonzept f{\"u}r die Region}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4399}, number = {SC-99-50}, year = {1999}, abstract = {Auf dem 89. Deutschen Bibliothekartag, der vom 25. bis 29. Mai 1999 in Freiburg (Breisgau) stattgefunden hat, wurde der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) zum ersten Mal der großen bibliothekarischen {\"O}ffentlichkeit vorgestellt. Am KOBV-Stand, der im Rahmen des gemeinsamen Standes der Arbeitsgemeinschaft der Verbundsysteme organisiert wurde, f{\"u}hrte die KOBV-Projektgruppe Funktionalit{\"a}ten der KOBV-Suchmaschine vor. In der Vortragsreihe zum Themenkreis XI "Neue Entwicklungen in den Verbund- und Lokalsystemen", die unter Mitwirkung der Arbeitsgemeinschaft der Verbundsysteme veranstaltet wurde, war der KOBV mit einem eigenen Vortrag vertreten: "Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) - Ein innovatives Verbundkonzept f{\"u}r die Region". In dem Vortrag hat die Verfasserin einen umfassenden {\"U}berblick {\"u}ber das KOBV-Projekt und den bisherigen Projektverlauf gegeben, die Projektziele und den politischen Rahmen er{\"o}rtert sowie die KOBV-Suchmaschine, das technische Kernst{\"u}ck des neuen Verbundes, vorgestellt. Der hier vorliegende Text ist die schriftlich ausgearbeitete Fassung dieses Vortrages.}, language = {de} } @misc{Helmberg1999, author = {Helmberg, Christoph}, title = {The m-Cost ATSP}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4374}, number = {SC-99-48}, year = {1999}, abstract = {Although the m-ATSP (or multi traveling salesman problem) is well known for its importance in scheduling and vehicle routing, it has, to the best of our knowledge, never been studied polyhedraly, i.e., it has always been transformed to the standard ATSP. This transformation is valid only if the cost of an arc from node \$i\$ to node \$j\$ is the same for all machines. In many practical applications this is not the case, machines produce with different speeds and require different (usually sequence dependent) setup times. We present first results of a polyhedral analysis of the m-ATSP in full generality. For this we exploit the tight relation between the subproblem for one machine and the prize collecting traveling salesman problem. We show that, for \$m\ge 3\$ machines, all facets of the one machine subproblem also define facets of the m-ATSP polytope. In particular the inequalities corresponding to the subtour elimination constraints in the one machine subproblems are facet defining for m-ATSP for \$m\ge 2\$ and can be separated in polynomial time. Furthermore, they imply the subtour elimination constraints for the ATSP-problem obtained via the standard transformation for identical machines. In addition, we identify a new class of facet defining inequalities of the one machine subproblem, that are also facet defining for m-ATSP for \$m\ge 2\$. To illustrate the efficacy of the approach we present numerical results for a scheduling problem with non-identical machines, arising in the production of gift wrap at Herlitz PBS AG.}, language = {en} } @misc{Helmberg1999, author = {Helmberg, Christoph}, title = {Semidefinite Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4382}, number = {SC-99-49}, year = {1999}, abstract = {Due to its many applications in control theory, robust optimization, combinatorial optimization and eigenvalue optimization, semidefinite programming had been in wide spread use even before the development of efficient algorithms brought it into the realm of tractability. Today it is one of the basic modeling and optimization tools along with linear and quadratic programming. Our survey is an introduction to semidefinite programming, its duality and complexity theory, its applications and algorithms.}, language = {en} } @misc{Stueben1999, author = {St{\"u}ben, Hinnerk}, title = {Decorrelation of the Topological Charge in Tempered Simulations of Full QCD}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4369}, number = {SC-99-47}, year = {1999}, abstract = {The improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering is studied. As an indicator for decorrelation the topological charge is used.}, language = {en} } @misc{MarchandMartinWeismanteletal.1999, author = {Marchand, Hugues and Martin, Alexander and Weismantel, Robert and Wolsey, Laurence}, title = {Cutting Planes in Integer and Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4339}, number = {SC-99-44}, year = {1999}, abstract = {This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored.}, language = {en} } @misc{FrieseSchmidtYevick1999, author = {Friese, Tilman and Schmidt, Frank and Yevick, David}, title = {Transparent Boundary Conditions for a Wide-Angle Approximation of the One-Way Helmholtz Equation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4345}, number = {SC-99-45}, year = {1999}, abstract = {We present nonlocal discrete transparent boundary conditions for a fourth-order wide-angle approximation of the two-dimensional Helmholtz equation. The boundary conditions are exact in the sense that they supply the same discrete solution on a bounded interior domain as would be obtained by considering the problem on the entire unbounded domain with zero boundary conditions at infinity. The proposed algorithm results in an unconditionally stable propagation method. Numerical examples from optics illustrate the efficiency of our approach.}, language = {en} } @misc{SchmidtFrieseYevick1999, author = {Schmidt, Frank and Friese, Tilmann and Yevick, David}, title = {Transparent Boundary Conditions for Split-Step Pade Approximations of the One-Way Helmholtz Equation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4353}, number = {SC-99-46}, year = {1999}, abstract = {In this paper, we generalize the nonlocal discrete transparent boundary condition introduced by Schmidt and Deuflhard {[}Comp. Math. Appl. 29 (1995) 53-76{]} and Schmidt and Yevick {[}J. Comput. Phys. 134 (1997) 96-107{]} to propagation methods based on arbitrary Pad\'e approximations to the two-dimensional one-way Helmholtz equation. Our approach leads to a recursive formula for the coefficients appearing in the nonlocal condition which then yields an unconditionally stable propagation method.}, language = {en} } @misc{BengerHegeMerzkyetal.1999, author = {Benger, Werner and Hege, Hans-Christian and Merzky, Andre and Radke, Thomas and Seidel, Edward}, title = {Efficient Distributed File I/O for Visualization in Grid Environments}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4326}, number = {SC-99-43}, year = {1999}, abstract = {Large scale simulations running in metacomputing environments face the problem of efficient file I/O. For efficiency it is desirable to write data locally, distributed across the computing environment, and then to minimize data transfer, i.e.\ reduce remote file access. Both aspects require I/O approaches which differ from existing paradigms. For the data output of distributed simulations, one wants to use fast local parallel I/O for all participating nodes, producing a single distributed logical file, while keeping changes to the simulation code as small as possible. For reading the data file as in postprocessing and file based visualization, one wants to have efficient partial access to remote and distributed files, using a global naming scheme and efficient data caching, and again keeping the changes to the postprocessing code small. However, all available software solutions require the entire data to be staged locally (involving possible data recombination and conversion), or suffer from the performance problems of remote or distributed file systems. In this paper we show how to interface the HDF5 I/O library via its flexible Virtual File Driver layer to the Globus Data Grid. We show, that combining these two toolkits in a suitable way provides us with a new I/O framework, which allows efficient, secure, distributed and parallel file I/O in a metacomputing environment.}, language = {en} } @misc{PowellWeiser1999, author = {Powell, Gary and Weiser, Martin}, title = {Container Adaptors}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4308}, number = {SC-99-41}, year = {1999}, abstract = {The C++ standard template library has many useful containers for data. The standard library includes two adpators, queue, and stack. The authors have extended this model along the lines of relational database semantics. Sometimes the analogy is striking, and we will point it out occasionally. An adaptor allows the standard algorithms to be used on a subset or modification of the data without having to copy the data elements into a new container. The authors provide many useful adaptors which can be used together to produce interesting views of data in a container.}, language = {en} } @misc{Galliat1999, author = {Galliat, Tobias}, title = {Clustering Data of Different Information Levels}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4319}, number = {SC-99-42}, year = {1999}, abstract = {For using Data Mining, especially cluster analysis, one needs measures to determine the similarity or distance between data objects. In many application fields the data objects can have different information levels. In this case the widely used euclidean distance is an inappropriate measure. The present paper describes a concept how to use data of different information levels in cluster analysis and suggests an appropriate similarity measure. An example from practice is included, that shows the usefulness of the concept and the measure in combination with {\sc Kohonens} Self-Organizing Map algorithm, a well-known and powerful tool for cluster analysis.}, language = {en} } @misc{Beck1999, author = {Beck, Rudolf}, title = {Algebraic Multigrid by Component Splitting for Edge Elements on Simplicial Triangulations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4290}, number = {SC-99-40}, year = {1999}, abstract = {Our focus is on Maxwell's equations in the low frequency range; two specific applications we aim at are time-stepping schemes for eddy current computations and the stationary double-curl equation for time-harmonic fields. We assume that the computational domain is discretized by triangles or tetrahedrons; for the finite element approximation we choose N\'{e}d\'{e}lec's \$H(curl)\$-conforming edge elements of the lowest order. For the solution of the arising linear equation systems we devise an algebraic multigrid preconditioner based on a spatial component splitting of the field. Mesh coarsening takes place in an auxiliary subspace, which is constructed with the aid of a nodal vector basis. Within this subspace coarse grids are created by exploiting the matrix graphs. Additionally, we have to cope with the kernel of the \$curl\$-operator, which comprises a considerable part of the spectral modes on the grid. Fortunately, the kernel modes are accessible via a discrete Helmholtz decomposition of the fields; they are smoothed by additional algebraic multigrid cycles. Numerical experiments are included in order to assess the efficacy of the proposed algorithms.}, language = {en} } @misc{SchmidtEhrenbergHege1999, author = {Schmidt-Ehrenberg, Johannes and Hege, Hans-Christian}, title = {Visualizing Quantum Mechanical Phenomena}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4287}, number = {SC-99-39}, year = {1999}, abstract = {In this paper we discuss several ways to visualize stationary and non-stationary quantum mechanical systems. We demonstrate an approach for the quantitative interpretation of probability density isovalues which yields a reasonable correlation between isosurfaces for different timesteps. As an intuitive quantity for visualizing the momentum of a quantum system we propose the probability flow density which can be treated by vector field visualization techniques. Finally, we discuss the visualization of non-stationary systems by a sequence of single timestep images.}, language = {en} } @misc{GalliatHuisingaDeuflhard1999, author = {Galliat, Tobias and Huisinga, Wilhelm and Deuflhard, Peter}, title = {Self-Organizing Maps Combined with Eigenmode Analysis for Automated Cluster Identification}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4279}, number = {SC-99-38}, year = {1999}, abstract = {One of the important tasks in Data Mining is automated cluster analysis. Self-Organizing Maps (SOMs) introduced by {\sc Kohonen} are, in principle, a powerful tool for this task. Up to now, however, its cluster identification part is still open to personal bias. The present paper suggests a new approach towards automated cluster identification based on a combination of SOMs with an eigenmode analysis that has recently been developed by {\sc Deuflhard et al.} in the context of molecular conformational dynamics. Details of the algorithm are worked out. Numerical examples from Data Mining and Molecular Dynamics are included.}, language = {en} } @misc{HelmbergKiwiel1999, author = {Helmberg, Christoph and Kiwiel, K.C.}, title = {A Spectral Bundle Method with Bounds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4256}, number = {SC-99-37}, year = {1999}, abstract = {Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality. However, solving them by primal-dual interior point methods can take much time even for problems of moderate size. The recent spectral bundle method of Helmberg and Rendl can solve quite efficiently large structured equality-constrained semidefinite programs if the trace of the primal matrix variable is fixed, as happens in many applications. We extend the method so that it can handle inequality constraints without seriously increasing computation time. Encouraging preliminary computational results are reported.}, language = {en} } @misc{SchuetteHuisingaDeuflhard1999, author = {Sch{\"u}tte, Christof and Huisinga, Wilhelm and Deuflhard, Peter}, title = {Transfer Operator Approach to Conformational Dynamics in Biomolecular Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4247}, number = {SC-99-36}, year = {1999}, abstract = {The article surveys the development of novel mathematical concepts and algorithmic approaches based thereon in view of their possible applicability to biomolecular design. Both a first deterministic approach, based on the Frobenius-Perron operator corresponding to the flow of the Hamiltonian dynamics, and later stochastic approaches, based on a spatial Markov operator or on Langevin dynamics, can be subsumed under the unified mathematical roof of the transfer operator approach to effective dynamics of molecular systems. The key idea of constructing specific transfer operators especially taylored for the purpose of conformational dynamics appears as the red line throughout the paper. Different steps of the algorithm are exemplified by a trinucleotide molecular system as a small representative of possible RNA drug molecules.}, language = {en} } @misc{LinkeKrebsSchuenemann1999, author = {Linke, Matthias and Krebs, Carsten and Sch{\"u}nemann, Marion}, title = {Metacomputing zwischen Berlin und Rostock}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4239}, number = {SC-99-35}, year = {1999}, abstract = {Das Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin (ZIB) und das Rechenzentrum der Universit{\"a}t Rostock, beide Einrichtungen betreiben massiv-parallele Rechner vom Typ CRAY T3E, haben sich an Hand einer Anwendung aus dem Bereich der Botanik mit den M{\"o}glichkeiten der Verteilung auf zwei Parallelrechner, gekoppelt nur {\"u}ber das Breitband-Wissenschaftsnetz des Deutschen Forschungsnetzes, vertraut gemacht. Das Projekt besteht aus zwei Teilen. Im ersten Teil wird ausf{\"u}hrlich das zwischen den Rechnern liegende Netz und die Ergebnisse einer Performanceanalyse dieses Netzes dokumentiert. Der zweite Teil beschreibt die Anwendung "Simulation des Wachstums von Pflanzen"' sowie die Ergebnisse der Verteilung dieser Anwendung auf beide Rechner. \begin{center} \bf{Abstract} \end{center} The "'Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin"' (ZIB) and the Computing Centre of the University of Rostock operate high-performance computers of type CRAY T3E. In this project an application from the area of the botany is distributed on two parallel computers, only coupled through the Broadband Science Network of the German Research Network (DFN). This project consists of two parts. In the first part the network which is situated between the computers and the results of a performance analysis is documented in detail. The second part describes the application "'Simulation of the growth of plants"' as well as the results of the distribution of this application to both computers.}, language = {de} } @misc{Deuflhard1999, author = {Deuflhard, Peter}, title = {Differential Equations in Technology and Medicine. Computational Concepts, Adaptive Algorithms, and Virtual Labs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4223}, number = {SC-99-34}, year = {1999}, abstract = {This series of lectures has been given to a class of mathematics postdocs at a European summer school on Computational Mathematics Driven by Industrial Applications in Martina Franca, Italy (organized by CIME). It deals with a variety of challenging real life problems selected from clinical cancer therapy, communication technology, polymer production, and pharmaceutical drug design. All of these problems from rather diverse application areas share two common features: (a) they have been modelled by various differential equations -- elliptic, parabolic, or Schr{\"o}dinger--type partial differential equations, countable ordinary diffential equations, or Hamiltonian systems, (b) their numerical solution has turned out to be real challenge to computational mathematics.}, language = {en} } @misc{ZoecklerStallingHege1999, author = {Z{\"o}ckler, Malte and Stalling, Detlev and Hege, Hans-Christian}, title = {Fast and Intuitive Generation of Geometric Shape Transitions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4219}, number = {SC-99-33}, year = {1999}, abstract = {We describe a novel method for continuously transforming two triangulated models of arbitrary topology into each other. Equal global topology for both objects is assumed, extensions for genus changes during metamorphosis are provided. The proposed method addresses the major challenge in 3D metamorphosis, namely specifying the morphing process intuitively, with minimal user interaction and sufficient detail. Corresponding regions and point features are interactively identified. These regions are parametrized automatically and consistently, providing a basis for smooth interpolation. Utilizing suitable 3D interaction techniques a simple and intuitive control over the whole morphing process is offered.}, language = {en} } @misc{BorndoerferGroetschelLoebel1999, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Der Schnellste Weg zum Ziel}, doi = {10.1007/978-3-322-96366-6_5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4209}, number = {SC-99-32}, year = {1999}, abstract = {Wir geben eine Einf{\"u}hrung in die Mathematik von und mit Wegen. Nicht auf dem k{\"u}rzesten, aber auf einem hoffentlich kurzweiligen Weg!}, language = {de} } @misc{Steinbach1999, author = {Steinbach, Marc}, title = {Markowitz Revisited: Single-Period and Multi-Period Mean-Variance Models}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4183}, number = {SC-99-30}, year = {1999}, abstract = {Mean-variance portfolio analysis provided the first quantitative treatment of the tradeoff between profit and risk. We investigate in detail the interplay between objective and constraints in a number of single-period variants, including semi-variance models. Particular emphasis is laid on avoiding the penalization of overperformance. The results are then used as building blocks in the development and theoretical analysis of multi-period models based on scenario trees. A key property is the possibility to remove surplus money in future decisions, yielding approximate downside risk minimization.}, language = {en} } @misc{AscheuerFischettiGroetschel1999, author = {Ascheuer, Norbert and Fischetti, Matteo and Gr{\"o}tschel, Martin}, title = {Solving the Asymmetric Travelling Salesman Problem with Time Windows by Branch-and-Cut}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4191}, number = {SC-99-31}, year = {1999}, abstract = {Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point of view. The real--world application we aim at is the control of a stacker crane in a warehouse. We have implemented codes based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms the other two models we considered --- at least for our special application --- and that the heuristics provide acceptable solutions.}, language = {en} } @misc{IlgenfritzKerlerStueben1999, author = {Ilgenfritz, Ernst-Michael and Kerler, Werner and St{\"u}ben, Hinnerk}, title = {Decorrelation of the topological charge in tempered Hybrid Monte Carlo simulations of QCD}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4168}, number = {SC-99-28}, year = {1999}, abstract = {We study the improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering. As an indicator for decorrelation we use the topological charge.}, language = {en} } @misc{GroetschelKrumkeRambau1999, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Wo bleibt der Aufzug?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4175}, number = {SC-99-29}, year = {1999}, abstract = {Dieser Artikel gibt eine allgemeinverst{\"a}ndliche Einf{\"u}hrung in die spezielle Problematik kombinatorischer Online-Problem am Beispiel der Fahrstuhlsteuerung.}, language = {de} } @misc{SchuetteHuisinga1999, author = {Sch{\"u}tte, Christof and Huisinga, Wilhelm}, title = {On Conformational Dynamics induced by Langevin Processes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4130}, number = {SC-99-25}, year = {1999}, abstract = {The function of many important biomolecules is related to their dynamic properties and their ability to switch between different {\em conformations}, which are understood as {\em almost invariant} or {\em metastable} subsets of the positional state space of the system. Recently, the present authors and their coworkers presented a novel algorithmic scheme for the direct numerical determination of such metastable subsets and the transition probability between them. Although being different in most aspects, this method exploits the same basic idea as {\sc Dellnitz} and {\sc Junge} in their approach to almost invariance in discrete dynamical systems: the almost invariant sets are computed via certain eigenvectors of the Markov operators associated with the dynamical behavior. In the present article we analyze the application of this approach to (high--friction) Langevin models describing the dynamical behavior of molecular systems coupled to a heat bath. We will see that this can be related to theoretical results for (symmetric) semigroups of Markov operators going back to {\sc Davies}. We concentrate on a comparison of our approach in respect to random perturbations of dynamical systems.}, language = {en} } @phdthesis{Gatermann1999, author = {Gatermann, Karin}, title = {Computer Algebra Methods for Equivariant Dynamical Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4140}, number = {SC-99-26}, year = {1999}, abstract = {An introductory chapter on Groebner bases is given which also includes new results on the detection of Groebner bases for sparse polynomial systems. Algorithms for the computation of invariants and equivariants for finite groups, compact Lie groups and algebraic groups are presented and efficient implementation and time comparision are discussed. This chapter also inlcudes improvements of the computation of Noether normalisation and Stanley decomposition. These results are applied in symmetric bifurcation theory and equivariant dynamics. As preparation of the investigation of the orbit space reduction three methods are compared for solving symmetric polynomial systems exactly. The method of orbit space reduction is improved by using the Cohen-Macaulayness of the invariant ring and nested Noether normalization. Finally this is applied for a case of mode interaction in the Taylor-Couette problem.}, language = {en} } @misc{GatermannHuber1999, author = {Gatermann, Karin and Huber, Birkett}, title = {A family of sparse polynomial systems arising in chemical reaction systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4150}, number = {SC-99-27}, year = {1999}, abstract = {A class of sparse polynomial systems is investigated which is defined by a weighted directed graph and a weighted bipartite graph. They arise in the model of mass action kinetics for chemical reaction systems. In this application the number of real positive solutions within a certain affine subspace is of particular interest. We show that the simplest cases are equivalent to binomial systems while in general the solution structure is highly determined by the properties of the two graphs. First we recall results by Feinberg and give rigorous proofs. Secondly, we explain how the graphs determine the Newton polytopes of the system of sparse polynomials and thus determine the solution structure. The results on positive solutions from real algebraic geometry are applied to this particular situation. Examples illustrate the theoretical results.}, language = {en} } @misc{GroetschelDalitz1999, author = {Gr{\"o}tschel, Martin and Dalitz, Wolfgang}, title = {Math-Net Abschlussbericht}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4120}, number = {SC-99-24}, year = {1999}, abstract = {Das Math-Net ist ein verteiltes Informationssystem f"ur die Mathematik. Es basiert auf den lokalen Informationsangeboten der Fachbereiche, die im Math-Net integriert, nutzerfreundlich aufbereitet und zug"anglich gemacht werden sollen. Das Math-Net ist durch die freiwillige Mitarbeit weiterer Institutionen in Deutschland zu einem fl{\"a}chendeckenden Dienst ausgebaut worden. Die am Projekt beteiligten Institutionen haben die mathematischen Institutionen in ihrer Region beim Aufbau eines qualitativ hochwertigen lokalen Informationsangebotes unterst{\"u}tzt und die Integration der lokalen Informationsangebote in das Math-Net koordiniert.}, language = {de} } @misc{Meyer1999, author = {Meyer, Michael}, title = {Ab Initio Study of Flavonoids}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4110}, number = {SC-99-23}, year = {1999}, abstract = {Flavone and the flavylium ion have been studied at Hartree-Fock, M{\o}ller-Plesset and B3LYP hybrid density functional level to determine the structures and barriers to internal rotation. Both molecules have a high perpendicular barrier about the single bond connecting the phenyl ring with the benzopyrone and benzopyrylium ring, respectively. In contrast to biphenyl both molecules have low coplanar barriers. B3LYP overestimates the perpendicular barrier heights compared to other methods. The dependence of the population and orbital energies on the torsion has been investigated and the structures of both flavonoids have been estimated by means of a reaction field model.}, language = {en} } @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{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} } @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{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{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{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} } @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{BackhausSchmidtDantus1999, author = {Backhaus, Peter and Schmidt, Burkhard and Dantus, Marcos}, title = {Control of photoassociation yield: A quantum-dynamical study of the mercury system to explore the role of pulse duration from nanoseconds to femtoseconds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4001}, number = {SC-99-12}, year = {1999}, abstract = {The photoassociation process shows strong dependence on the temporal duration of the electromagnetic field pulses and their frequencies. This dependence is investigated using quantum mechanical simulations that include all ranges of impact parameters and contributions from bound-to-bound transitions. The photoassociation yield of mercury atoms to produce excimer dimers is enhanced for short (ps) and for ultrashort (fs) pulse durations. Ultrashort laser pulses effectively overlap the entire range of free-to-bound transition, therefore achieving a maximum probability. Short pulses show a maximum in the photoassociation yield when their carrier frequency overlaps a particular free-to-bound spectroscopic resonance. Implications of these calculations on efforts to control bimolecular reactions are discussed.}, language = {en} } @misc{OPUS4-973, title = {Jahresbericht 1998}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9731}, number = {1998}, year = {1999}, language = {de} } @misc{SchmidtZdanska1999, author = {Schmidt, Burkhard and Zdanska, Petra}, title = {Solution of the Time-Dependent Schroedinger Equation for Highly Symmetric Potentials}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3996}, number = {SC-99-11}, year = {1999}, abstract = {The method of symmetry adapted wavepackets (SAWP) to solve the time-dependent Schr{\"o}dinger equation for a highly symmetric potential energy surface is introduced. The angular dependence of a quantum-mechanical wavepackets is expanded in spherical harmonics where the number of close-coupled equations for the corresponding radial functions can be efficiently reduced by symmetry adaption of the rotational basis using the SWAP approach. Various techniques to generate symmetry adapted spherical harmonics (SASHs) for the point groups of highest symmetry (octahedral, icosahedral) are discussed. The standard projection operator technique involves the use of Wigner rotation matrices. Two methods to circumvent numerical instabilities occuring for large azimuthal quantum numbers are suggested. The first is based on a numerical scheme which employs Gaussian integrations yielding exact and stable results. The second is a recursive algorithm to generate higher order SASHs accurately and efficiently from lower order ones. The paper gives a complete set of ``seed functions'' generated by projection techniques which can be used obtain SASHs for all irreducible representations of the octahedral and icosahedral point groups recursively.}, language = {en} } @misc{Schuette1999, author = {Sch{\"u}tte, Christof}, title = {Partial Wigner Transforms and the Quantum--Classical Liouville Equation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3983}, number = {SC-99-10}, year = {1999}, abstract = {In molecular dynamics applications there is a growing interest in mixed quantum-classical models. The {\em quantum-classical Liouville equation} (QCL) describes most atoms of the molecular system under consideration by means of classical phase space density but an important, small portion of the system by means of quantum mechanics. The QCL is derived from the full quantum dynamical (QD) description by applying the Wigner transform to the classical part'' of the system only. We discuss the conditions under which the QCL model approximates the full QD evolution of the system. First, analysis of the asymptotic properties of the Wigner transform shows that solving the QCL yields a first order approximation of full quantum dynamics. Second, we discuss the adiabatic limit of the QCL. This discussion shows that the QCL solutions may be interpretated as classical phase space densities, at least near the adiabatic limit. Third, it is demonstrated that the QCL yields good approximations of {\em non-adiabatic quantum effects,} especially near so-called {\em avoided crossings} where most quantum-classical models fail.}, language = {en} } @misc{HauptmeierKrumkeRambau1999, author = {Hauptmeier, Dietrich and Krumke, Sven and Rambau, J{\"o}rg}, title = {The Online Dial-a-Ride Problem under Reasonable Load}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3961}, number = {SC-99-08}, year = {1999}, abstract = {In this paper, we analyze algorithms for the online dial-a-ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride problem is reasonable if the requests that come up in a sufficiently large time period can be served in a time period of at most the same length. This new notion is a stability criterion implying that the system is not overloaded. The new concept is used to analyze the online dial-a-ride problem for the minimization of the maximal resp.\ average flow time. Under reasonable load it is possible to distinguish the performance of two particular algorithms for this problem, which seems to be impossible by means of classical competitive analysis.}, language = {en} } @misc{GroetschelHauptmeierKrumkeetal.1999, author = {Gr{\"o}tschel, Martin and Hauptmeier, Dietrich and Krumke, Sven and Rambau, J{\"o}rg}, title = {Simulation Studies for the Online-Dial-a-Ride Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3976}, number = {SC-99-09}, year = {1999}, abstract = {In a large distribution center of Herlitz AG, Berlin, we invesigated the elevator subsystem of the fully automated pallet transportation system. Each elevator may carry one pallet and has to serve eight levels. The goal is to minimize the average resp.\ the maximum flow time. The variants of this elevator control problem have been subject of recent theoretical research and are known as online-dial-a-ride problems. In this paper we investigate several online algorithms for several versions of online-dial-a-ride problems by means of a simulation program, developed on the basis of the simulation library AMSEL. We draw statistics from samples of randomly generated data providing for different load situations. Moreover, we provide preliminary studies with real production data for a system of five elevators connected by a conveyor circuit, as can be found at the Herlitz plant. We show which algorithms are best under certain load situations and which lead to break downs under particular circumstances.}, language = {en} } @misc{BraessDeuflhardLipnikov1999, author = {Braess, Dietrich and Deuflhard, Peter and Lipnikov, Konstantin}, title = {A Subspace Cascadic Multigrid Method for Mortar Elements}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3954}, number = {SC-99-07}, year = {1999}, abstract = {A cascadic multigrid (CMG) method for elliptic problems with strong material jumps is proposed and analyzed. Non--matching grids at interfaces between subdomains are allowed and treated by mortar elements. The arising saddle point problems are solved by a subspace confined conjugate gradient method as smoother for the CMG. Details of algorithmic realization including adaptivity are elaborated. Numerical results illustrate the efficiency of this CMG algorithm.}, language = {en} } @misc{HauptmeierKrumkeRambauetal.1999, author = {Hauptmeier, Dietrich and Krumke, Sven and Rambau, J{\"o}rg and Wirth., Hans-Christoph}, title = {Euler is Standing in Line}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3947}, number = {SC-99-06}, year = {1999}, abstract = {In this paper we study algorithms for ``Dial-a-Ride'' transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and an approximation algorithm on general graphs with a performance of~\$9/4\$. For trees we improve the performance to~\$5/3\$.}, language = {en} } @misc{LohrumSchneiderWillenborg1999, author = {Lohrum, Stefan and Schneider, Wolfram and Willenborg, Josef}, title = {De-duplication in KOBV}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3931}, number = {SC-99-05}, year = {1999}, abstract = {In KOBV we offer the user an efficient tool for searching regional and worldwide accessible library catalogues (KOBV search engine). Search is performed by a distributed Z39.50 retrieval and an index based quicksearch. Due to the number of catalogues, result sets may contain a significant amount of duplicate records. Therefore we integrate a de-duplication procedure into KOBV search engine. It is part of the distributed search and the KOBV quicksearch as well. Main goals are the presentation of uniform retrieval results, the preservation of retrieval quality and cutting off redundant information. At least we keep an eye on efficiency. De-duplication is fully parametrizable, so that settings can be changed easily on line.}, language = {en} } @misc{SeewaldPolleiKraumeetal.1999, author = {Seewald, Frank and Pollei, Anja and Kraume, Matthias and Mittelbach, Walter and Lang., Jens}, title = {Numerical Calculation of the Heat Transfer in an Adsorption Energy Storage with KARDOS}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3927}, number = {SC-99-04}, year = {1999}, abstract = {A new seasonal energy storage for thermal solar systems has been developed on the basis of an adsorption-desorption process. Design and optimization of this storage will be supported by numerical simulations of heat and mass transfer with KARDOS. This paper focuses on the unsteady heat transfer during the major operating step of energetic discharge of the storage, which is characterized by conductive heat transfer in the fixed bed and a strong heat source caused by the adsorption enthalpy. Results are interpreted concerning the influence of variations in the parameter set. The method of implementation of the differential equation will be shown as well as the post-processing and gridwriting programs.}, language = {en} } @phdthesis{Martin1999, author = {Martin, Alexander}, title = {Integer Programs with Block Structure}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3911}, number = {SC-99-03}, year = {1999}, abstract = {In this thesis we study and solve integer programs with block structure, i.\,e., problems that after the removal of certain rows (or columns) of the constraint matrix decompose into independent subproblems. The matrices associated with each subproblem are called blocks and the rows (columns) to be removed linking constraints (columns). Integer programs with block structure come up in a natural way in many real-world applications. The methods that are widely used to tackle integer programs with block structure are decomposition methods. The idea is to decouple the linking constraints (variables) from the problem and treat them at a superordinate level, often called master problem. The resulting residual subordinate problem then decomposes into independent subproblems that often can be solved more efficiently. Decomposition methods now work alternately on the master and subordinate problem and iteratively exchange information to solve the original problem to optimality. In Part I we follow a different approach. We treat the integer programming problem as a whole and keep the linking constraints in the formulation. We consider the associated polyhedra and investigate the polyhedral consequences of the involved linking constraints. The variety and complexity of the new inequalities that come into play is illustrated on three different types of real-world problems. The applications arise in the design of electronic circuits, in telecommunication and production planning. We develop a branch-and-cut algorithm for each of these problems, and our computational results show the benefits and limits of the polyhedral approach to solve these real-world models with block structure. Part II of the thesis deals with general mixed integer programming problems, that is integer programs with no apparent structure in the constraint matrix. We will discuss in Chapter 5 the main ingredients of an LP based branch-and-bound algorithm for the solution of general integer programs. Chapter 6 then asks the question whether general integer programs decompose into certain block structures and investigate whether it is possible to recognize such a structure. The remaining two chapters exploit information about the block structure of an integer program. In Chapter 7 we parallelize parts of the dual simplex algorithm, the method that is commonly used for the solution of the underlying linear programs within a branch-and-cut algorithm. In Chapter 8 we try to detect small blocks in the constraint matrix and to derive new cutting planes that strengthen the integer programming formulation. These inequalities may be associated with the intersection of several knapsack problems. We will see that they significantly improve the quality of the general integer programming solver introduced in Chapter 5.}, language = {en} } @misc{HuberRambauSantos1999, author = {Huber, Birkett and Rambau, J{\"o}rg and Santos, Francisco}, title = {The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3874}, number = {SC-98-44}, year = {1999}, abstract = {In 1994, Sturmfels gave a polyhedral version of the Cayley Trick of elimination theory: he established an order-preserving bijection between the posets of \emph{coherent} mixed subdivisions of a Minkowski sum \$\mathcal{A}_1+\cdots+\mathcal{A}_r\$ of point configurations and of \emph{coherent} polyhedral subdivisions of the associated Cayley embedding \$\mathcal{C}(\mathcal{A}_1,\dots,\mathcal{A}_r)\$. In this paper we extend this correspondence in a natural way to cover also \emph{non-coherent} subdivisions. As an application, we show that the Cayley Trick combined with results of Santos on subdivisions of Lawrence polytopes provides a new independent proof of the Bohne-Dress Theorem on zonotopal tilings. This application uses a combinatorial characterization of lifting subdivisions, also originally proved by Santos.}, language = {en} } @misc{AthanasiadisRambauSantos1999, author = {Athanasiadis, Christos A. and Rambau, J{\"o}rg and Santos, Francisco}, title = {The Generalized Baues Problem for Cyclic Polytopes II}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3862}, number = {SC-98-43}, year = {1999}, abstract = {Given an affine surjection of polytopes \$\pi: P \to Q\$, the Generalized Baues Problem asks whether the poset of all proper polyhedral subdivisions of \$Q\$ which are induced by the map \$\pi\$ has the homotopy type of a sphere. We extend earlier work of the last two authors on subdivisions of cyclic polytopes to give an affirmative answer to the problem for the natural surjections between cyclic polytopes \$\pi: C(n,d') \to C(n,d)\$ for all \$1 \leq d < d' < n\$.}, language = {en} } @misc{Decker1999, author = {Decker, Ingmar}, title = {A Picture-based Document Retrieval Service for the Electronic Visualization Library}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5689}, number = {TR-98-07}, year = {1999}, abstract = {This report describes the development of an experimental service for picture-based document retrieval for the Electronic Visualization Library (EVlib). The EVlib is a digital library for scientific visualization, established at the Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin (ZIB). The picture-based retrieval service allows users to look for documents by describing the pictures they contain. This query method was developed based on the assumption that (1) pictures often represent relevant parts of the contents of a document, and (2) pictures are often remembered well. A picture-based approach provides a new quality of accessing and exploring scientific literature. Motivation, concepts and realization of our service are outlined. Results of a user test are presented, too. The results indicate that this service can be used for searching and browsing the document collection in principle. On the other hand, problems were detected which can give fruitful hints for future work concerning document and image retrieval.}, language = {en} } @misc{SchuetteFischerHuisingaetal.1999, author = {Sch{\"u}tte, Christof and Fischer, Alexander and Huisinga, Wilhelm and Deuflhard, Peter}, title = {A Direct Approach to Conformational Dynamics based on Hybrid Monte Carlo}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3889}, number = {SC-98-45}, year = {1999}, abstract = {Recently, a novel concept for the computation of essential features of the dynamics of Hamiltonian systems (such as molecular dynamics) has been proposed. The realization of this concept had been based on subdivision techniques applied to the Frobenius--Perron operator for the dynamical system. The present paper suggests an alternative but related concept that merges the conceptual advantages of the dynamical systems approach with the appropriate statistical physics framework. This approach allows to define the phrase ``conformation'' in terms of the dynamical behavior of the molecular system and to characterize the dynamical stability of conformations. In a first step, the frequency of conformational changes is characterized in statistical terms leading to the definition of some Markov operator \$T\$ that describes the corresponding transition probabilities within the canonical ensemble. In a second step, a discretization of \$T\$ via specific hybrid Monte Carlo techniques is shown to lead to a stochastic matrix \$P\$. With these theoretical preparations, an identification algorithm for conformations is applicable. It is demonstrated that the discretization of \$T\$ can be restricted to few essential degrees of freedom so that the combinatorial explosion of discretization boxes is prevented and biomolecular systems can be attacked. Numerical results for the n-pentane molecule and the triribonucleotide adenylyl\emph{(3'-5')}cytidylyl\emph{(3'-5')}cytidin are given and interpreted.}, language = {en} } @misc{Wolf1999, author = {Wolf, Thomas}, title = {A comparison of four approaches to the calculation of conservation laws}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3896}, number = {SC-99-01}, year = {1999}, abstract = {The paper compares computational aspects of four approaches to compute conservation laws of single differential equations or systems of them, ODEs and PDEs. The only restriction, required by two of the four corresponding computer algebra programs, is that each DE has to be solvable for a leading derivative. Extra constraints may be given. Examples of new conservation laws include non-polynomial expressions, an explicit variable dependence and conservation laws involving arbitrary functions. Examples involve the following equations: Ito, Liouville, Burgers, Kadomtsev-Petviashvili, Karney-Sen-Chu-Verheest, Boussinesq, Tzetzeica, Benney.}, language = {en} } @misc{SokolovWolf1999, author = {Sokolov, Vladimir V. and Wolf, Thomas}, title = {A symmetry test for quasilinear coupled systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3901}, number = {SC-99-02}, year = {1999}, abstract = {It is well known that the following class of systems of evolution equations \begin{eqnarray} \label{nsgen} \cases{ u_{t}=u_{xx}+F(u,v,u_x,v_x),\cr v_{t}=-v_{xx}+G(u,v,u_x,v_x),\cr} \end{eqnarray} is very rich in integrable cases. The complete classification problem is very difficult. Here we consider only the most interesting (from our opinion) subclass of systems (1). Namely, we consider equations linear in all derivatives of the form \begin{eqnarray} \label{kvazgen} \cases{ u_t = u_{xx} + A_{1}(u,v) u_x + A_{2}(u,v) v_x + A_{0}(u,v)\cr v_t = - v_{xx} + B_{1}(u,v) v_x + B_{2}(u,v) u_x + B_{0}(u,v). \cr} \end{eqnarray} without any restrictions on the functions \$A_{i}(u,v), B_{i}(u,v)\$.}, language = {en} } @phdthesis{Friese1998, author = {Friese, Tilmann}, title = {Eine Mehrgitter-Methode zur L{\"o}sung des Eigenwertproblems der komplexen Helmholtzgleichung}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:188-1999000133}, year = {1998}, language = {en} } @phdthesis{Borndoerfer1998, author = {Bornd{\"o}rfer, Ralf}, title = {Aspects of Set Packing, Partitioning, and Covering}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10126}, year = {1998}, abstract = {Diese Dissertation befaßt sich mit ganzzahligen Programmen mit 0/1 Systemen: SetPacking-, Partitioning- und Covering-Probleme. Die drei Teile der Dissertation behandeln polyedrische, algorithmische und angewandte Aspekte derartiger Modelle.}, language = {en} } @misc{BestHege1998, author = {Best, Christoph and Hege, Hans-Christian}, title = {Visualizing conformations in molecular dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3859}, number = {SC-98-42}, year = {1998}, abstract = {The Monte Carlo simulation of the dynamics of complex molecules produces trajectories with a large number of different configurations to sample configuration space. It is expected that these configurations can be classified into a small number of conformations representing essential changes in the shape of the molecule. We present a method to visualize these conformations by point sets in the plane based on a geometrical distance measure between individual configurations. It turns out that different conformations appear as well-separated point sets. The method is further improved by performing a cluster analysis of the data set. The point-cluster representation is used to control a three-dimensional molecule viewer application to show individual configurations and conformational changes. The extraction of essential coordinates and visualization of molecular shape is discussed.}, language = {en} } @misc{Best1998, author = {Best, Christoph}, title = {A simple C++ library for manipulating scientific data sets as structured data}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5674}, number = {TR-98-06}, year = {1998}, abstract = {Representing scientific data sets efficiently on external storage usually involves converting them to a byte string representation using specialized reader/writer routines. The resulting storage files are frequently difficult to interpret without these specialized routines as they do not contain information about the logical structure of the data. Avoiding such problems usually involves heavy-weight data format libraries or data base systems. We present a simple C++ library that allows to create and access data files that store structured data. The structure of the data is described by a data type that can be built from elementary data types (integer and floating-point numbers, byte strings) and composite data types (arrays, structures, unions). An abstract data access class presents the data to the application. Different actual data file structures can be implemented under this layer. This method is particularly suited to applications that require complex data structures, e.g. molecular dynamics simulations. Extensions such as late type binding and object persistence are discussed.}, language = {en} } @misc{BorndoerferLoebelStrubbeetal.1998, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Strubbe, Uwe and V{\"o}lker, Manfred}, title = {Zielorientierte Dienstplanoptimierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3847}, number = {SC-98-41}, year = {1998}, abstract = {Dieser Artikel behandelt einen Ansatz zur zielorientierten Optimierung der Dienstplanung im {\"O}PNV. Der Ansatz zielt auf die vollst{\"a}ndige Ausnutzung aller planerischen Freiheitsgrade unter korrekter Ber{\"u}cksichtigung von gesetzlichen, tariflichen, technischen und betrieblichen Rahmenbedingungen. Er basiert auf mathematischen Optimierungstechniken, die wir gegenw{\"a}rtig in einem vom Bundesministerium f{\"u}r Bildung und Forschung ({\tt bmb+f}) gef{\"o}rderten Verbundprojekt in einer Kooperation zwischen der HanseCom GmbH, der IVU GmbH und dem Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin entwickeln. Es ist geplant, das Verfahren in die Softwareprodukte HOT II, MICROBUS II und OPUS zu integrieren. Verhandlungen mit den Berliner Verkehrsbetrieben {\"u}ber eine Projektbeteiligung und Integration unserer Software in BERTA sind zur Zeit im Gang. Wir beschreiben die Methodik des Ansatzes, diskutieren Aspekte seiner praktischen Verwendung, und wir berichten {\"u}ber den Stand der Entwicklung.}, language = {de} } @misc{StallingZoecklerSanderetal.1998, author = {Stalling, Detlev and Z{\"o}ckler, Malte and Sander, Oliver and Hege, Hans-Christian}, title = {Weighted Labels for 3D Image Segmentation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3828}, number = {SC-98-39}, year = {1998}, abstract = {Segmentation tools in medical imaging are either based on editing geometric curves or on the assignment of region labels to image voxels. While the first approach is well suited to describe smooth contours at subvoxel accuracy, the second approach is conceptually more simple and guarantees a unique classification of image areas. However, contours extracted from labeled images typically exhibit strong staircase artifacts and are not well suited to represent smooth tissue boundaries. In this paper we describe how this drawback can be circumvented by supplementing region labels with additional weights. We integrated our approach into an interactive segmentation system providing a well-defined set of manual and semi-automatic editing tools. All tools update both region labels as well as the corresponding weights simultaneously, thus allowing one to define segmentation results at high resolution. We applied our techniques to generate 3D polygonal models of anatomical structures.}, language = {en} } @phdthesis{Stalling1998, author = {Stalling, Detlev}, title = {Fast Texture-Based Algorithms for Vector Field Visualization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3838}, number = {SC-98-40}, year = {1998}, abstract = {In this thesis we develop new methods for visualizing vector fields which specifically address three design goals: accuracy, performance, and cognition. Our methods will be general-purpose and can be applied to arbitrary vector fields in two- and three-dimensional space. The methodology behind our approach is {\em texture-based visualization}. Texture-based visualization methods imitate techniques known from experimental flow visualization, namely, the observation of randomly dispersed particles or dye injection patterns. Instead of depicting individual lines or symbols, a contiguous high-resolution image or texture is generated. This texture clearly reveals the directional structure of the field. In this way intuitive insight can be obtained and even small details of the field become visible. However, it remains unclear what kind of textures are best suited for our purpose. How do we generate them? Can we apply these methods in three-dimensional space? In particular, we focus on a technique known as {\em line integral convolution} or LIC. This method turns out to be quite versatile and well-suited for visualizing many interesting vector fields. LIC images display the integral curves or field lines of a vector field at high spatial resolution. Although conceptually quite simple, line integral convolution implies a number of interesting mathematical and algorithmic questions.}, language = {en} } @misc{KedziorskiKehlPaetsch1998, author = {Kedziorski, Rafal and Kehl, Detlef and Paetsch, Olaf}, title = {Client-Server-Anwendung zur Steuerung von Ausgabeger{\"a}ten}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5658}, number = {TR-98-04}, year = {1998}, abstract = {\\{\bf Zusammenfassung: }\noindent Die Steuerung von grafischen Ausgabeger{\"a}ten erfordert oft mehr als ein oder zwei Optionen, wie man sie vom UNIX {\em lpr}-Kommando kennt. Hier bietet sich eine grafische Benutzungsschnittstelle zur {\"u}bersichtlichen Einstellung aller m{\"o}glichen Parameter und Optionen an. Wenn dieses Ger{\"a}t zudem nur {\"u}ber eine besondere Treiber-Software zu bedienen ist und in einem heterogenen Intranet zur Verf{\"u}gung gestellt werden soll, ist eine Steuerung mittels eines WWW-Servers naheliegend. Im Folgenden sollen L{\"o}sungsans{\"a}tze diskutiert werden, die auf HTML/CGI- bzw. Java-Basis derartige Steuerung realisieren. {\small} It is often the case that graphical output devices need more than one or two control options like the UNIX {\em lpr}-command. A driver programme with a graphical user interface (GUI) can satisfy this requirement. If such a device shall be accessible in an heterogenous network a solution using a WWW-server can be used. Possible HTML/CGI resp. Java-based solutions are discussed in the following.}, language = {de} } @misc{StallingSeebassZachow1998, author = {Stalling, Detlev and Seebass, Martin and Zachow, Stefan}, title = {Mehrschichtige Oberfl{\"a}chenmodelle zur computergest{\"u}tzten Planung in der Chirurgie}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5661}, number = {TR-98-05}, year = {1998}, abstract = {Polygonale Sch{\"a}delmodelle bilden ein wichtiges Hilfsmittel f{\"u}r computergest{\"u}tzte Planungen im Bereich der plastischen Chirurgie. Wir beschreiben, wie derartige Modelle automatisch aus hochaufgel{\"o}sten CT-Datens{\"a}tzen erzeugt werden k{\"o}nnen. Durch einen lokal steuerbaren Simplifizierungsalgorithmus werden die Modelle so weit vereinfacht, daß auch auf kleineren Graphikcomputern interaktives Arbeiten m{\"o}glich wird. Die Verwendung eines speziellen Transparenzmodells erm{\"o}glicht den ungehinderten Blick auf die bei der Planung relevanten Knochenstrukturen und l{\"a}ßt den Benutzer zugleich die Kopfumrisse des Patienten erkennen.}, language = {de} } @misc{SchuetteNettesheim1998, author = {Sch{\"u}tte, Christof and Nettesheim, Peter}, title = {Non-Adiabatic Effects in Quantum-Classical Molecular Dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3817}, number = {SC-98-38}, year = {1998}, abstract = {In molecular dynamics applications there is a growing interest in mixed quantum-classical models. The article is concerned with the so-called QCMD model. This model describes most atoms of the molecular system by the means of classical mechanics but an important, small portion of the system by the means of a wavefunction. We review the conditions under which the QCMD model is known to approximate the full quantum dynamical evolution of the system. In most quantum-classical simulations the {\em Born-Oppenheimer model} (BO) is used. In this model, the wavefunction is adiabatically coupled to the classical motion which leads to serious approximation deficiencies with respect to non-adiabatic effects in the fully quantum dynamical description of the system. In contrast to the BO model, the QCMD model does include non-adiabatic processes, e.g., transitions between the energy levels of the quantum system. It is demonstrated that, in mildly non-adiabatic scenarios, so-called {\em surface hopping} extensions of QCMD simulations yield good approximations of the non-adiabatic effects in full quantum dynamics. The algorithmic strategy of such extensions of QCMD is explained and the crucial steps of its realization are discussed with special emphasis on the numerical problems caused by highly oscillatory phase effects.}, language = {en} } @misc{Nettesheim1998, author = {Nettesheim, Peter}, title = {Second Order Transitions in Quantum-Classical Molecular Dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3805}, number = {SC-98-37}, year = {1998}, abstract = {Mixed quantum--classical models have attracted considerable interest due to the expectation that they correctly describe non--adiabatic processes of full quantum dynamics. One of these models, the so--called QCMD model, represents most degrees of freedom of the molecular system by the means of classical mechanics but an important, small portion of the system is modeled by a wavefunction: the wavefunction is nonlinearly coupled to the classical motion via a singularly perturbed Schr{\"o}dinger equation. In extension to the analysis given by F.A.~Bornemann [{\em Homogenization in Time of Singularly Perturbed Mechanical Systems}, Lecture Notes in Mathematics, no.~1687, 1998, Springer, Berlin], the article presents an asymptotic expansion up to second order in the perturbation parameter. This result allows for the construction of new models and numerical integration schemes.}, language = {en} } @misc{HuisingaBestCordesetal.1998, author = {Huisinga, Wilhelm and Best, Christoph and Cordes, Frank and Roitzsch, Rainer and Sch{\"u}tte, Christof}, title = {From Simulation Data to Conformational Ensembles: Structure and Dynamics based Methods}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3797}, number = {SC-98-36}, year = {1998}, abstract = {Statistical methods for analyzing large data sets of molecular configurations within the chemical concept of molecular conformations are described. The strategies are based on dependencies between configurations of a molecular ensemble; the article concentrates on dependencies induces by a) correlations between the molecular degrees of freedom, b) geometrical similarities of configurations, and c) dynamical relations between subsets of configurations. The statistical technique realizing aspect a) is based on an approach suggested by {\sc Amadei et al.} (Proteins, 17 (1993)). It allows to identify essential degrees of freedom of a molecular system and is extended in order to determine single configurations as representatives for the crucial features related to these essential degrees of freedom. Aspects b) and c) are based on statistical cluster methods. They lead to a decomposition of the available simulation data into {\em conformational ensembles} or {\em subsets} with the property that all configurations in one of these subsets share a common chemical property. In contrast to the restriction to single representative conformations, conformational ensembles include information about, e.g., structural flexibility or dynamical connectivity. The conceptual similarities and differences of the three approaches are discussed in detail and are illustrated by application to simulation data originating from a hybrid Monte Carlo sampling of a triribonucleotide.}, language = {en} } @misc{Kuberek1998, author = {Kuberek, Monika}, title = {Bibliothekarische Inhalte und Zielsetzungen des KOBV}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5646}, number = {TR-98-03}, year = {1998}, abstract = {Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) wurde 1997 auf politische Initiative hin gegr{\"u}ndet, um f{\"u}r die ressourcenreiche, aber elektronisch unzul{\"a}nglich erschlossene Bibliotheksregion Berlin-Brandenburg eine moderne Informationsinfrastruktur zu schaffen. Auf der Basis eines Expertengutachtens wird sowohl in technischer als auch in organisatorischer Hinsicht ein neues Kooperationsmodell entwickelt, das auf den Prinzipien der Dezentralisierung, Deregulierung und Kooperation beruht. Der vorliegende Artikel ist das Ergebnis einer bibliothekarischen Arbeitsgruppe des KOBV, die von Dezember 1997 bis M{\"a}rz 1998 das Modell des KOBV unter bibliothekarischen Gesichtspunkten diskutiert hat. Es werden erste Leitlinien festgelegt zu den Serviceleistungen des KOBV, zu den Prinzipien der Zusammenarbeit der Bibliotheken untereinander sowie zur Einbindung des Verbundes in das Bibliothekswesen der Bundesrepublik. Damit dient der Artikel zugleich der Positionsbestimmung des KOBV innerhalb des deutschen Bibliothekswesens.}, language = {de} } @misc{DeuflhardWeiserSeebass1998, author = {Deuflhard, Peter and Weiser, Martin and Seebass, Martin}, title = {A New Nonlinear Elliptic Multilevel FEM Applied to Regional Hyperthermia}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3785}, number = {SC-98-35}, year = {1998}, abstract = {In the clinical cancer therapy of regional hyperthermia nonlinear perfusion effects inside and outside the tumor seem to play a not negligible role. A stationary model of such effects leads to a nonlinear Helmholtz term within an elliptic boundary value problem. The present paper reports about the application of a recently designed adaptive multilevel FEM to this problem. For several 3D virtual patients, nonlinear versus linear model is studied. Moreover, the numerical efficiency of the new algorithm is compared with a former application of an adaptive FEM to the corresponding instationary model PDE.}, language = {en} } @misc{KuehnKorzenPaetsch1998, author = {K{\"u}hn, Wolfgang and Korzen, Manfred and Paetsch, Olaf}, title = {Fast Data Assimilation in Fire Tests of Steel Members}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3766}, number = {SC-98-33}, year = {1998}, abstract = {This report presents a fast data assimilation method to produce an interpolating time and space temperature distribution for steel members subject to fire testing. The method assimilates collected temperature data into the numerical integration of the heat equation. This physically based method also allows the computation of lateral and axial heat flux into and inside the member.}, language = {en} } @misc{AscheuerKrumkeRambau1998, author = {Ascheuer, Norbert and Krumke, Sven and Rambau, J{\"o}rg}, title = {The Online Transportation Problem: Competitive Scheduling of Elevators}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3779}, number = {SC-98-34}, year = {1998}, abstract = {In this paper we consider the following online transportation problem (\textsc{Oltp}): Objects are to be transported between the vertices of a given graph. Transportation requests arrive online, specifying the objects to be transported and the corresponding source and target vertex. These requests are to be handled by a server which commences its work at a designated origin vertex and which picks up and drops objects at their starts and destinations. After the end of its service the server returns to its start. The goal of \textsc{Oltp} is to come up with a transportation schedule for the server which finishes as early as possible. We first show a lower bound of~\$5/3\$ for the competitive ratio of any deterministic algorithm. We then analyze two simple and natural strategies which we call \textsf{REPLAN} and \textsf{IGNORE}. \textsf{REPLAN} completely discards its schedule and recomputes a new one when a new request arrives. \textsf{IGNORE} always runs a (locally optimal) schedule for a set of known requests and ignores all new requests until this schedule is completed. We show that both strategies, \textsf{REPLAN} and \textsf{IGNORE}, are \$5/2\$-competitive. We also present a somewhat less natural strategy \textsf{SLEEP}, which in contrast to the other two strategies may leave the server idle from time to time although unserved requests are known. We also establish a competitive ratio of~\$5/2\$ for the algorithm \textsf{SLEEP}. Our results are extended to the case of ``open schedules'' where the server is not required to return to its start position at the end of its service.}, language = {en} } @misc{Kuehn1998, author = {K{\"u}hn, Wolfgang}, title = {iTe 1.1 User's Guide}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5638}, number = {TR-98-02}, year = {1998}, abstract = {iTe is an easy to use, interactive authoring tool for LaTeX and TeX documents. With iTe, it is possible to select arbitrary display fragments such as figures, equations, labels, captions, etc. These fragments can then be freely moved, rotated and scaled.}, language = {en} } @misc{Schmidt1998, author = {Schmidt, Frank}, title = {An Alternative Derivation of the Exact DtN-Map on a Circle}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3752}, number = {SC-98-32}, year = {1998}, abstract = {The paper supplies an alternative derivation of the exact boundary conditions needed for the solution of time-harmonic acoustic scattering problems modeled by the Helmholtz equation. The main idea is to consider the exterior domain problem as an initial value problem with initial data given on the boundary of a disc or sphere. The solution of the exterior domain problem is obtained via Laplace transformation techniques, where the asymptotic Sommerfeld radiation condition is reformulated accordingly.}, language = {en} } @misc{SchneiderBottaGeratzetal.1998, author = {Schneider, Thomas and Botta, Nicola and Geratz, Karl Josef and Klein, Rupert}, title = {Extension of finite volume compressible flow solvers to multi-dimensional, variable density zero Mach number flow}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3749}, number = {SC-98-31}, year = {1998}, abstract = {When attempting to compute unsteady, variable density flows at very small or zero Mach number using a standard finite volume compressible flow solver one faces at least the following difficulties: (i) Spatial pressure variations vanish as the Mach number \$M \rightarrow 0\$, but they do affect the velocity field at leading order; (ii) the resulting spatial homogeneity of the leading order pressure implies an elliptic divergence constraint for the energy flux; (iii) violation of this constraint would crucially affect the transport of mass, thereby disabling a code to properly advect even a constant density distribution. A previous companion paper derived the above observations from a single time - multiple length scale asymptotic analysis for \$M \ll 1\$, applied to the conservation form of the governing equations and assuming an ideal gas with constant specific heats. The paper then restricted to weakly compressible one-dimensional flows and introduced a semi-implicit extension of a compressible flow solver, designed to handle the interaction of long wavelength acoustics with small scale, large amplitude density fluctuations. In the present paper we concentrate on the limit of zero Mach number for multi-dimensional, variable density flows. The construction of numerical fluxes for all conserved quantities involves: An explicit upwind step (1) yielding predictions for the nonlinear convective flux components. This procedure still neglects the influence of pressure gradients on the convective fluxes during the time step. Suitable corrections are applied in step (2), which guarantees compliance of the convective fluxes with the divergence constraint. This step requires the solution of a Poisson-type equation to obtain the relevant pressure gradients. Step (3), which requires the solution of a second Poisson-type equation, yields the yet unknown (non-convective) pressure contribution to the total flux of momentum. The final, cell centered velocity field exactly satisfies a discrete divergence constraint consistent with the asymptotic limit. Notice that step (1) can be done by any standard finite volume compressible flow solver and that the input to steps (2) and (3) involves solely the fluxes from step (1), but is independent on how these were obtained. Thus, we claim that our approach allows any such solver to be extended to simulate incompressible flows. Extensions to the weakly compressible regime \$0 < M \ll 1\$, reactive flows and more complex equations of state will be addressed in follow-up publications.}, language = {en} } @misc{DeuflhardSeebass1998, author = {Deuflhard, Peter and Seebass, Martin}, title = {Adaptive Multilevel FEM as Decisive Tools in the Clinical Cancer Therapy Hyperthermia}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3739}, number = {SC-98-30}, year = {1998}, abstract = {The paper surveys recent progress in a joint mathematical-medical project on cancer therapy planning. Within so-called regional hyperthermia the computational task is to tune a set of coupled radiofrequency antennas such that a carefully measured tumor is locally heated, but any outside hot spots are avoided. A mathematical model of the whole clinical system -- air, applicator with antennas, water bolus, individual patient body -- involves Maxwell's equations in inhomogeneous media and a parabolic bioheat transfer equation, which represents a simplified model of heat transfer in the human body (ignoring strong blood vessel heat transport). Both PDEs need to be computed fast and to medical reliability (!) on a workstation within a clinical environment. This requirement triggered a series of new algorithmic developments to be reported here, among which is an adaptive multilevel FEM for Maxwell's equations, which dominates the numerical simulation time. In total, however, the main bulk of computation time (see Table 3 in Section 4 below) still goes into segmentation -- a necessary preprocessing step in the construction a 3D virtual patient from the input of a stack of 2D computed tomograms (left out here).}, language = {en} } @misc{HuisingaPesceKosloffetal.1998, author = {Huisinga, Wilhelm and Pesce, Lorenzo and Kosloff, Ronnie and Saalfrank, Peter}, title = {Faber and Newton Polynomial Integrators for Open-System Density Matrix Propagation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3725}, number = {SC-98-29}, year = {1998}, abstract = {Two polynomial expansions of the time-evolution superoperator to directly integrate Markovian Liouville-von Neumann (LvN) equations for quantum open systems, namely the Newton interpolation and the Faber approximation, are presented and critically compared. Details on the numerical implementation including error control, and on the performance of either method are given. In a first physical application, a damped harmonic oscillator is considered. Then, the Faber approximation is applied to compute a condensed phase absorption spectrum, for which a semi--analytical expression is derived. Finally, even more general applications are discussed. In all applications considered here it is found that both the Newton and Faber integrators are fast, general, stable, and accurate.}, language = {en} } @misc{BrunsGubeladzeHenketal.1998, author = {Bruns, Winfried and Gubeladze, Joseph and Henk, Martin and Martin, Alexander and Weismantel, Robert}, title = {A counterexample to an integer analogue of Caratheodorys theorem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3718}, number = {SC-98-28}, year = {1998}, abstract = {For \$n\geq 6\$ we provide a counterexample to the conjecture that every integral vector of a \$n\$-dimensional integral polyhedral pointed cone \$C\$ can be written as a nonnegative integral combination of at most \$n\$ elements of the Hilbert basis of \$C\$. In fact, we show that in general at least \$\lfloor 7/6 \cdot n \rfloor\$ elements of the Hilbert basis are needed.}, language = {en} } @misc{Steinbach1998, author = {Steinbach, Marc}, title = {Recursive Direct Optimization and Successive Refinement in Multistage Stochastic Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3706}, number = {SC-98-27}, year = {1998}, abstract = {The paper presents a new algorithmic approach for multistage stochastic programs which are seen as discrete optimal control problems with a characteristic dynamic structure induced by the scenario tree. To exploit that structure, we propose a highly efficient dynamic programming recursion for the computationally intensive task of KKT systems solution within a primal-dual interior point method. Convergence is drastically enhanced by a successive refinement technique providing both primal and dual initial estimates. Test runs on a multistage portfolio selection problem demonstrate the performance of the method.}, language = {en} } @misc{GroetschelLuegger1998, author = {Gr{\"o}tschel, Martin and L{\"u}gger, Joachim}, title = {Scientific Information Systems and Metadata}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3698}, number = {SC-98-26}, year = {1998}, abstract = {This article begins with a short survey on the history of the classification of knowledge. It briefly discusses the traditional means of keeping track of scientific progress, i.e., collecting, classifying, abstracting, and reviewing all publications in a field. The focus of the article, however, is on modern electronic information and communication systems that try to provide high-quality information by automatic document retrieval or by using metadata, a new tool to guide search engines. We report, in particular, on efforts of this type made jointly by a number of German scientific societies. A full version of this paper including all hypertext references, links to online papers and references to the literature can be found under the URL: {\tt http://elib.zib.de/math.org.softinf.pub} .}, language = {en} } @misc{GroetschelDalitzWinczewski1998, author = {Gr{\"o}tschel, Martin and Dalitz, Wolfgang and Winczewski, Vincent}, title = {Math-Net: Ein Informationssystem der Mathematik}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3680}, number = {SC-98-25}, year = {1998}, abstract = {In diesem Artikel geben wir einen {\"U}berblick {\"u}ber das Math-Net-Projekt. Wir berichten {\"u}ber die organisatorischen und technischen Vorgehensweisen beim Aufbau eines verteilten Informationssystems f{\"u}r die Mathematik in Deutschland.}, language = {de} } @misc{AscheuerGroetschelKrumkeetal.1998, author = {Ascheuer, Norbert and Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Combinatorial Online Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3674}, number = {SC-98-24}, year = {1998}, abstract = {In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material.}, language = {en} } @misc{Steinbach1998, author = {Steinbach, Marc}, title = {Recursive Direct Algorithms for Multistage Stochastic Programs in Financial Engineering}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3661}, number = {SC-98-23}, year = {1998}, abstract = {Multistage stochastic programs can be seen as discrete optimal control problems with a characteristic dynamic structure induced by the scenario tree. To exploit that structure, we propose a highly efficient dynamic programming recursion for the computationally intensive task of KKT systems solution within an interior point method. Test runs on a multistage portfolio selection problem demonstrate the performance of the algorithm.}, language = {en} } @misc{LourencoRosaCastroetal.1998, author = {Lourenco, Maria Jos{\´e} and Rosa, Samuel Costa S. and Castro, Carlos Alberto Nieto de and Albuquerque, C. and Erdmann, Bodo and Lang, Jens and Roitzsch, Rainer}, title = {Simulation of the Transient Heating in an Unsymmetrical Coated Hot--Strip Sensor with a Self--Adaptive Finite Element Method}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3656}, number = {SC-98-22}, year = {1998}, abstract = {The transient heating in an unsymmetrical coated hot--strip sensor was simulated with a self--adaptive finite element method. The first tests of this model show that it can determine with a small error the thermal conductivity of liquids, from the transient temperature rise in the hot--strip, deposited in a substrate and coated by an alumina spray.}, language = {en} } @misc{BrandtBrandt1998, author = {Brandt, Andreas and Brandt, Manfred}, title = {On a Two-Queue Priority System with Impatience and its Application to a Call Center}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3641}, number = {SC-98-21}, year = {1998}, abstract = {We consider a \$s\$-server system with two FCFS queues, where the arrival rates at the queues and the service rate may depend on the number \$n\$ of customers being in service or in the first queue, but the service rate is assumed to be constant for \$n>s\$. The customers in the first queue are impatient. If the offered waiting time exceeds a random maximal waiting time \$I\$, then the customer leaves the first queue after time \$I\$. If \$I\$ is less than a given deterministic time then he leaves the system else he transits to the end of the second queue. The customers in the first queue have priority. The service of a customer from the second queue will be started if the first queue is empty and more than a given number of servers become idle. For the model being a generalization of the \$M(n)/M(n)/s\!+\!GI\$ system balance conditions for the density of the stationary state process are derived yielding the stability conditions and the probabilities that precisely \$n\$ customers are in service or in the first queue. For obtaining performance measures for the second queue a system approximation basing on fitting impatience intensities is constructed. The results are applied to the performance analysis of a call center with an integrated voice-mail-server. For an important special case a stochastic decomposition is derived illuminating the connection to the dynamics of the \$M(n)/M(n)/s\!+\!GI\$ system.}, language = {en} } @misc{Bley1998, author = {Bley, Andreas}, title = {On the Complexity of Vertex-Disjoint Length-Restricted Path Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3639}, number = {SC-98-20}, year = {1998}, abstract = {Let \$G=(V,E)\$ be a simple graph and \$s\$ and \$t\$ be two distinct vertices of \$G\$. A path in \$G\$ is called \$\ell\$-bounded for some \$\ell\in\mathbb{N}\$, if it does not contain more than \$\ell\$ edges. We study the computational complexity of approximating the optimum value for two optimization problems of finding sets of vertex-disjoint \$\ell\$-bounded \$s,t\$-paths in \$G\$. First, we show that computing the maximum number of vertex-disjoint \$\ell\$-bounded \$s,t\$-paths is \$\mathcal{AP\kern-1pt X}\$--complete for any fixed length bound \$\ell\geq 5\$. Second, for a given number \$k\in\mathbb{N}\$, \$1\leq k \leq |V|-1\$, and non-negative weights on the edges of \$G\$, the problem of finding \$k\$ vertex-disjoint \$\ell\$-bounded \$s,t\$-paths with minimal total weight is proven to be \$\mathcal{NPO}\$--complete for any length bound \$\ell\geq 5\$. Furthermore, we show that, even if \$G\$ is complete, it is \$\mathcal{NP}\$--complete to approximate the optimal solution value of this problem within a factor of \$2^{\langle\phi\rangle^\epsilon}\$ for any constant \$0<\epsilon<1\$, where \$\langle\phi\rangle\$ denotes the encoding size of the given problem instance \$\phi\$. We prove that these results are tight in the sense that for lengths \$\ell\leq 4\$ both problems are polynomially solvable, assuming that the weights satisfy a generalized triangle inequality in the weighted problem. All results presented also hold for directed and non-simple graphs. For the analogous problems where the path length restriction is replaced by the condition that all paths must have length equal to \$\ell\$ or where vertex-disjointness is replaced by edge-disjointness we obtain similar results.}, language = {en} } @phdthesis{Reich1998, author = {Reich, Sebastian}, title = {Dynamical Systems, Numerical Integration, and Exponentially Small Estimates}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3622}, number = {SC-98-19}, year = {1998}, abstract = {Dynamical systems with two well-separated time-scales are investigated using normal form theory. Exponential estimates for the normal form truncation error are derived and applied to the numerical integration of differential equations (backward error analysis) and the reduction of highly oscillatory Hamiltonian systems (constrained dynamics and correcting potentials). The theoretical results are used to formulate new algorithms for the time integration of conservative Hamiltonian systems (projected multiple time stepping, soft constraints, rigid bodies, symplectic variable step-size methods).}, language = {en} }