@misc{KaehlerHege2001, author = {K{\"a}hler, Ralf and Hege, Hans-Christian}, title = {Interactive Volume Rendering of Adaptive Mesh Refinement Data}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6561}, number = {01-30}, year = {2001}, abstract = {Many phenomena in nature and engineering happen simultaneously on rather diverse spatial and temporal scales, i.e.\ exhibit a multi-scale character. Therefore various hierarchical data structures and numerical schemes have been devised to represent quantitatively such phenomena. A special numerical multilevel technique, associated with a particular hierarchical data structure, is so-called Adaptive Mesh Refinement (AMR). This scheme achieves locally very high spatial and temporal resolutions. Due to its popularity, many scientists are in need of interactive visualization tools for AMR data. In this article we present a 3D texture-based volume rendering algorithm for AMR data, that directly utilizes the hierarchical structure. Thereby interactive rendering even for large data sets is achieved. In particular the problems of interpolation artifacts, opacity corrections, and texture memory limitations are addressed. The algorithm's value in practice is demonstrated with simulation and image data.}, language = {en} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Telota - was soll das?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6538}, number = {01-27}, year = {2001}, abstract = {Telota ist ein Kunstwort, das f{\"u}r alle Aktivit{\"a}ten der Berlin-Brandenburgischen Akademie der Wissenschaften steht, die der F{\"o}rderung von Forschung, Kommunikation und Pr{\"a}sentation durch elektronische Medien dienen. In diesem Artikel werden die Entstehung des Telota-Projektes geschildert und die Ziele diskutiert, die mit diesem Projekt erreicht werden sollen. Es geht darum, moderne Informationstechnik bewusst, geplant und nachhaltig f{\"u}r alle Belange der {\rm BBAW} einzusetzen. Informationstechnische Werkzeuge sollen f{\"u}r die wissenschaftliche Arbeit effizient genutzt werden; die Information nach innen und nach außen soll deutlich verbessert werden; eine bessere Kommunikationsinfrastuktur soll die Zusammenarbeit f{\"o}rdern.}, language = {de} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Empfehlungen des Wissenschaftsrates zur digitalen Informationsversorgung durch Hochschulbibliotheken}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6546}, number = {01-28}, year = {2001}, abstract = {Der Wissenschaftsrat hat in seiner Juli-Sitzung 2001 \glqq Empfehlungen zur digitalen Informationsversorgung durch Hochschulbibliotheken \grqq verabschiedet. Einige der Vorschl{\"a}ge des Wissenschaftsrates k{\"o}nnen, falls sie von den angesprochenen Institutionen aufgenommen werden, zu einer nachhaltigen Ver{\"a}nderung der wissenschaftlichen Informationslandschaft f{\"u}hren. In meinem kurzen Kommentar zu diesem Papier m{\"o}chte ich auf einige dieser Anregungen hinweisen.}, language = {de} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Mein digitaler Traum}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6558}, number = {01-29}, year = {2001}, abstract = {Von welcher "Informationsumwelt" tr{\"a}umt jemand, der f{\"u}r seine wissenschaftliche (und sonstige) Arbeit digitale Informationstechnologie intensiv einsetzt? In diesem Artikel beschreibe ich meinen "digitalen Traum". Er ist ganz einfach zu formulieren:"Ich will alles und zwar sofort, jederzeit, "{\"u}berall" und kostenlos zur Verf{\"u}gung haben." Ich schildere, was davon heute schon (fast) realisiert ist und was noch fehlt. Ich skizziere einige zentrale Schwierigkeiten der vollst{\"a}ndigen Realisierung und skizziere m{\"o}gliche L{\"o}sungen.}, language = {de} } @misc{Helmberg2001, author = {Helmberg, Christoph}, title = {A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6527}, number = {01-26}, year = {2001}, abstract = {The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges to the optimal solution under reasonable assumptions on the separation oracle and the feasible set. We have implemented a practical variant of the cutting plane algorithm for improving semidefinite relaxations of constrained quadratic 0-1 programming problems by odd-cycle inequalities. We also consider separating odd-cycle inequalities with respect to a larger support than given by the cost matrix and present a heuristic for selecting this support. Our preliminary computational results for max-cut instances on toroidal grid graphs and balanced bisection instances indicate that warm start is highly efficient and that enlarging the support may sometimes improve the quality of relaxations considerably.}, language = {en} } @misc{Steinbach2001, author = {Steinbach, Marc}, title = {General Information Constraints in Stochastic Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6502}, number = {01-24}, year = {2001}, abstract = {Scenario tree models of stochastic programs arise naturally under standard nonanticipativity assumptions. We demonstrate how tree-sparse programs cover the general case, with \emph{arbitrary} information constraints. Detailed examples and intuitive interpretations illuminate the basic thoughts behind the abstract but elementary construction.}, language = {en} } @misc{KaehlerSimonHege2001, author = {K{\"a}hler, Ralf and Simon, Mark and Hege, Hans-Christian}, title = {Fast Volume Rendering of Sparse High-Resolution Datasets Using Adaptive Mesh Refinement Hierarchies}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6516}, number = {01-25}, year = {2001}, abstract = {In this paper we present an algorithm that accelerates 3D texture-based volume rendering of large and sparse data sets. A hierarchical data structure (known as AMR tree) consisting of nested uniform grids is employed in order to efficiently encode regions of interest. The hierarchies resulting from this kind of space partitioning yield a good balance between the amount of volume to render and the number of texture bricks -- a prerequisite for fast rendering. Comparing our approach to an octree based algorithm we show that our algorithm increases rendering performance significantly for sparse data. A further advantage is that less parameter tuning is necessary.}, language = {en} } @misc{HohageSchmidtZschiedrich2001, author = {Hohage, Thorsten and Schmidt, Frank and Zschiedrich, Lin}, title = {Solving time-harmonic scattering problems based on the pole condition: Convergence of the PML method}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6494}, number = {01-23}, year = {2001}, abstract = {In this paper we study the PML method for Helmholtz-type scattering problems with radially symmetric potential. The PML method consists in surrounding the computational domain by a \textbf{P}erfectly \textbf{M}atched sponge \textbf{L}ayer. We prove that the approximate solution obtained by the PML method converges exponentially fast to the true solution in the computational domain as the thickness of the sponge layer tends to infinity. This is a generalization of results by Lassas and Somersalo based on boundary integral eqaution techniques. Here we use techniques based on the pole condition instead. This makes it possible to treat problems without an explicitly known fundamental solution.}, language = {en} } @misc{KrumkeRambauTorres2001, author = {Krumke, Sven and Rambau, J{\"o}rg and Torres, Luis Miguel}, title = {Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6484}, number = {01-22}, year = {2001}, abstract = {Given a set of service requests (events), a set of guided servers (units), and a set of unguided service contractors (conts), the vehicle dispatching problem {\sl vdp} is the task to find an assignment of events to units and conts as well as tours for all units starting at their current positions and ending at their home positions (dispatch) such that the total cost of the dispatch is minimized. The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit costs consist of driving costs, service costs and overtime costs; cont costs consist of a fixed cost per service; event costs consist of late costs linear in the late time, which occur whenever the service of the event starts later than its deadline. The program \textsf{ZIBDIP} based on dynamic column generation and set partitioning yields solutions on heavy-load real-world instances (215 events, 95 units) in less than a minute that are no worse than 1\\% from optimum on state-of-the-art personal computers.}, language = {en} } @misc{Otto2001, author = {Otto, Dagmar}, title = {Informationsportale und Digitale Bibliotheken}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6479}, number = {01-21}, year = {2001}, abstract = {Im ersten Teil des folgenden Aufsatzes werden allgemeine {\"U}berlegungen zur Entwicklung von Bibliotheken hin zu Informationsvermittlungsstellen f{\"u}r sowohl elektronische wie auch gedruckte Medien angestellt. Basierend auf den Ergebnissen der Evaluation digitaler Bibliotheken und Informationsportale in Deutschland wird ein erster Kriterienkatalog f{\"u}r ein Verbund-Informationsportal f{\"u}r den Kooperativen Bibliotheksverbund Berlin-Brandenburg entwickelt. Im Anhang befindet sich der Statusbericht {\"u}ber Informationsportale und digitale Bibliotheken in Deutschland. Dazu wurden sieben digitale Bibliotheken auf Verbundebene und 21 Bibliotheken nach Bundesl{\"a}ndern evaluiert.}, language = {de} } @misc{Koch2001, author = {Koch, Thorsten}, title = {ZIMPL User Guide}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6466}, number = {01-20}, year = {2001}, abstract = {{\sc Zimpl} is a little language to translate the mathematical model of a problem into a linear or (mixed-)integer mathematical program expressed in {\tt lp} or {\tt mps} file format which can be read by a LP or MIP solver.}, language = {en} } @misc{JeltschStrangDeuflhard2001, author = {Jeltsch, Rolf and Strang, Gilbert and Deuflhard, Peter}, title = {First SIAM-EMS Conference "Applied Mathematics in our Changing World" Berlin 2001 - Collection of Abstracts}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6452}, number = {01-19}, year = {2001}, abstract = {Collection of abstracts of the first SIAM-EMS conference Applied Mathematics in our Changing World'' in Berlin, September 2-6, 2001.}, language = {en} } @misc{Wagler2001, author = {Wagler, Annegret}, title = {Rank-Perfect and Weakly Rank-Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6448}, number = {01-18}, year = {2001}, abstract = {An edge of a perfect graph \$G\$ is critical if \$G-e\$ is imperfect. We would like to decide whether \$G - e\$ is still {\sl almost perfect} or already {\sl very imperfect}. Via relaxations of the stable set polytope of a graph, we define two superclasses of perfect graphs: rank-perfect and weakly rank-perfect graphs. Membership in those two classes indicates how far an imperfect graph is away from being perfect. We study the cases, when a critical edge is removed from the line graph of a bipartite graph or from the complement of such a graph.}, language = {en} } @misc{GroetschelKrumkeRambauetal.2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Winter, Thomas and Zimmermann, Uwe}, title = {Combinatorial Online Optimization in Real Time}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6424}, number = {01-16}, year = {2001}, abstract = {Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when decisions have to be made before all data of the problem are known. And we speak of a real-time online problem when online decisions have to be computed within very tight time bounds. This paper surveys the are of combinatorial online and real-time optimization, it discusses, in particular, the concepts with which online and real-time algorithms can be analyzed.}, language = {en} } @misc{GroetschelKrumkeRambau2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimization of Complex Transportation Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6438}, number = {01-17}, year = {2001}, abstract = {This paper discusses online optimization of real-world transportation systems. We concentrate on transportation problems arising in production and manufacturing processes, in particular in company internal logistics. We describe basic techniques to design online optimization algorithms for such systems, but our main focus is decision support for the planner: which online algorithm is the most appropriate one in a particular setting? We show by means of several examples that traditional methods for the evaluation of online algorithms often do not suffice to judge the strengths and weaknesses of online algorithms. We present modifications of well-known evaluation techniques and some new methods, and we argue that the selection of an online algorithm to be employed in practice should be based on a sound combination of several theoretical and practical evaluation criteria, including simulation.}, language = {en} } @misc{EhrigOfenlochSchaberetal.2001, author = {Ehrig, Rainald and Ofenloch, Oliver and Schaber, Karlheinz and Deuflhard, Peter}, title = {Modelling and Simulation of Aerosol Formation by Heterogeneous Nucleation in Gas-Liquid Contact Devices}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6416}, number = {01-15}, year = {2001}, abstract = {This paper describes a new simulation tool for the prediction of aerosol formation and behavior in gas--liquid contact devices such as absorbers, scrubbers, quench coolers, and condensers as well as multistage gas cleaning processes, respectively. Aerosol formation can impact severely the separation efficiency of gas cleaning processes. Aerosol or fog formation can arise by spontaneous condensation or desublimation in supersaturated gas phases. The rigorous description of the mass and energy transfer between the gas phase, the liquid phase, and the growing aerosol droplets leads to a system of partial differential and algebraic equations. For the solution of these systems we have developed the plant simulation tool AerCoDe. This program bases upon the linearly--implicit Euler discretisation, which in combination with extrapolation permits an adaptive step size and order control. Typical simulation results of a multistage industrial flue gas scrubbing process are presented. It is shown, that experimental data can be confirmed if the number concentration of condensation nuclei as an input parameter is roughly known.}, language = {en} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Copyright und elektronisches Publizieren: Auf dem Weg zu vern{\"u}nftigen Regelungen?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6395}, number = {01-13}, year = {2001}, abstract = {Das \emph{Committee on Electronic Information and Communication} (CEIC) der \emph{International Mathematical Union} (IMU) hat die Aufgabe, sich {\"u}ber die langfristige Informationsversorgung in der Mathematik Gedanken zu machen und L{\"o}sungsvorschl{\"a}ge hierf{\"u}r zu erarbeiten. Das Kernthema ist nat{\"u}rlich "`Elektronisches Publizieren"'. Dazu geh{\"o}ren auch Copyright-Regelungen. \% Sie sind -- \% neben einer Andeutung der weiteren CEIC-Pl{\"a}ne -- der Fokus dieses \% kurzen Artikels. Er schließt mit einem von der IMU verabschiedeten \% Aufruf zu vern{\"u}nftigem Verhalten bei Copyright-Vereinbarungen. Eine \% nachhaltige Befolgung dieses Aufrufs -- verbunden mit weiteren \% Aktivit{\"a}ten -- k{\"o}nnte die (derzeit kaum noch bezahlbare und \% dadurch gef{\"a}hrdete) Literaturversorgung nachhaltig zum Positiven \% ver{\"a}ndern. Mit diesem Artikel beginnt eine kleine Serie von Aufs{\"a}tzen, in denen ich (in meiner Funktion als eines von elf CEIC-Mitgliedern) die Empfehlungen des CEIC erl{\"a}utern werde. \% Das heutige Thema sind die \% CEIC-Vorschl{\"a}ge zum Copyright}, language = {de} } @misc{ReinefeldLindenstruth2001, author = {Reinefeld, Alexander and Lindenstruth, Volker}, title = {How to Build a High-Performance Compute Cluster for the Grid}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6374}, number = {01-11}, year = {2001}, abstract = {The success of large-scale multi-national projects like the forthcoming analysis of the LHC particle collision data at CERN relies to a great extent on the ability to efficiently utilize computing a management software (Datagrid, Globus, etc.), while the effective integration of computing nodes has been largely neglected up to now. This is the focus of our work. We present a framework for a high-performance cluster that can be used as a reliable computing node in the Grid. We outline the cluster architecture, the management of distributed data and the seamless intergration of the cluster into the Grid environment.}, language = {en} } @misc{Kuberek2001, author = {Kuberek, Monika}, title = {KOBV: institutionalisiert}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6360}, number = {01-10}, year = {2001}, abstract = {Der Aufsatz ist die ausgearbeitete Fassung eines Vortrages, gehalten am 05.04.2001 auf dem 91. Deutschen Bibliothekartag in Bielefeld. Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) ist im Rahmen eines wissenschaftlichen Projektes in den Jahren 1997 bis 2000 am Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin (ZIB) aufgebaut worden. Nachdem das Projekt erfolgreich abgeschlossen ist, wird der KOBV 2001 institutionalisiert. In dem Vortrag hat die Verfasserin einen {\"U}berblick {\"u}ber das bisher Erreichte, den derzeitigen Stand und die Perspektiven des neuen Verbundes gegeben. Der KOBV stellt eine neue Art von Bibliotheksverbund dar. Sein technisches Konzept und sein organisatorischer Aufbau basieren auf der {\sl Internetphilosophie}. Den informationstechnischen Kern bildet eine Suchmaschine, die die heterogenen lokalen Bibliothekssysteme miteinander verbindet. Die KOBV-Organisation ist dezentral. Sie wird getragen von der Kooperation der Bibliotheken in Berlin und Brandenburg. Eine kleine Verbundzentrale koordiniert dieses Geflecht vernetzter lokaler Einheiten, vertritt den KOBV nach außen und arbeitet - in Form von Projekten - an seiner Weiterentwicklung. Der Entwicklungsaspekt und die Nutzerorientierung sind zwei wesentliche Komponenten in der Verbundarbeit. Berlin und Brandenburg haben auf engem Raum zahlreiche Bibliotheken mit großen, reichhaltigen Medienbest{\"a}nden. Mittel- bis langfristig sollen Bibliotheken aller Sparten und Gr{\"o}ßen in den KOBV integriert werden, seien es wissenschaftliche Universalbibliotheken, universit{\"a}re Bibliothekssysteme, Spezialbibliotheken, Beh{\"o}rden- und Parlamentsbibliotheken oder {\"o}ffentliche Bibliotheken. Auch regionale Bibliotheksverb{\"u}nde k{\"o}nnen als Subverb{\"u}nde am KOBV teilnehmen. Mit der KOBV-Suchmaschine ist eine offene Plattform geschaffen worden, auf der weitere Entwicklungen aufsetzen k{\"o}nnen. Der Aufbau einer virtuellen Regionalbibliothek mit Bestell- und Lieferkomponenten ist eines der Ziele. Dar{\"u}ber hinaus ist es die Vision, in der Region ein virtuelles {\sl Wissensportal} aufzubauen, das dem Nutzer unter einer Adresse den umfassenden Zugang und die umfassende Bereitstellung von Informationen aller Art bietet.}, language = {de} } @misc{BrandtBrandt2001, author = {Brandt, Andreas and Brandt, Manfred}, title = {On the Moments of the Overflow and Freed Carried Traffic for the GI/M/C/0 System}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6355}, number = {01-09}, year = {2001}, abstract = {In circuit switching networks call streams are characterized by their mean and peakedness (two-moment method). The \$GI/M/C/0\$ system is used to model a single link, where the \$GI\$-stream is determined by fitting moments appropriately. For the moments of the overflow traffic of a \$GI/M/C/0\$ system there are efficient numerical algorithms available. However, for the moments of the freed carried traffic, defined as the moments of a virtual link of infinite capacity to which the process of calls accepted by the link (carried arrival process) is virtually directed and where the virtual calls get fresh exponential i.i.d.\ holding times, only complex numerical algorithms are available. This is the reason why the concept of the freed carried traffic is not used rigorously. The main result of this paper is an efficient algorithm for computing the moments of the freed carried traffic, in particular an explicit formula for its peakedness. This result offers a unified handling of both overflow and carried traffics in networks. Furthermore, some refined characteristics for the overflow and freed carried streams are derived.}, language = {en} } @misc{OPUS4-975, title = {Jahresbericht 2000}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9751}, number = {2000}, year = {2001}, language = {de} } @misc{Steinbach2001, author = {Steinbach, Marc}, title = {Tree-Sparse Convex Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6340}, number = {01-08}, year = {2001}, abstract = {Dynamic stochastic programs are prototypical for optimization problems with an inherent tree structure inducing characteristic sparsity patterns in the KKT systems of interior methods. We propose an integrated modeling and solution approach for such tree-sparse programs. Three closely related natural formulations are theoretically analyzed from a control-theoretic viewpoint and compared to each other. Associated KKT solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.}, language = {en} } @misc{KrumkePaepeRambauetal.2001, author = {Krumke, Sven and Paepe, Willem de and Rambau, J{\"o}rg and Stougie, Leen}, title = {Online Bin-Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6338}, number = {01-07}, year = {2001}, abstract = {We introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly enviroment. The bin coloring problem is to pack unit size colored items into bins, such that the maximum number of different colors per bin is minimized. Each bin has size~\$B\in\mathbb{N}\$. The packing process is subject to the constraint that at any moment in time at most \$q\in\mathbb{N}\$ bins may be partially filled. Moreover, bins may only be closed if they are filled completely. An online algorithm must pack each item must be packed without knowledge of any future items. We investigate the existence of competitive online algorithms for the online uniform binpacking problem. We show upper bounds for the bin coloring problem. We prove an upper bound of \$3q\$ - 1 and a lower bound of \$2q\$ for the competitive ratio of a natural greedy-type algorithm, and show that surprisingly a trivial algorithm which uses only one open bin has a strictly better competitive ratio of \$2q\$ - 1. Morever, we show that any deterministic algorithm has a competitive ratio \$\Omega (q)\$ and that randomization does not improve this lower bound even when the adversary is oblivious.}, language = {en} } @misc{Byun2001, author = {Byun, Chul-Young}, title = {Lower Bounds for Large-Scale Set Partitioning Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6321}, number = {01-06}, year = {2001}, abstract = {In this work we concentrate on developing methods which determine good lower bounds for set partitioning problems (SPP) in an appropriate amount of time. We found out that it makes sense to use the Lagrangian relaxation method for this task. The Lagrangian relaxed problem of SPP has a simple structure, which leads to algorithms and heuristics, whose total complexity per iteration depends linearly on the number of non-zeros of the problem matrix of SPP. In contrast, other methods like simplex methods or interior point methods have a complexity of higher order. Because the problem matrices of our tested instances are sparse, the linear dependence becomes an advantage for the algorithms and heuristics mentioned above. As a reference for the state-of-the-art we have applied the dual simplex method and the barrier function method, implemented in CPLEX. The methods, which we have developed and compared with those of CPLEX, are SBM, CAM, CCBM, and CBM. SBM is a subgradient bundle method derived from the basic subgradient method, which is a global convergent method for determining the maximum of concave functions. CAM is a coordinate ascent method, where the convex coordinate bundle method CCBM and the coordinate bundle method CBM are derivatives from CAM. We observed that the basic subgradient and the coordinate ascent method are improved if bundling techniques can be used. But the motivation for bundling differs for both approaches. In the former case bundling helps to approximate a minimum norm subgradient, which provides a steepest ascent direction, in order to speed up the performance. In the latter case bundling enables proceeding along directions, which are not restricted on the coordinate directions. By this the performance is accelerated. Among all used techniques stabilization is worth mentioning. Stabilization improves the performance especially at the beginning by avoiding too big steps during the proceeding. This leads to a more stabilized progression. Stabilization was successfully applied to SBM, CAM, CCBM, and CBM. As an overall result we conclude the following: \begin{enumerate} \item CPLEX computes the optimal objective values, whereas SBM and CBM has on average a gap of under \$1.5\\%\$. \item In comparison to CPLEX baropt, SBM, CAM, and CBM the algorithm CCBM has a slow convergence because of the convex combination of ascent coordinate directions. An alternative is to relax the convex combination to a simple sum of the corresponding directions. This idea is realized in CBM. \item If we focus on the running time rather than on optimality then CBM is on average the fastest algorithm. \end{enumerate} Note that methods like SBM or CBM are applied on static SPP instances in order to determine a good lower bound. For solving SPP we need dynamical methods. Due to the complex topic of dynamical methods we will not discuss them, but a certain technique is worth mentioning. It is called column generation. We have indicated that this technique needs good Lagrangian multipliers of the corresponding SPP instances in order to generate further columns (in our case duties), which are added to the current SPP instance. Those multipliers are by-products of methods like our six considered methods. Due to the large number of such generation steps the running time depends on the computation time of these methods. Therefore, CBM fits more to this technique than CPLEX baropt or SBM. To sum it up it can be said that applications such as a duty scheduling can be described as set partitioning problems, whose lower bound can be solved by simplex, interior points, subgradient, or coordinate ascent methods. It turns out that the interior points method CPLEX baropt and the heuristic CBM have good performances. Furthermore, good Lagrangian multipliers, which are by-products of these methods, can be used by techniques like column generation. For this particular technique it also turns out that among our tested algorithms CBM is the most efficient one. In general we can state that real-world applications, which have to solve a large number of Lagrangian relaxed SPP instances can improve their performance by using CBM.}, language = {en} } @misc{HenrionLiMoelleretal.2001, author = {Henrion, Rene and Li, Pu and M{\"o}ller, Andris and Steinbach, Marc and Wendt, Moritz and Wozny, G{\"u}nter}, title = {Stochastic Optimization for Operating Chemical Processes Under Uncertainty}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6304}, number = {01-04}, year = {2001}, abstract = {Mathematical optimization techniques are on their way to becoming a standard tool in chemical process engineering. While such approaches are usually based on deterministic models, uncertainties such as external disturbances play a significant role in many real-life applications. The present article gives an introduction to practical issues of process operation and to basic mathematical concepts required for the explicit treatment of uncertainties by stochastic optimization.}, language = {en} } @misc{GarridoSteinbach2001, author = {Garrido, Izaskun and Steinbach, Marc}, title = {A Multistage Stochastic Programming Approach in Real-Time Process Control}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6317}, number = {01-05}, year = {2001}, abstract = {Standard model predictive control for real-time operation of industrial production processes may be inefficient in the presence of substantial uncertainties. To avoid overly conservative disturbance corrections while ensuring safe operation, random influences should be taken into account explicitly. We propose a multistage stochastic programming approach within the model predictive control framework and apply it to a distillation process with a feed tank buffering external sources. A preliminary comparison to a probabilistic constraints approach is given and first computational results for the distillation process are presented.}, language = {en} } @misc{FischerSchuetteDeuflhardetal.2001, author = {Fischer, Alexander and Sch{\"u}tte, Christof and Deuflhard, Peter and Cordes, Frank}, title = {Hierarchical Uncoupling-Coupling of Metastable Conformations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6296}, number = {01-03}, year = {2001}, abstract = {Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. UCMC aims at avoiding the typical metastable or trapping behavior of Monte Carlo techniques. From the viewpoint of Monte Carlo, a slowly converging long-time Markov chain is replaced by a limited number of rapidly mixing short-time ones. Therefore, the state space of the chain has to be hierarchically decomposed into its metastable conformations. This is done by means of combining the technique of conformation analysis as recently introduced by the authors, and appropriate annealing strategies. We present a detailed examination of the uncoupling-coupling procedure which uncovers its theoretical background, and illustrates the hierarchical algorithmic approach. Furthermore, application of the UCMC algorithm to the \$n\$-pentane molecule allows us to discuss the effect of its crucial steps in a typical molecular scenario.}, language = {en} } @misc{BorndoerferGroetschelLoebel2001, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Duty Scheduling in Public Transit}, doi = {10.1007/978-3-642-55753-8_50}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6286}, number = {01-02}, year = {2001}, abstract = {This article is about \emph{adaptive column generation techniques} for the solution of duty scheduling problems in public transit. The current optimization status is exploited in an adaptive approach to guide the subroutines for duty generation, LP resolution, and schedule construction toward relevant parts of a large problem. Computational results for three European scenarios are reported.}, language = {en} } @misc{GroetschelFonsecaDavis2001, author = {Gr{\"o}tschel, Martin and Fonseca, Irene and Davis, Mark}, title = {Round Table: The Impact of Mathematical Research on Industry and Vice Versa}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6259}, number = {00-57}, year = {2001}, abstract = {This paper is a summary of the Round Table: ``The Impact of Mathematical Research on Industry and Vice Versa'' held at 3ecm in Barcelona on July 11, 2000. The round table started with contributions of the three panelists. Irene Fonseca, the panel chair, opened the discussion by stating six questions addressing the main issues of the round table topic. She presented the panel's answers to these questions, drawing on many examples from her own academic experience. In the following additional presentations, the other two panel members added further points of view based on their personal involvement with industry. The round table ended with a lively discussion with members from the audience. This written summary of the oral presentations follows the structure of the round table indicated above.}, language = {en} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Frequency Assignment in Mobile Phone Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6265}, number = {00-58}, year = {2001}, abstract = {Wireless communication networks employ radio frequencies to establish communication links. The available radio spectrum is very limited. To meet today's radio communication demand, this resource has to be administered and reused carefully in order to control mutual interference. The reuse can be organized via separation in space, time, or frequency, for example. The problem, therefore, arises to distribute frequencies to links in a ``reasonable manner''. This is the basic form of the frequency assignment problem. What ``reasonable'' means, how to quantify this measure of quality, which technical side constraints to consider cannot be answered in general. The exact specification of this task and its mathematical model depend heavily on the particular application considered. In this paper we discuss this issue with respect to the GSM standard for mobile communication.}, language = {en} } @misc{HohageSchmidtZschiedrich2001, author = {Hohage, Thorsten and Schmidt, Frank and Zschiedrich, Lin}, title = {Solving time-harmonic scattering problems based on the condition: Theory}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6279}, number = {01-01}, year = {2001}, abstract = {The pole condition is a general concept for the theoretical analysis and the numerical solution of a variety of wave propagation problems. It says that the Laplace transform of the physical solution in radial direction has no poles in the lower complex half-plane. In the present paper we show that for the Helmholtz equation with a radially symmetric potential the pole condition is equivalent to Sommerfeld's radiation condition. Moreover, a new representation formula based on the pole condition is derived and used to prove existence, uniqueness and asymptotic properties of solutions. This lays the foundations of a promising new algorithm to solve time-harmonic scattering problems numerically and provides a new approach for analyzing existing algorithms such as the Perfectly Matched Layer (PML) method and the Bayliss-Gunzburger-Turkel (BGT) algorithm.}, language = {en} } @misc{KrumkeRambau2000, author = {Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6238}, number = {00-55}, year = {2000}, abstract = {Wie soll man einen Aufzug steuern, wenn man keine Informationen {\"u}ber zuk{\"u}nftige Fahrauftr{\"a}ge besitzt? Soll man eine Bahncard kaufen, wenn die n{\"a}chsten Bahnreisen noch unbekannt sind? In der klassischen kombinatorischen Optimierung geht man davon aus, daß die Daten jeder Probleminstanz vollst{\"a}ndig gegeben sind. In vielen F{\"a}llen modelliert diese \emph{Offline-Optimierung} jedoch die Situationen aus Anwendungen nur ungen{\"u}gend. Zahlreiche Problemstellungen in der Praxis sind in nat{\"u}rlicher Weise \emph{online}: Sie erfordern Entscheidungen, die unmittelbar und ohne Wissen zuk{\"u}nftiger Ereignisse getroffen werden m{\"u}ssen. Als ein Standardmittel zur Beurteilung von Online-Algorithmen hat sich die \emph{kompetitive Analyse} durchgesetzt. Dabei vergleicht man den Zielfunktionswert einer vom Online-Algorithmus generierten L{\"o}sung mit dem Wert einer optimalen Offline-L{\"o}sung. Mit Hilfe der kompetitiven Analyse werden im Skript Algorithmen zum Caching, Netzwerk-Routing, Scheduling und zu Transportaufgaben untersucht. Auch die Schw{\"a}chen der kompetitiven Analyse werden aufgezeigt und alternative Analysekonzepte vorgestellt. Neben der theoretischen Seite werden auch die Anwendungen der Online-Optimierung in der Praxis, vor allem bei Problemen der innerbetrieblichen Logistik, beleuchtet. Bei der Steuerung automatischer Transportsysteme tritt eine F{\"u}lle von Online-Problemen auf. Hierbei werden an die Algorithmen oftmals weitere Anforderungen gestellt. So m{\"u}ssen Entscheidungen unter strikten Zeitbeschr{\"a}nkungen gef{\"a}llt werden (Echtzeit-Anforderungen). Dieses Skript ist aus dem Online-Teil der Vorlesung -Ausgew{\"a}hlte Kapitel aus der ganzzahligen Optimierung- (Wintersemester~1999/2000) und der Vorlesung -Online Optimierung- (Sommersemester~2000) an der Technischen Universit{\"a}t Berlin entstanden.}, language = {de} } @misc{KrumkeRambauWeider2000, author = {Krumke, Sven and Rambau, J{\"o}rg and Weider, Steffen}, title = {An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6217}, number = {00-53}, year = {2000}, abstract = {In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most \$C\$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation.}, language = {en} } @misc{SchmidtFrieseZschiedrichetal.2000, author = {Schmidt, Frank and Friese, Tilmann and Zschiedrich, Lin and Deuflhard, Peter}, title = {Adaptive Multigrid Methods for the Vectorial Maxwell Eigenvalue Problem for Optical Waveguide Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6228}, number = {00-54}, year = {2000}, abstract = {This paper has been motivated by the need for a fast robust adaptive multigrid method to solve the vectorial Maxwell eigenvalue problem arising from the design of optical chips. Our nonlinear multigrid methods are based on a previous method for the scalar Helmholtz equation, which must be modified to cope with the null space of the Maxwell operator due to the divergence condition. We present two different approaches. First, we present a multigrid algorithm based on an edge element discretization of time-harmonic Maxwell's equations, including the divergence condition. Second, an explicit elimination of longitudinal magnetic components leads to a nodal discretization known to avoid discrete \emph{spurious modes} also and a vectorial eigenvalue problem, for which we present a multigrid solver. Numerical examples show that the edge element discretization clearly outperforms the nodal element approach.}, language = {en} } @misc{Stueben2000, author = {St{\"u}ben, Hinnerk}, title = {Hadron masses from dynamical, non-perturbatively O(a) improved Wilson fermions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6205}, number = {00-52}, year = {2000}, abstract = {We present results on light hadron masses from simulations of full QCD and report on experiences in running such simulations on a Hitachi SR8000-F1 supercomputer.}, language = {en} } @misc{SanderRunge2000, author = {Sander, Oliver and Runge, Daniel}, title = {Fast Surface Reconstruction Using a Probe Sphere}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6181}, number = {00-50}, year = {2000}, abstract = {We introduce a new method for reconstructing a triangular surface from an unorganized set of points in space. It is based on placing a probe sphere on the point set and rolling it around, connecting all triples of points with a triangle that the sphere comes to rest on. Therefore, the algorithm interpolates, rather than approximates, the input points. The method needs considerably less running time than previous algorithms and yields good results on point sets that are reasonably well-behaved.}, language = {en} } @misc{GalliatDeuflhardRoitzschetal.2000, author = {Galliat, Tobias and Deuflhard, Peter and Roitzsch, Rainer and Cordes, Frank}, title = {Automatic Identification of Metastable Conformations via Self-Organized Neural Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6197}, number = {00-51}, year = {2000}, abstract = {As has been shown recently, the identification of metastable chemical conformations leads to a Perron cluster eigenvalue problem for a reversible Markov operator. Naive discretization of this operator would suffer from combinatorial explosion. As a first remedy, a pre-identification of essential degrees of freedom out of the set of torsion angles had been applied up to now. The present paper suggests a different approach based on neural networks: its idea is to discretize the Markov operator via self-organizing (box) maps. The thus obtained box discretization then serves as a prerequisite for the subsequent Perron cluster analysis. Moreover, this approach also permits exploitation of additional structure within embedded simulations. As it turns out, the new method is fully automatic and efficient also in the treatment of biomolecules. This is exemplified by numerical results.}, language = {en} } @misc{Wagler2000, author = {Wagler, Annegret}, title = {Critical and Anticritical Edges in Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6174}, number = {00-49}, year = {2000}, abstract = {We call an edge \$e\$ of a perfect graph \$G\$ critical if \$G-e\$ is imperfect and say further that \$e\$ is anticritical with respect to the complementary graph \$\overline G\$. We ask in which perfect graphs critical and anticritical edges occur and how to find critical and anticritical edges in perfect graphs. Finally, we study whether we can order the edges of certain perfect graphs such that deleting all the edges yields a sequence of perfect graphs ending up with a stable set.}, language = {en} } @misc{BleyKoch2000, author = {Bley, Andreas and Koch, Thorsten}, title = {Optimierung in der Planung und beim Aufbau des G-WiN}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6169}, number = {00-48}, year = {2000}, abstract = {Ende Juni diesen Jahres wurde das Gigabit-Wissenschaftsnetz offiziell gestartet. In der zweij{\"a}hrigen Vorbereitungsphase wurden nicht nur die technischen M{\"o}glichkeiten der neuen {\"U}bertragungstechniken und Dienste getestet. Es wurden auch verschiedene Fragestellungen zum effizienten Einsatz der verf{\"u}gbaren Ressourcen f{\"u}r den Betrieb des G-WiN untersucht. In diesem Artikel beschreiben wir, wie das G-WiN zu seiner jetzigen Struktur und Topologie gekommen ist.}, language = {de} } @misc{Rambau2000, author = {Rambau, J{\"o}rg}, title = {Triangulierungen von Punktmengen und Polyedern}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6145}, number = {00-46}, year = {2000}, abstract = {Dieser Report wurde im Sommersemester 2000 an der TU Berlin in einer Spezialvorlesung {\"u}ber Triangulierungen von Punktmengen und Polyedern als Skriptum verwendet. Nach einem motivierenden Kapitel werden grundlegende Begriffe und Konstruktionen in der Theorie der Triangulierungen von Punktmengen und Polyedern vorgestellt. Danach werden als weiterf{\"u}hrende Themen regul{\"a}re Triangulierungen, Sekund{\"a}rpolytope, bistellare Operationen, h{\"o}here Stasheff-Tamari-Halbordnungen und Triangulierungen mit wenigen bzw. gar keinen Flips behandelt. Ein Kapitel {\"u}ber Enumeration und Optimierung beschließt die Zusammenstellung.}, language = {de} } @misc{EisenblaetterGroetschelKoster2000, author = {Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Koster, Arie M.C.A.}, title = {Frequency Planning and Ramifications of Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6152}, number = {00-47}, year = {2000}, abstract = {This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are \$T\$-coloring and list coloring. To model all the subtleties, the techniques of integer programming have proven to be very useful. The ability to produce good frequency plans in practice is essential for the quality of mobile phone networks. The present algorithmic solution methods employ variants of some of the traditional coloring heuristics as well as more sophisticated machinery from mathematical programming. This paper will also address this issue. Finally, this paper discusses several practical frequency assignment problems in detail, states the associated mathematical models, and also points to public electronic libraries of frequency assignment problems from practice. The associated graphs have up to several thousand nodes and range from rather sparse to almost complete.}, language = {en} } @misc{Rambau2000, author = {Rambau, J{\"o}rg}, title = {Circuit Admissible Triangulations of Oriented Matroids}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6139}, number = {00-45}, year = {2000}, abstract = {All triangulations of euclidean oriented matroids are of the same PL-homeomorphism type by a result of Anderson. That means all triangulations of euclidean acyclic oriented matroids are PL-homeomorphic to PL-balls and that all triangulations of totally cyclic oriented matroids are PL-homeomorphic to PL-spheres. For non-euclidean oriented matroids this question is wide open. One key point in the proof of Anderson is the following fact: for every triangulation of a euclidean oriented matroid the adjacency graph of the set of all simplices ``intersecting'' a segment \$[p_-p_+]\$ is a path. We call this graph the \$[p_-p_+]\$-adjacency graph of the triangulation. While we cannot solve the problem of the topological type of triangulations of general oriented matroids we show in this note that for every circuit admissible triangulation of an arbitrary oriented matroid the \$[p_-p_+]\$-adjacency graph is a path.}, language = {en} } @misc{Groetschel2000, author = {Gr{\"o}tschel, Martin}, title = {Mathematik in der Industrie: interessante Branchen und zuk{\"u}nftige Einsatzfelder}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6125}, number = {00-44}, year = {2000}, abstract = {Dieser kurze Artikel hat keine umfassende {\"U}bersicht zum Ziel. Basierend auf eigenen Erfahrungen durch Projekte mit Industriefirmen m{\"o}chte ich einige Branchen erw{\"a}hnen, bei denen nach meiner Einsch{\"a}tzung Mathematik in Zukunft zunehmend Anwendung finden wird. Ich werde das anhand konkreter Beispiele erl{\"a}utern. Mathematik ersetzt in der Regel traditionelle Analyse-, Planungs- und Entwurfstechniken. Den (nicht leichten) Schritt zum Einsatz mathematischer Methoden macht ein Praktiker nur, wenn es sich f{\"u}r ihn ``lohnt''. Wann sich dies lohnt, ist schwer abzusch{\"a}tzen. Man kann aber einige Indikatoren daf{\"u}r finden, ob eine Branche f{\"u}r den Einsatz von Mathematik ``reif'' ist. Ob es dann dazu kommt, h{\"a}ngt von vielen Faktoren ab, nicht zuletzt von der Psychologie und dem sozialen Umfeld der beteiligten Personen sowie der Bereitschaft, sich auf ein so schwieriges Terrain zu begeben und Kompromisse einzugehen. Gerade letzteres f{\"a}llt Mathematikern gelegentlich schwer.}, language = {de} } @misc{KuberekLillLohrumetal.2000, author = {Kuberek, Monika and Lill, Monika and Lohrum, Stefan and Rusch, Beate}, title = {Spezifikation der Schnittstelle zwischen KOBV-Suchmaschine und Lokalsystemen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6106}, number = {00-42}, year = {2000}, abstract = {Die Kommunikation zwischen der KOBV-Suchmaschine und entfernten Bibliotheksinformationssystemen unterschiedlicher Hersteller wird {\"u}ber das Standardprotokoll Z39.50 abgewickelt. Die Suchmaschine erm{\"o}glicht Online-Recherchen in lokalen Bibliotheksinformationssystemen, die dazu ein Z39.50 Target (Server) zur Verf{\"u}gung stellen m{\"u}ssen. Die Suchmaschine liefert ihre Daten ebenfalls {\"u}ber Z39.50 aus. Ein Lokalsystem ben{\"o}tigt hierf{\"u}r einen Z39.50 Origin (Client). In dem Papier wird die Schnittstelle zwischen der KOBV-Suchmaschine und lokalen Bibliothekssystemen spezifiziert: Es werden die grundlegenden Anforderungen an Lokalsysteme definiert und die Konfigurationsparameter f{\"u}r die Z39.50-Kommunikation zwischen KOBV-Suchmaschine und Lokalsystemen beschrieben.}, language = {de} } @misc{GroetschelKuberekLilletal.2000, author = {Gr{\"o}tschel, Martin and Kuberek, Monika and Lill, Monika and Lohrum, Stefan and L{\"u}gger, Joachim and Rusch, Beate}, title = {Kooperativer Bibliotheksverbund Berlin-Brandenburg (KOBV)}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6118}, number = {00-43}, year = {2000}, abstract = {Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) wurde in den Jahren 1997-2000 im Rahmen eines wissenschaftlichen Projektes eingerichtet. Er stellt eine neuartige Form von Bibliotheksverbund dar. Sein technisches Konzept und sein organisatorischer Aufbau basieren auf der Internetphilosophie. Den informationstechnischen Kern bildet eine Suchmaschine, die die heterogenen lokalen Bibliothekssysteme miteinander verbindet. Die KOBV-Organisation ist dezentral. Sie wird getragen von der Kooperation der Bibliotheken in Berlin und Brandenburg; diese werden von einer kleinen Verbundzentrale unterst{\"u}tzt. Die KOBV-Suchmaschine ist zu erreichen unter: {\begin{rawhtml} http://www.kobv.de/suche/ \end{rawhtml}}}, language = {de} } @misc{HeidlStaudemeyer2000, author = {Heidl, Sebastian and Staudemeyer, Ralf}, title = {Implementation von WAP-Diensten f{\"u}r die SGI/CRAY T3E des ZIB}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6098}, number = {00-41}, year = {2000}, abstract = {Die zunehmende Verf{\"u}gbarkeit von mobilen Ger{\"a}ten, die mit einem Internetanschluß ausger{\"u}stet sind, bringt auch eine steigende Nachfrage nach Informationsdiensten f{\"u}r diese Art von Clients mit sich. Das ZIB stellt mit seinem H{\"o}chstleistungsrechner vom Typ SGI/CRAY T3E Wissenschaftlern große Rechenkapazit{\"a}ten zur Verf{\"u}gung. Im Rahmen dieser Studienarbeit wurde ein WAP-Interface zur T3E entwickelt, das es den Nutzern erm{\"o}glicht, {\"u}ber ein mobiles, WAP-f{\"a}higes Ger{\"a}t Informationen zur Betriebsbereitschaft und zur Auslastung des H{\"o}chstleistungsrechners, sowie Informationen zu den von ihnen in Auftrag gegebenen Rechenjobs abzurufen. Die Untersuchung der aktuellen M{\"o}glichkeiten in der mobilen Kommunikation brachte einige Einschr{\"a}nkungen f{\"u}r das geplante Informationsangebot mit sich. So mußte auf Grund von Sicherheitsbedenken auf eine tats{\"a}chliche Interaktionsm{\"o}glichkeit (z.B. neue Rechenjobs zu starten) verzichtet werden. Demgegen{\"u}ber konnte gezeigt werden, daß die Bereitstellung der gleichen Informationen f{\"u}r unterschiedliche Arten von Clients (WWW-Browser \$\rightarrow\$ HTML, WAP-Browser \$\rightarrow\$ WML) durch die Verwendung von XML als internes Datenformat problemlos m{\"o}glich ist. Es hat sich gezeigt, daß die Bereitstellung eines WAP-Informationsdienstes auf Grund verschiedener Inkompatibilit{\"a}tsprobleme (verschiedene Gateways, verschiedene WAP-Browser) mit erheblichem Aufwand verbunden sein kann. An dieser Stelle besteht noch Handlungsbedarf seitens der Hersteller dieser Softwarepakete.}, language = {de} } @misc{Kuberek2000, author = {Kuberek, Monika}, title = {Kooperativer Bibliotheksverbund Berlin-Brandenburg (KOBV) - Konzept, Erfahrungen, Ausblick -}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6079}, number = {00-39}, year = {2000}, abstract = {Der Aufsatz ist die ausgearbeitete Fassung eines Vortrages, gehalten auf dem 2. BSZ-Kolloquium des Bibliotheksservice-Zentrums Baden-W{\"u}rttemberg (BSZ) am 10. Oktober 2000 in Konstanz. Der Kooperative Bibliotheksverbund Berlin-Brandenburg, kurz KOBV, ist ein sehr junger Verbund - genauer gesagt, befindet er sich im Oktober 2000 immer noch in der Aufbauphase. Das KOBV-Projekt hat am 1. April 1997 begonnen und wird am 31. Dezember 2000 enden. Ab 2001 wird der KOBV in eine institutionalisierte Form {\"u}berf{\"u}hrt, die - wie bereits das Projekt - am Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin (ZIB) - angesiedelt wird. Mit dem KOBV wurde ein in technischer wie auch in organisatorischer Hinsicht neuartiger Bibliotheksverbund aufgebaut, der auf der \glqq Internetphilosophie\grqq basiert: Den technischen Kern bildet eine eigens entwickelte Suchmaschine; die Organisation ist dezentral ausgerichtet und gr{\"u}ndet sich auf der Kooperation der KOBV-Partner. In dem Vortrag werden das technische und das organisatorische Verbundkonzept vorgestellt, {\"u}ber die Erfahrungen nach einj{\"a}hriger Betriebsdauer berichtet und ein kurzer Ausblick dar{\"u}ber gegeben, wie es mit dem KOBV weitergeht.}, language = {de} } @misc{Steinbach2000, author = {Steinbach, Marc}, title = {Autos, Ziegen und Streith{\"a}hne}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6087}, number = {00-40}, year = {2000}, abstract = {Das aus den Medien bekannte umstrittene Ziegenproblem (auch Drei-T{\"u}ren-Problem genannt) wird vollst{\"a}ndig analysiert und gel{\"o}st. In der Streitfrage spielen sprachliche Mehrdeutigkeiten der Problemformulierung eine wesentliche Rolle; zudem werden Zufallsereignisse mit willk{\"u}rlicher Information {\"u}ber deren Ergebnisse verwechselt. Tats{\"a}chlich erweisen sich beide strittigen L{\"o}sungen als teilweise richtige Bestandteile der Gesamtl{\"o}sung. Die Argumentation wird in allgemeinverst{\"a}ndlicher Sprache gef{\"u}hrt und anschliessend durch eine formale mathematische Betrachtung erg{\"a}nzt.}, language = {de} } @misc{KochMartinVoss2000, author = {Koch, Thorsten and Martin, Alexander and Voß, Stefan}, title = {SteinLib: An Updated Library on Steiner Tree Problems in Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6056}, number = {00-37}, year = {2000}, abstract = {In this paper we present the {\em SteinLib}, a library of data sets for the Steiner tree problem in graphs. This library extends former libraries on Steiner tree problems by many new interesting and difficult instances, most of them arising from real-world applications. We give a survey on the difficulty of these problem instances by giving references to state-of-the-art software packages that were the first or are currently among the best to solve these instances.}, language = {en} } @misc{KellerReinefeld2000, author = {Keller, Axel and Reinefeld, Alexander}, title = {Anatomy of a Resource Management System for HPC-Clusters}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6063}, number = {00-38}, year = {2000}, abstract = {Workstation clusters are often not only used for high-throughput computing in time-sharing mode but also for running complex parallel jobs in space-sharing mode. This poses several difficulties to the resource management system, which must be able to reserve computing resources for exclusive use and also to determine an optimal process mapping for a given system topology. On the basis of our CCS software, we describe the anatomy of a modern resource management system. Like Codine, Condor, and LSF, CCS provides mechanisms for the user-friendly system access and management of clusters. But unlike them, CCS is targeted at the effective support of space-sharing parallel and even metacomputers. Among other features, CCS provides a versatile resource description facility, topology-based process mapping, pluggable schedulers, and hooks to metacomputer management.}, language = {en} } @misc{KosterZymolka2000, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Stable Multi-Sets}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6047}, number = {00-36}, year = {2000}, abstract = {In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets. For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined. The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks.}, language = {en} } @misc{Helmberg2000, author = {Helmberg, Christoph}, title = {SBmethod --- A C++ Implementation of the Spectral Bundle Method. Manual to Version 1.1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6039}, number = {00-35}, year = {2000}, abstract = {\texttt{SBmethod}, Version 1.1, is an implementation of the spectral bundle method for eigenvalue optimization problems of the form \begin{displaymath} \min_{y\in \mathbf{R}^m}\;\; a\;\lambda_{\max}(C-\sum_{i=1}^{m} A_i y_i)+b^Ty. \end{displaymath} The design variables \$y_i\$ may be sign constrained, \$C\$ and and \$A_i\$ are given real symmetric matrices, \$b\in\mathbf{R}^m\$ allows to specify a linear cost term, and \$a>0\$ is a constant multiplier for the maximum eigenvalue function \$\lambda_{\max}(\cdot)\$. The code is intended for large scale problems and allows to exploit structural properties of the matrices such as sparsity and low rank structure. The manual contains instructions for installation and use of the program. It describes in detail input format, options, and output. The meaning of the variables and parameters is made precise by relating them to a mathematical description of the algorithm in pseudocode.}, language = {en} } @phdthesis{Helmberg2000, author = {Helmberg, Christoph}, title = {Semidefinite Programming for Combinatorial Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6022}, number = {00-34}, year = {2000}, abstract = {This book offers a self-contained introduction to the field of semidefinite programming, its applications in combinatorial optimization, and its computational methods. We equip the reader with the basic results from linear algebra on positive semidefinite matrices and the cone spanned by them. Starting from linear programming, we introduce semidefinite programs and discuss the associated duality theory. We then turn to semidefinite relaxations of combinatorial optimization and illustrate their interrelation. In the second half we deal with computational methods for solving semidefinite programs. First, the interior point approach, its iteration complexity, and implementational issues are discussed. Next, we explain in great detail the spectral bundle method, which is particularly suited for large scale semidefinite programming. One of the most successful techniques in integer linear programming is the cutting plane approach which improves an initial relaxation by adding violated inequalities. We explore possibilities to combine the two solution methods with the cutting plane approach in order to strengthen semidefinite relaxations of combinatorial optimization problems.}, language = {en} } @misc{Schintke2000, author = {Schintke, Florian}, title = {Ermittlung von Programmlaufzeiten anhand von Speicherzugriffen, Microbenchmarks und Simulation vonSpeicherhierarchien}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6018}, number = {00-33}, year = {2000}, abstract = {\\{\bf Zusammenfassung:} Kostenmodelle dienen der Ermittlung von Programmlaufzeiten, zum Vergleich der Effizienz von Algorithmen und zur Analyse des Verhaltens von Speicherhierarchien. Ein neuartiges Kostenmodell ist das Latency-of-Data-Access (LDA) Modell, das mehrere hierarchische Speicherebenen mit unterschiedlichen Latenzzeiten ber{\"u}{}cksichtigt. In dieser Diplomarbeit wird ein Simulator f{\"u}{}r Speicherhierarchien pr{\"a}{}sentiert, der die Berechnung von Programmausf{\"u}{}hrungszeiten nach dem LDA-Modell erlaubt. Mit Hilfe des Simulators wird die These gepr{\"u}{}ft, da\ss{} mit diesem Modell die Ausf{\"u}{}hrungszeit eines Programms ad{\"a}{}quat abgesch{\"a}{}tzt werden kann. Mit dem Simulator ist es erstmals praktikabel m{\"o}{}glich, Programmausf{\"u}{}hrungszeiten nach dem LDA-Modell zu bestimmen. Der Simulator kann f{\"u}{}r Systeme mit unterschiedlichen Speicherarchitekturen konfiguriert werden und unterst{\"u}{}tzt Mehrprozessorsysteme mit gemeinsamem Speicher (SMP-Systeme) mit verschiedenen Koh{\"a}{}renzprotokollen. Der Simulator kann mit den Ergebnissen von Microbenchmarks konfiguriert werden, die die Architekturparameter einer Speicherhierarchie messen. Die Ergebnisse best{\"a}{}tigen die These nicht nur f{\"u}{}r Einzelprozessorsysteme, sondern auch f{\"u}{}r SMP-Systeme, wo gleichzeitig interagierende Prozessoren gegenseitig ihre Zugriffssequenz auf Zwischenspeicher beeinflussen. Zus{\"a}{}tzlich wurde eine neue Einsatzm{\"o}{}glichkeit des LDA-Modells entwickelt, um die Ausf{\"u}{}hrungszeit von Programmteilen zu bestimmen. Einzelne Zugriffskosten k{\"o}{}nnen einem mehrerer parallel laufender Modelle zugeordnet werden. Dadurch k{\"o}{}nnen Kosten, die Zugriffe auf einzelne Speicherbereiche verursachen, separat bestimmt werden. Diese Profiling-Technik erlaubt Optimierungen an Datenstrukturen und Speicherzugriffsmustern durch pr{\"a}{}zise und gezielte Informationsproduktion.Cost models are used to determine the execution time of programs, to compare the efficiency of algorithms, and to analyse the behaviour of memory hierarchies. The Latency-of-Data-Access (LDA) model that takes into account multiple hierarchical memory levels with different latencies, is a newly proposed, innovative cost model. In this diploma-thesis, a simulator for memory hierarchies is presented that allows the calculation of execution times using the LDA-model. The simulator is used to prove the claim that the execution time of a program can be accurately estimated with the LDA-model. With the simulator, it is for the first time possible to determine the execution time of programs with this model in a practical way. The simulator can be configured for systems with various cache architectures and supports shared memory (SMP) multiprocessor systems with different cache coherence protocols. The simulator can be configured with the results from microbenchmarks which measure the architectural properties of a memory hierarchy. The results confirm the claim not only for single processor systems, but also for SMP systems, where concurrently interacting processors influence each others cache access sequence. Additionally, a new field of usage of the LDA-model was developed to determine execution times of program parts. Single access costs can be assigned to one of several parallel running models. As an example the costs of accesses to different memory areas can be split and determined separately. This profiling technique allows to optimise data structures and memory access patterns of sequential and parallel SMP programs by precise production of information.}, language = {de} } @misc{HegeMerzkyZachow2000, author = {Hege, Hans-Christian and Merzky, Andre and Zachow, Stefan}, title = {Distributed Visualization with OpenGL Vizserver: Practical Experiences}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5992}, number = {00-31}, year = {2000}, abstract = {The increasing demand for distributed solutions in computing technology does not stop when it comes to visualization techniques. However, the capabilities of todays applications to perform remote rendering are limited by historical design legacys. Especially the popular X11 protokoll, which has been proven to be extremely flexible and usefull for remote 2D graphics applications, breaks down for the case of remote 3D rendering. In this white paper, we give a short overview of generic remote rendering technologies available today, and compare their performance to the recently released vizserver by SGI: a network extension to the SGI OpenGL rendering engines.}, language = {en} } @misc{Gatermann2000, author = {Gatermann, Karin}, title = {Counting stable solutions of sparse polynomial systems in chemistry}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6007}, number = {00-32}, year = {2000}, abstract = {The polynomial differential system modelling the behavior of a chemical reaction is given by graphtheoretic structures. The concepts from toric geometry are applied to study the steady states and stable steady states. Deformed toric varieties give some insight and enable graph theoretic interpretations. The importance of the circuits in the directed graph are emphazised. The counting of positive solutions of a sparse polynomial system by B.\ Sturmfels is generalized to the counting of stable positive solutions in case of a polynomial differential equation. The generalization is based on a method by sparse resultants to detect whether a system may have a Hopf bifurcation. Special examples from chemistry are used to illustrate the theoretical results.}, language = {en} } @misc{Potra2000, author = {Potra, Florian}, title = {A path-following method for linear complementarity problems based on the affine invariant Kantorovich Theorem}, doi = {10.1007/s10107-003-0501-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5981}, number = {00-30}, year = {2000}, abstract = {A path following algorithm for linear complementarity problems is presented. Given a point \$z\$ that approximates a point \$z(\tau)\$ on the central path with complementarity gap \$\tau\$, one determines a parameter \$\theta\in (0,1)\$ so that this point satisfies the hypothesis of the affine invariant Kantorovich Theorem for the equation defining \$z((1-\theta)\tau)\$. It is shown that \$\theta\$ is bounded below by a multiple of \$n^{-1/2}\$, where \$n\$ is the dimension of the problem. Since the hypothesis of of the Kantorovich Theorem is satisfied the sequence generated by Newton's method, or by the simplified Newton method, will converge to \$z((1-\theta)\tau)\$. We show that the number of steps required to obtain an acceptable approximation of \$z((1-\theta)\tau)\$ is bounded above by a number independent of \$n\$. Therefore the algorithm has \$O(\sqrt{n}L)\$-iteration complexity. The parameters of the algorithm can be determined in such a way that only one Newton step is needed each time the complementarity gap is decreased.}, language = {en} } @misc{Wagler2000, author = {Wagler, Annegret}, title = {The Classes of Critically and Anticritically Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5975}, number = {00-29}, year = {2000}, abstract = {We focus on two new types of extremal graphs with respect to perfectness: critically and anticritically perfect graphs that lose their perfectness by simply deleting and adding an arbitrary edge, respectively. We present examples and study properties in order to compare critically and anticritically perfect graphs with minimally imperfect graphs, another type of extremal graphs with respect to perfectness. We discuss two attempts to characterize the classes of all critically and anticritically perfect graphs and give a brief overview on classes of perfect graphs which contain critically or anticritically perfect graphs.}, language = {en} } @misc{SeebassBeckGellermannetal.2000, author = {Seebass, Martin and Beck, Rudolf and Gellermann, Johanna and Nadobny, Jacek and Wust, Peter}, title = {Electromagnetic phased arrays for regional hyperthermia -- optimal frequency and antenna arrangement}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5961}, number = {00-28}, year = {2000}, abstract = {In this paper we investigate the effects of the three-dimensional arrangement of antennas and frequency on temperature distributions that can be achieved in regional hyperthermia using an electromagnetic phased array. We compare the results of power-based and temperature-based optimization. Thus we are able to explain the discrepancies between previous studies favouring more antenna rings on the one hand and more antennas per ring on the other hand. We analyze the sensitivity of the results with respect to changes in amplitudes and phases as well as patient position. This analysis can be used for different purposes. First, it provides additional criteria for selecting the optimal frequency. Second, it can be used for specifying the required phase and amplitude accuracy for a real phased array system. Furthermore, it may serve as a basis for technological developments in order to reduce both types of sensitivities described above.}, language = {en} } @misc{StallingSeebassZoeckleretal.2000, author = {Stalling, Detlev and Seebass, Martin and Z{\"o}ckler, Malte and Hege, Hans-Christian}, title = {Hyperthermia Treatment Planning with HyperPlan - User's Manual}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5957}, number = {00-27}, year = {2000}, abstract = {HyperPlan is a software system for performing 3D-simulations and treatment planning in regional hyperthermia. It allows the user to understand the complex effects of electromagnetic wave propagation and heat transport inside a patient's body. Optimized power amplitudes and phase settings can be calculated for the BSD radiowave applicators Sigma 60 and Sigma 2000 (eye-applicator). HyperPlan is built on top of the modular, object-oriented visualization system Amira. This system already contains powerful algorithms for image processing, geometric modelling and 3D graphics display. HyperPlan provides a number of hyperthermia-specific modules, allowing the user to create 3D tetrahedral patient models suitable for treatment planning. In addition, all numerical simulation modules required for hyperthermia simulation are part of HyperPlan. This guide provides a step-by-step introduction to hyperthermia planning using HyperPlan. It also describes the usage of the underlying visualization system Amira.}, language = {en} } @misc{Huisinga2000, author = {Huisinga, Wilhelm}, title = {The Essential Spectral Radius and Asymptotic Properties of Transfer Operators}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5942}, number = {00-26}, year = {2000}, abstract = {The statistical behavior of deterministic and stochastic dynamical systems may be described using transfer operators, which generalize the notion of Frobenius Perron and Koopman operators. Since numerical techniques to analyze dynamical systems based on eigenvalues problems for the corresponding transfer operator have emerged, bounds on its essential spectral radius became of interest. This article shows that they are also of great theoretical interest. We give an analytical representation of the essential spectral radius in \$L^{1}\!(\mu)\$, which then is exploited to analyze the asymptotical properties of transfer operators by combining results from functional analysis, Markov operators and Markov chain theory. In particular, it is shown, that an essential spectral radius less than \$1\$, constrictiveness and some weak form'' of the so--called Doeblin condition are equivalent. Finally, we apply the results to study three main problem classes: deterministic systems, stochastically perturbed deterministic systems and stochastic systems.}, language = {en} } @misc{IlgenfritzKerlerMuellerPreusskeretal.2000, author = {Ilgenfritz, Ernst-Michael and Kerler, Werner and M{\"u}ller-Preussker, Michael and St{\"u}ben, Hinnerk}, title = {Parallel tempering and decorrelation of topological charge in full QCD}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5930}, number = {00-25}, year = {2000}, abstract = {The improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering is studied on \$10^4\$ and \$12^4\$ lattices. As an indicator for decorrelation the topological charge is used.}, language = {en} } @misc{SperberDalitz2000, author = {Sperber, Wolfram and Dalitz, Wolfgang}, title = {Portale, Search Engines und Math-Net}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5923}, number = {00-24}, year = {2000}, abstract = {Wie sucht ein Wissenschaftler im Internet die ben"otigten Informationen f{\"u}r seine Arbeit? Welche relevanten Informationen gibt es {\"u}berhaupt im Web? Sind daf{\"u}r solche Suchmaschinen wie AltaVista, Google oder HotBot die richtigen Werkzeuge? Die Antwort der Mathematiker heisst Math-Net, ein Informations- und Kommunikationssystem f{\"u}r die Mathematik. Math-Net besteht zun{\"a}chst aus den Informationen von Personen und Institutionen, die ihre f{\"u}r die Mathematik relevanten Informationen dort bereitstellen wollen. Das soll i.a. auf den Web-Servern der Personen oder Institutionen geschehen. Hierin unterscheidet sich die Situation im Math-Net nicht von der im WWW insgesamt. Im Math-Net sollen aber die Informationen in einheitlicher Weise erschlossen werden. Dazu gibt es sowohl f{\"u}r Server als auch f{\"u}r die Dokumente Empfehlungen f{\"u}r deren Strukturierung. Die lokalen Informationen werden dann im Math-Net durch automatische Verfahren gesammelt, ausgewertet und indexiert. Diese Indexe sind die Basis f{\"u}r die Math-Net Dienste. Das sind Search Engines und Portale, die einen qualifizierten und effizienten Zugang zu den Informationen im Math-Net bieten. Die Math-Net Dienste sind auf die Mathematik spezialisiert. Im Gegensatz zu den oben erw{\"a}hnten universellen Suchmaschinen decken sie nur einen winzigen Bruchteil des Web ab, aber daf{\"u}r den f{\"u}r die Mathematik relevanten Teil. Math-Net ist mehr als nur Search Engine oder Portal zu Informationen in der Mathematik. Es ist auch ein Informations- und Kommunikationssystem sowie ein Publikationsmedium f{\"u}r die Mathematik. Die mathematische Community hat sich in der Math-Net Initiative organisiert. Diese Initiative wird von der International Mathematical Union (IMU), der weltweiten Dachorganisation der mathematischen Gesellschaften, koordiniert. Die Entwicklung des Math-Net wird von dem breiten Konsens der Mathematiker getragen, den Zugang zu der f{\"u}r die Mathematik relevanten Information zu erleichtern und zu verbessern.}, language = {de} } @misc{Luegger2000, author = {L{\"u}gger, Joachim}, title = {{\"U}ber Suchmaschinen, Verb{\"u}nde und die Integration von Informationsangeboten}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5919}, number = {00-23}, year = {2000}, abstract = {Die Entwicklung einer bibliothekarischen Suchmaschine ist das technisch-organisatorische Herzt{\"u}ck des Kooperativen Bibliotheksverbundes Berlin-Brandenburg (KOBV). Auf dem Wege {\"u}ber diese Innovation verfolgen die L{\"a}nder Berlin und Brandenburg und ihre Bibliotheken das Ziel, ihr Bibliothekswesen zu erneuern und zu reorganisieren. Die Entwicklung der Suchmaschine ist f{\"u}r die Partner im KOBV-Projekt kein Selbstzweck, sondern nur Mittel zum Zweck - insbesondere, um die heterogene Welt der in Berlin und in Brandenburg eingesetzten integrierten Bibliotheksinformationssysteme harmonisch miteinender zu verbinden. Mit der KOBV-Suchmaschine sind informationstechnische Sichtweisen und Methoden entstanden, die sich potentiell auch auf die {\"u}berregionale Arbeit des KOBV auswirken k{\"o}nnen und in Kooperation mit den Bibliotheksverb{\"a}nden auf die Zusammenarbeit der Verb{\"u}nde insgesamt. Der Artikel konzentriert sich am Beispiel der KOBV-Such!'ma!'schine auch auf diesen Aspekt. Auf die Bibliotheken kommen mit dem Internet und dem World Wide Web f{\"u}r sie neuartige Medien, Mittel und Aufgaben zu, in erster Linie aus dem Bereich der Wissenschaften und der wissenschaftlichen Fachgesellschaften. Die Herausforderung besteht darin, die neuen elektronischen Informationen und Angebote zu integrieren. Das Stichwort hierzu lautet digitale Bibliothek bzw. virtuelle Fachbibliothek. Auch zu der Diskussion um diese aktuelle Entwicklung will der Artikel einen Beitrag leisten.}, language = {de} } @misc{HoeselKosterLeenseletal.2000, author = {Hoesel, Stan P.M. van and Koster, Arie M.C.A. and Leensel, Robert L.M.J. van de and Savelsbergh, Martin W.P.}, title = {Polyhedral Results for the Edge Capacity Polytope}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5907}, number = {00-22}, year = {2000}, abstract = {Network loading problems occur in the design of telecommunication networks, in many different settings. The polyhedral structure of this problem is important in developing solution methods for the problem. In this paper we investigate the polytope of the problem restricted to one edge of the network (the edge capacity problem). We describe classes of strong valid inequalities for the edge capacity polytope, and we derive conditions under which these constraints define facets. As the edge capacity problem is a relaxation of the network loading problem, their polytopes are intimately related. We, therefore, also give conditions under which the inequalities of the edge capacity polytope define facets of the network loading polytope. Furthermore, some structural properties are derived, such as the relation of the edge capacity polytope to the knapsack polytope. We conclude the theoretical part of this paper with some lifting theorems, where we show that this problem is polynomially solvable for most of our classes of valid inequalities. In a computational study the quality of the constraints is investigated. Here, we show that the valid inequalities of the edge capacity polytope are not only important for solving the edge capacity problem, but also for the network loading problem, showing that the edge capacity problem is an important subproblem.}, language = {en} } @misc{LangErdmann2000, author = {Lang, Jens and Erdmann, Bodo}, title = {Adaptive Linearly Implicit Methods for Heat and Mass Transfer Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5892}, number = {00-21}, year = {2000}, abstract = {Dynamical process simulation of complex real-life problems often requires the use of modern algorithms, which automatically adapt both the time and space discretization in order to get error-controlled approximations of the solution. In this paper, a combination of linearly implicit time integrators of Rosenbrock type and adaptive multilevel finite elements based on a posteriori error estimates is presented. This approach has proven to work quite satisfactorily for a wide range of challenging practical problems. We show the performance of our adaptive method for two applications that arise in the study of flame balls and brine transport in porous media.}, language = {en} } @misc{MeyerSchnurreReissbrodtetal.2000, author = {Meyer, Michael and Schnurre, R{\"u}diger and Reissbrodt, Rolf and Trowitzsch-Kienast, Wolfram}, title = {Computer-aided design of novel siderophores: Pyridinochelin}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5887}, number = {00-20}, year = {2000}, abstract = {Pyridinochelin, a novel catecholate type siderophore, has been designed on the basis of the active analog enterobactin. Growth promotion tests indicate that this synthetic siderophore feeds various pathogenic bacteria effectively with iron even though it lacks one catecholate group compared to enterobactin. The superposition of the siderophore structures suggests that the structure of the skeleton connecting the catecholate groups might be an important factor for the iron transport.}, language = {en} } @misc{KrumkeNoltemeierWirth2000, author = {Krumke, Sven and Noltemeier, Hartmut and Wirth, Hans-Christoph}, title = {Graphentheoretische Konzepte und Algorithmen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5873}, number = {00-19}, year = {2000}, abstract = {Das vorliegende Skript bietet eine Einf{{\"u}}hrung in die Graphentheorie und graphentheoretische Algorithmen. Im zweiten Kapitel werden Grundbegriffe der Graphentheorie vorgestellt. Das dritte Kapitel besch{{\"a}}ftigt sich mit der Existenz von Wegen in Graphen. Hier wird auch die L{{\"o}}suung des ber{{\"u}}hmten K{{\"o}}nigsberger Br{{\"u}}ckenproblems aufgezeigt und der Satz von Euler bewiesen. Im vierten Kapitel wird gezeigt, wie man auf einfache Weise die Zusammenhangskomponenten eines Graphen bestimmen kann. Im Kapitel sechs wird dann sp{{\"a}}ter mit der Tiefensuche ein Verfahren vorgestellt, das schneller arbeitet und mit dessen Hilfe man noch mehr Informationen {{\"u}}ber die Struktur eines Graphen gewinnen kann. In den folgenden Kapiteln werden Algorithmen vorgestellt, um minimale aufspannenden B{{\"a}}ume, k{{\"u}}rzeste Wege und maximale Fl{{\"u}}sse in Graphen zu bestimmen. Am Ende des Skripts wird ein kurzer Einblick in die planaren Graphen und Graphhomomorphismen geboten.}, language = {de} } @misc{Koster2000, author = {Koster, Arie M.C.A.}, title = {Re-Optimization of Signaling Transfer Points}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5863}, number = {00-18}, year = {2000}, abstract = {In this paper we describe the results of a computational study towards the (re)optimization of signaling transfer points (STPs) in telecommunication networks. The best performance of an STP is achieved whenever the traffic load is evenly distributed among the internal components. Due to the continuously changing traffic pattern, the load of the components has to be re-optimized on a regular basis. Besides the balancing objective also the number of rearrangements have to be taken into account. In this paper we present two alternative formulations to deal with both requirements. Computational results show that for both formulations (near) optimal solutions can be obtained within reasonable time limits.}, language = {en} } @misc{OPUS4-974, title = {Jahresbericht 1999}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9749}, number = {1999}, year = {2000}, language = {de} } @misc{Steinbach2000, author = {Steinbach, Marc}, title = {Hierarchical Sparsity in Multistage Convex Stochastic Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5837}, number = {00-15}, year = {2000}, abstract = {Interior point methods for multistage stochastic programs involve KKT systems with a characteristic global block structure induced by dynamic equations on the scenario tree. We generalize the recursive solution algorithm proposed in an earlier paper so that its linear complexity extends to a refined tree-sparse KKT structure. Then we analyze how the block operations can be specialized to take advantage of problem-specific sparse substructures. Savings of memory and operations for a financial engineering application are discussed in detail.}, language = {en} } @misc{MeyerSteinkeBrandletal.2000, author = {Meyer, Michael and Steinke, Thomas and Brandl, Maria and S{\"u}hnel, J{\"u}rgen}, title = {Density functional study of guanine and uracil quartets and of guanine quartet metal/ion complexes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5842}, number = {00-16}, year = {2000}, abstract = {The structures and interaction energies of guanine and uracil quartets have been determined by B3LYP hybrid density functional calculations. The total interaction energy \$\Delta\$E\$^{T}\$ of the \$\it{C}\$\$_{4h}\$-symmetric guanine quartet consisting of Hoogsteen type base pairs with two hydrogen bonds between two neighbour bases is -66.07 kcal/mol at the highest level. The uracil quartet with C6-H6...O4 interactions between the individual bases has only a small interaction energy of -20.92 kcal/mol and the interaction energy of -24.63 kcal/mol for the alternative structure with N3-H3...O4 hydrogen bonds is only slightly more negative. Cooperative effects contribute between 10 and 25 \\% to all interaction energies. Complexes of metal ions with G-quartets can be classified into different structure types. The one with Ca\$^{2+}\$ in the central cavity adopts a \$\it{C}\$\$_{4h}\$-symmetric structure with coplanar bases, whereas the energies of the planar and non-planar Na\$^{+}\$ complexes are almost identical. The small ions Li\$^{+}\$, Be\$^{2+}\$, Cu\$^{+}\$ and Zn\$^{2+}\$ prefer a non-planar \$\it{S}\$\$_{4}\$-symmetric structure. The lack of co-planarity prevents probably a stacking of these base quartets. The central cavity is too small for K\$^{+}\$ ions and therefore this ion favours in contrast to all other investigated ions a \$\it{C}\$\$_{4}\$-symmetric complex, which is 4.73 kcal/mol more stable than the \$\it{C}\$\$_{4h}\$-symmetric one. The distance 1.665 {\AA} between K\$^{+}\$ and the root mean squares plane of the guanine bases is approximately half of the distance between two stacked G-quartets. The total interaction energy of alkaline earth ion complexes exceeds the ones with alkali ions. Within both groups of ions the interaction energy decreases with an increasing row position in the periodic table. The B3LYP and BLYP methods lead to similar structures and energies. Both methods are suitable for hydrogen-bonded biological systems. Compared with the before mentioned methods the HCTH functional leads to longer hydrogen bonds and different relative energies for two U-quartets. Finally we calculated also structures and relative energies with the MMFF94 forcefield. Contrary to all DFT methods, MMFF94 predicts bifurcated C-H...O contacts in the uracil quartet. In the G-quartet the MMFF94 hydrogen bond distances N2-H22...N7 are shorter than the DFT distances, whereas the N1-H1...O6 distances are longer.}, language = {en} } @misc{OevermannKleinBergeretal.2000, author = {Oevermann, Michael and Klein, Rupert and Berger, Marsha and Goodman, Jonathan}, title = {A Projection Method for Two-Phase Incompressible Flow with Surface Tension and Sharp Interface Resolution}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5851}, number = {00-17}, year = {2000}, abstract = {We present a fully second order projection method for the simulation of two-phase incompressible flow with surface tension. The Navier-Stokes equations are solved with a projection method on a fixed Cartesian grid. The free interface between the two fluids is tracked with a level set approach. The conditions at the interface for the pressure, the pressure gradient, and the velocity are explicitly incorporated into the scheme leading to a sharp representation of the pressure discontinuity and the interfacial force. The scheme in the presented form does not introduce additional points in the standard finite difference stencils. Computational results are compared with analytic solutions for a static round bubble, damped surface waves, and Rayleigh-Taylor instabilities.}, language = {en} } @misc{BienstockBley2000, author = {Bienstock, Daniel and Bley, Andreas}, title = {Capacitated Network Design with Multicast Commodities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5823}, number = {00-14}, year = {2000}, abstract = {This paper addresses the problem of designing a minimum cost network whose capacities are sufficiently large to allow a feasible routing of a given set of multicast commodities. A multicast commodity consists of a set of two or mo re terminals that need to be connected by a so called broadcast tree, which consumes on all of its edges a capacity as large as the demand value associated with that commodity. We model the network design problem with multicast commodities as the problem of packing capacitated Steiner trees in a graph. In the first part of the paper we present three mixed-integer programming formulations for this problem. The first natural formulation uses only one integer capacity variable for each edge and and one binary tree variable for each commodity-edge pair. Applying well-known techniques from the Steiner tree problem, we then develop a stronger directed and a multicommodity flow based mixed-integer programming formulation. In the second part of the paper we study the associated polyhedra and derive valid and even facet defining inequalities for the natural formulation. Finally, we describe separation algorithms for these inequalities and present computational results that demonstrate the strength of our extended formulations.}, language = {en} } @misc{GalliatDeuflhard2000, author = {Galliat, Tobias and Deuflhard, Peter}, title = {Adaptive hierarchical cluster analysis by Self-Organizing Box Maps}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5815}, number = {00-13}, year = {2000}, abstract = {The present paper aims at an extension of {\sc Kohonen's} Self-Organizing Map (SOM) algorithm to be called Self-Organizing Box Map (SOBM) algorithm; it generates box codebooks in lieu of point codebooks. Box codebooks just like point codebooks indirectly define a Voronoi tessellation of the input space, so that each codebook vector represents a unique set of points. Each box codebook vector comprises a multi-dimensional interval that approximates the related partition of the Voronoi tessellation. Upon using the automated cluster identification method that has recently been developed by the authors, the codebook vectors can be grouped in such a way that each group represents a point cluster in the input space. Since the clustering usually depends on the size of the SOM, one cannot be sure, whether the clustering comes out to be optimal. Refinement of part of the identified clusters would often improve the results. This paper presents the concept of an adaptive multilevel cluster algorithm that performs such refinements automatically. Moreover the paper introduces a concept of essential dimensions and suggests a method for their identification based on our herein suggested box codebooks. Applications of the algorithm to molecular dynamics will be described in a forthcoming paper.}, language = {en} } @misc{Rusch2000, author = {Rusch, Beate}, title = {Kooperativer Bibliotheksverbund Berlin-Brandenburg: Erste Erfahrungen im Produkionsbetrieb}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5793}, number = {00-11}, year = {2000}, abstract = {In diesem Artikel wird der Status des Projekts Kooperativer Bibliotheksverbund Berlin-Brandenburg beschrieben, der im November 1999 mit der KOBV-Suchmaschine seinen produktiven Betrieb aufgenommen hat. Die Recherchem{\"o}glichkeiten im WWW werden erl{\"a}utert, Zugriffszahlen genannt und Entwicklungsperspektiven skizziert. Dieser Bericht entspricht der schriftlichen Fassung eines gleichnamigen Vortrages, der auf dem 1. Gemeinsamen Kongreß der Bundesvereinigung Deutscher Bibliotheksverb{\"a}nde e.V. und der Deutschen Gesellschaft f{\"u}r Informationswissenschaft und Informationspraxis e.V. Information und {\"O}ffentlichkeit gehalten wurde, der vom 20. bis 23. M{\"a}rz 2000 in Leipzig stattfand.}, language = {de} } @misc{BrandtBrandt2000, author = {Brandt, Andreas and Brandt, Manfred}, title = {Asymptotic Results and a Markovian Approximation for the M(n)/M(n)/s+GI System}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5801}, number = {00-12}, year = {2000}, abstract = {In this paper for the \$M(n)/M(n)/s+GI\$ system, i.e.\ for a \$s\$-server queueing system where the calls in the queue may leave the system due to impatience, we present new asymptotic results for the intensities of calls leaving the system due to impatience and a Markovian system approximation where these results are applied. Furthermore, we present a new proof for the formulae of the conditional density of the virtual waiting time distributions, recently given by Movaghar for the less general \$M(n)/M/s+GI\$ system. Also we obtain new explicit expressions for refined virtual waiting time characteristics as a byproduct.}, language = {en} } @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{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} }