@misc{KuberekRadu2005, author = {Kuberek, Monika and Radu, Raluca}, title = {Online-Fernleihe im KOBV - Handbuch f{\"u}r Bibliotheken}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8681}, number = {05-34}, year = {2005}, abstract = {\documentclass[12pt]{article} \usepackage{german} \parindent=0pt \begin{document} Im KOBV wird f{\"u}r die Online-Fernleihe der Zentrale-Fernleihserver (ZFL-Server) der Firma Sisis eingesetzt. Die Software ist in der KOBV-Zentrale installiert. Der ZFL-Server dient im KOBV sowohl f{\"u}r die Bestellung von Monographien als auch f{\"u}r die Bestellung von Aufsatzkopien aus Zeitschriften. Prinzipiell gibt es zwei Verfahren, mit denen sich Bibliotheken an der Online-Fernleihe beteiligen k{\"o}nnen: das E-Mail-Verfahren und das SLNP-Verfahren. Auf beide wird im Handbuch eingegangen. Die Online-Fernleihe wurde im KOBV eingef{\"u}hrt, um die Fernleihe f{\"u}r die Benutzer zu beschleunigen, das Verfahren f{\"u}r die Bibliotheksmitarbeiter zu vereinfachen und den Arbeitsaufwand zu reduzieren. Sie basiert darauf, dass eine Bestellung anhand eines gefundenen Treffers ausgel{\"o}st wird - d.h. die bibliographischen Daten sind bereits verifiziert und in einem Katalog nachgewiesen. Anschlie\"send werden die Fernleihbestellungen {\"u}ber den ZFL-Server automatisch ausgef{\"u}hrt und verwaltet - sowohl in der regionalen KOBV-Fernleihe als auch in der verbund{\"u}bergreifenden Fernleihe mit den deutschen Bibliotheksverb{\"u}nden. Der ZFL-Server besteht aus verschiedenen technischen Komponenten. Eine dieser Komponenten ist das Bibliothekskonto, eine Internetanwendung, in der die Bestellverwaltung des ZFL-Servers im Internet f{\"u}r die Bibliotheksbediensteten transparent gemacht wird. Sowohl f{\"u}r die aktive als auch f{\"u}r die passive Fernleihe ist im Bibliothekskonto der Status der Bearbeitung zu jedem Zeitpunkt ersichtlich, z.B. in welcher Bibliothek sich die Bestellung gerade befindet, wann sie dort eingegangen ist und wann sie weggeschickt wurde, ob mit positivem oder negativem Ergebnis. Das Bibliothekskonto ist damit f{\"u}r die Bibliothek ein komfortables Instrument zum {\"U}berwachen der Fernleihbestellungen, in dem sie zudem - falls notwendig - in den Bestellvorgang eingreifen kann. Dazu hat jede Bibliothek im Bibliothekskonto eine eigene, Passwort-gesch{\"u}tzte Dienstoberfl{\"a}che. Das vorliegende Handbuch beschreibt die Vorg{\"a}nge der Bestellverwaltung im Bibliothekskonto. Es richtet sich an Bibliotheksmitarbeiter, die sich mit den einzelnen Arbeitsschritten der Online-Fernleihe vertraut machen wollen. Dar{\"u}ber hinaus ist es zum Nachschlagen gedacht, wenn sich in der t{\"a}glichen Arbeit Unklarheiten ergeben. \end{document}}, language = {de} } @misc{BurgschweigerGnaedigSteinbach2005, author = {Burgschweiger, Jens and Gn{\"a}dig, Bernd and Steinbach, Marc}, title = {Nonlinear Programming Techniques for Operative Planning in Large Drinking Water Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8657}, number = {05-31}, year = {2005}, abstract = {Mathematical decision support for operative planning in water supply systems is highly desirable but leads to very difficult optimization problems. We propose a nonlinear programming approach that yields practically satisfactory operating schedules in acceptable computing time even for large networks. Based on a carefully designed model supporting gradient-based optimization algorithms, this approach employs a special initialization strategy for convergence acceleration, special minimum up and down time constraints together with pump aggregation to handle switching decisions, and several network reduction techniques for further speed-up. Results for selected application scenarios at Berliner Wasserbetriebe demonstrate the success of the approach.}, language = {en} } @misc{BurgschweigerGnaedigSteinbach2005, author = {Burgschweiger, Jens and Gn{\"a}dig, Bernd and Steinbach, Marc}, title = {Optimierte Tagesplanung im Berliner Trinkwassernetz}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8668}, number = {05-32}, year = {2005}, abstract = {Der Artikel beschreibt ein mathematisches Optimierungssystem zur Betriebsplanung in großen Wassernetzen, das bei den Berliner Wasserbetrieben eingesetzt wird. F{\"u}r das Berliner Versorgungsnetz werden Optimierungsergebnisse vorgestellt.}, language = {de} } @misc{OPUS4-979, title = {Jahresbericht 2004}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9799}, number = {2004}, year = {2005}, language = {de} } @misc{BoevHodoroabaImhof2005, author = {Boev, Ivan and Hodoroaba, Lavinia and Imhof, Andres}, title = {Der KOBV-Metadaten-Austausch-Parser (KMA-Parser): Ein Werkzeug f{\"u}r Metadata-Sharing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8636}, number = {05-29}, year = {2005}, abstract = {\\ Zusammenfassung: Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) betreibt f{\"u}r das KOBV-Portal einen Austausch von Beschreibungen zu elektronischen Ressourcen (Metadaten), der zwisc zwischen verschiedenen Informationsportalen in der Region durchgef{\"u}hrt wird. Die unterschiedlichen Informationsportale verwenden verschiedene Metadaten-Schemata und Austausch-Formate f{\"u}r ihre Ressourcebeschreibungen. Um die Heterogenit{\"a}t der Metadaten zu {\"u}berwinden, wurde der KOBV-Metadaten-Austausch-Parser (KMA-Parser) entwickelt. Andere Metadaten-Schemata werden auf das KOBV-Metadaten-Schema abgebildet. Der KMA-Parser f{\"u}hrt gegebenenfalls eine Format-Transformation durch, konvertiert die Inhalte einzelner Elemente {\"u}ber Konkordanzen und erzeugt neue Metadaten-Elemente aus vorhandenen Feldern. Er validiert den Inhalt auf Vollst{\"a}ndigkeit und steuert den Austausch der Metadaten zwischen den Portalen. Der Umwandlungsprozess funktioniert jedoch nicht nur in die Richtung des KOBV-Portals, sondern auch in die entgegengesetzte Richtung. Der Artikel beschreibt die einzelnen Vorg{\"a}nge im KMA-Parser und schildert die Erfahrungen im Umgang mit der Heterogenit{\"a}t von Metadaten. Die gewonnenen Erfahrungen verweisen auf grundlegende Perspektiven in der universellen Zusammenarbeit von Informationsanbietern und -providern.The Kooperativer Bibliotheksverbund Berlin-Brandenburg (KOBV) has built a framework for a bi-directional exchange workflow of electronic resources{\AE} descriptions (metadata) between the KOBV Portal and other Information Portals in the region. The Information Portals use different exchange formats, metadata schemata and controlled vocabularies for their descriptions of resources. In order to overcome this metadata heterogeneity, an application, the KOBV Metadata Exchange Parser (KMA-Parser), has been developed. The KMA-Parser maps the local portals{\AE} metadata schemata into the metadata schema of the KOBV Portal. If necessary, it transforms the exchange format, converts contents of individual elements by means roduces new metadata elements on the basis of existent elements. It checks elements{\AE} contents on completeness and controls the metadata exchange between the portals. However, the transformation process takes place not only towards the KOBV Portal, but al so vice versa. The article describes the individual processes in the KMA Parser and depicts the experiences in handling the metadata{\AE}s heterogeneity. The experiences gathered give an idea of the prospects for a universal cooperation between information suppliers and providers.}, language = {de} } @misc{AchterbergKochMartin2005, author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander}, title = {MIPLIB 2003}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8625}, number = {05-28}, year = {2005}, abstract = {This paper reports on the fourth version of the Mixed Integer Programming Library. Since ({\sc miplib}) is to provide a concise set of challenging problems, it became necessary to purge instances that became too easy. We present an overview of the 27 new problems and statistical data for all 60 instances.}, language = {en} } @misc{SchaedleZschiedrich2005, author = {Sch{\"a}dle, Achim and Zschiedrich, Lin}, title = {Additive Schwarz method for scattering problems using the PML method at interfaces}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8613}, number = {05-27}, year = {2005}, abstract = {Scattering problems in integrated optics can be modeled in simple cases by the Helmholtz equation. The computational domain is truncated by a non-reflecting boundary condition. We investigate Schwarz algorithms with a sort of DtN operator, realized by the PML-method, at the interfaces of the sub-domains as an iterative solver.}, language = {en} } @misc{LopezFernandezPalenciaSchaedle2005, author = {Lopez-Fernandez, Maria and Palencia, Cesar and Sch{\"a}dle, Achim}, title = {A spectral order method for inverting sectorial Laplace transforms}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8607}, number = {05-26}, year = {2005}, abstract = {Laplace transforms which admit a holomorphic extension to some sector strictly containing the right half plane and exhibiting a potential behavior are considered. A spectral order, parallelizable method for their numerical inversion is proposed. The method takes into account the available information about the errors arising in the evaluations. Several numerical illustrations are provided.}, language = {en} } @misc{ImhofMalo2005, author = {Imhof, Andres and Malo, Markus}, title = {Aufbau einer verteilten Fachredaktion f{\"u}r freie Internet-Ressourcen im KOBV-Portal}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8599}, number = {05-25}, year = {2005}, abstract = {Die KOBV-Zentrale betreibt mit dem KOBV-Portal neben der Metasuche in freien Online-Katalogen und Datenbanken ein Nachweisinstrument f{\"u}r elektronische Ressourcen, die von den Bibliotheken Berlin-Brandenburgs lizenziert sind und dar{\"u}ber hinaus diejenigen, die frei zug{\"a}nglich sowie wissenschaftlich relevant sind. Die Erschließung der freien Ressourcen {\"u}bernimmt eine kooperative Fachredaktion, die sich aus FachreferentInnen und -lektorInnen aus der Region rekrutiert. Dabei {\"u}bernimmt jede beteiligte Person die Betreuung einer oder mehrerer Fachgruppen der Dewey Decimal-Classification (DDC) eigenverantwortlich. Die Aufgabe aller FachredakteurInnen besteht in der inhaltlichen Beschreibung, der Klassifizierung, der Vergabe von Schlagworten und der regelm{\"a}ßigen Reevaluation der einzelnen Ressourcen. Die KOBV-Zentrale hat hierf{\"u}r einen Kriterienkatalog entwickelt, der als Grundlage f{\"u}r die Beurteilung von elektronischen Ressourcen dient. Erschlossen werden die Ressourcen schließlich {\"u}ber ein webbasierte Eingabe-Tool, dem Metadata-Tool der KOBV-Zentrale. {\"U}ber eine Mailingliste wird der Abstimmungsbedarf untereinander gedeckt und Diskussionen gef{\"u}hrt, die das Projekt weiterf{\"u}hren sollen. Der Artikel beschreibt das Konzept der kooperativen Fachredaktion f{\"u}r freie Ressourcen, die Vorg{\"a}nge und die Arbeiten, die f{\"u}r die Initiierung notwendig waren.}, language = {de} } @misc{HildebrandtPolthierWardetzky2005, author = {Hildebrandt, Klaus and Polthier, Konrad and Wardetzky, Max}, title = {On the Convergence of Metric and Geometric Properties of Polyhedral Surfaces}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8587}, number = {05-24}, year = {2005}, abstract = {We provide conditions for convergence of polyhedral surfaces and their discrete geometric properties to smooth surfaces embedded in Euclidian \$3\$-space. The notion of totally normal convergence is shown to be equivalent to the convergence of either one of the following: surface area, intrinsic metric, and Laplace-Beltrami operators. We further s how that totally normal convergence implies convergence results for shortest geodesics, mean curvature, and solutions to the Dirichlet problem. This work provides the justification for a discrete theory of differential geometric operators defined on polyhedral surfaces based on a variational formulation.}, language = {en} } @misc{GroetschelRoggenbuckSperber2005, author = {Gr{\"o}tschel, Martin and Roggenbuck, Robert and Sperber, Wolfram}, title = {Entwicklung und Aufbau des Internet-Dienstes "Math\&Industry"}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8573}, number = {05-23}, year = {2005}, abstract = {Die Anwendung mathematischer Methoden und Verfahren wird immer mehr zur Voraussetzung innovativer Produkte und Dienstleistungen. Um neue Produkte und Dienstleistungen zu entwickeln, m{\"u}ssen die Produktions- und technologischen Prozesse mathematisch modelliert, beschrieben und optimiert werden. Diesen Umstand Rechnung tragend, hat das Bundesministerium f{\"u}r Bildung und Forschung (BMBF) 1993 begonnen, den Einsatz mathematischer Verfahren und Methoden in der Mathematik {\"u}ber ein spezielles Mathematikprogramm zu f{\"o}rdern. Inzwischen hat die vierte F{\"o}rderperiode des Mathematikprogramms begonnen. \par Das Medium Internet und insbesondere das WWW sind f{\"u}r die Sichtbarkeit und Transparenz wissenschaftlicher Resultate in den letzten zehn Jahren immer wichtiger geworden. Wer nicht im Web "'sichtbar"' ist, l{\"a}uft Gefahr, nicht wahrgenommen zu werden. Intention und Ziel des durchgef{\"u}hrten Projekts war es, ein Konzept f{\"u}r eine qualitativ hochwertige und umfassende Darstellung des BMBF Mathematikprogramms, insbesondere der in den Projekten erzielten Ergebnisse, zu entwickeln und zu realisieren und damit den Stellenwert und die Akzeptanz mathematischer Forschung in der Gesellschaft zu festigen und den Wissenstransfer zwischen mathematischer Forschung sowie Forschung und Entwicklung in der Wirtschaft und dem Dienstleistungsbereich zu f{\"o}rdern.}, language = {de} } @misc{BleyPattloch2005, author = {Bley, Andreas and Pattloch, Marcus}, title = {Modellierung und Optimierung der X-WiN Plattform}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8551}, number = {05-21}, year = {2005}, abstract = {In diesem Artikel werden die Optimierungsmodelle und -verfahren beschrieben, die bei der Planung des Kernnetzes und der Zugangsinfrastruktur des X-WiN verwendet wurden.}, language = {de} } @misc{BorndoerferGroetschelPfetsch2005, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {Public Transport to the fORe!}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8562}, number = {05-22}, year = {2005}, abstract = {Can OR methods help the public transport industry to break even? The article gives evidence that there exist significant potentials in this direction, which can be harnessed by a combination of modern mathematical methods and local planning knowledge. Many of the planning steps in public transport are classical combinatorial problems, which can be solved in unprecedented size and quality due the rapid progress in large-scale optimization. Three examples on vehicle scheduling, duty scheduling, and integrated vehicle and duty scheduling illustrate the level that has been reached and the improvements that can be achieved today. Extensions of such methods to further questions of strategic, online, and market-oriented planning are currently investigated. In this way, OR can make a significant contribution to answer the basic but extremely difficult question ``What is a good public transport network?.}, language = {en} } @misc{Achterberg2005, author = {Achterberg, Tobias}, title = {Conflict Analysis in Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8537}, number = {05-19}, year = {2005}, abstract = {Conflict analysis for infeasible subproblems is one of the key ingredients in modern SAT solvers to cope with large real-world instances. In contrast, it is common practice for today's mixed integer programming solvers to just discard infeasible subproblems and the information they reveal. In this paper we try to remedy this situation by generalizing the SAT infeasibility analysis to mixed integer programming. We present heuristics for branch-and-cut solvers to generate valid inequalities from the current infeasible subproblem and the associated branching information. SAT techniques can then be used to strengthen the resulting cuts. We performed computational experiments which show the potential of our method: On feasible MIP instances, the number of required branching nodes was reduced by 50\\% in the geometric mean. However, the total solving time increased by 15\\%. on infeasible MIPs arising in the context of chip verification, the number of nodes was reduced by 90\\%, thereby reducing the solving time by 60\\%.}, language = {en} } @misc{BorndoerferGroetschelPfetsch2005, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {A Column-Generation Approach to Line Planning in Public Transport}, doi = {/10.1287/trsc.1060.0161}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8522}, number = {05-18}, year = {2005}, abstract = {The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported.}, language = {en} } @misc{WeberMeyer2005, author = {Weber, Marcus and Meyer, Holger}, title = {ZIBgridfree - Adaptive Conformation Analysis with qualified Support of Transition States and Thermodynamic Weights}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8514}, number = {05-17}, year = {2005}, abstract = {This paper introduces a new algorithm of conformational analysis based on mesh-free methods as described in [M. Weber. Mehless methods in Conformation Dynamics.(2005)]. The adaptive decomposition of the conformational space by softly limiting functions avoids trapping effects and allows adaptive refinement strategies. These properties of the algorithm makes ZIBgridfree particularly suitable for the complete exploration of high-dimensional conformational space. The adaptive control of the algorithm benefits from the tight integration of molecular simulation and conformational analysis. An emphasized part of the analysis is the Robust Perron Cluster Analysis (PCCA+) based on the work of Peter Deuflhard and Marcus Weber. PCCA+ supports an almost-characteristic cluster definition with an outstanding mapping of transition states. The outcome is expressed by the metastable sets of conformations, their thermodynamic weights and flexibility.}, language = {en} } @misc{LangePolthier2005, author = {Lange, Carsten and Polthier, Konrad}, title = {Anisotropic Smoothing of Point Sets}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8508}, number = {05-16}, year = {2005}, abstract = {The use of point sets instead of meshes became more popular during the last years. We present a new method for anisotropic fairing of a point sampled surface using an anisotropic geometric mean curvature flow. The main advantage of our approach is that the evolution removes noise from a point set while it detects and enhances geometric features of the surface such as edges and corners. We derive a shape operator, principal curvature properties of a point set, and an anisotropic Laplacian of the surface. This anisotropic Laplacian reflects curvature properties which can be understood as the point set analogue of Taubin's curvature-tensor for polyhedral surfaces. We combine these discrete tools with techniques from geometric diffusion and image processing. Several applications demonstrate the efficiency and accuracy of our method.}, language = {en} } @phdthesis{Koch2005, author = {Koch, Thorsten}, title = {Rapid Mathematical Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8346}, number = {04-58}, year = {2005}, abstract = {The thesis deals with the implementation and application of out-of-the-box tools in linear and mixed integer programming. It documents the lessons learned and conclusions drawn from five years of implementing, maintaining, extending, and using several computer codes to solve real-life industrial problems. By means of several examples it is demonstrated how to apply algebraic modeling languages to rapidly devise mathematical models of real-world problems. It is shown that today's MIP solvers are capable of solving the resulting mixed integer programs, leading to an approach that delivers results very quickly. Even though, problems are tackled that not long ago required the implementation of specialized branch-and-cut algorithms. In the first part of the thesis the modeling language Zimpl is introduced. Chapter 2 contains a complete description of the language. In the subsequent chapter details of the implementation are described. Both theoretical and practical considerations are discussed. Aspects of software engineering, error prevention, and detection are addressed. In the second part several real-world projects are examined that employed the methodology and the tools developed in the first part. Chapter 4 presents three projects from the telecommunication industry dealing with facility location problems. Chapter 5 characterizes questions that arise in UMTS planning. Problems, models, and solutions are discussed. Special emphasis is put on the dependency of the precision of the input data and the results. Possible reasons for unexpected and undesirable solutions are explained. Finally, the Steiner tree packing problem in graphs, a well-known hard combinatorial problem, is revisited. A formerly known, but not yet used model is applied to combine switchbox wire routing and via minimization. All instances known from the literature are solved by this approach, as are some newly generated bigger problem instances.}, language = {en} } @misc{SchielaWeiser2005, author = {Schiela, Anton and Weiser, Martin}, title = {Superlinear Convergence of the Control Reduced Interior Point Method for PDE Constrained Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8490}, number = {05-15}, year = {2005}, abstract = {A thorough convergence analysis of the Control Reduced Interior Point Method in function space is performed. This recently proposed method is a primal interior point pathfollowing scheme with the special feature, that the control variable is eliminated from the optimality system. Apart from global linear convergence we show, that this method converges locally almost quadratically, if the optimal solution satisfies a function space analogue to a non-degeneracy condition. In numerical experiments we observe, that a prototype implementation of our method behaves in compliance with our theoretical results.}, language = {en} } @misc{GaertnerKaibel2005, author = {G{\"a}rtner, Bernd and Kaibel, Volker}, title = {Two New Bounds for the Random-Edge Simplex Algorithm}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8483}, number = {05-14}, year = {2005}, abstract = {We prove that the Random-Edge simplex algorithm requires an expected number of at most \$13n/sqrt(d)\$ pivot steps on any simple d-polytope with n vertices. This is the first nontrivial upper bound for general polytopes. We also describe a refined analysis that potentially yields much better bounds for specific classes of polytopes. As one application, we show that for combinatorial d-cubes, the trivial upper bound of \$2^d\$ on the performance of Random-Edge can asymptotically be improved by any desired polynomial factor in d.}, language = {en} } @misc{Koster2005, author = {Koster, Arie M.C.A.}, title = {Wavelength Assignment in Multi-Fiber WDM Networks by Generalized Edge Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8478}, number = {05-13}, year = {2005}, abstract = {In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results for stars are also of interest for general meshed topologies. We show that wavelength assignment with at most two links per lightpath can be modeled as a generalized edge coloring problem. By this relation, we show that for a network with an even number of fibers at all links and at most two links per lightpath, all lightpaths can be assigned a wavelength without conversion. Moreover, we derive a lower bound on the number of lightpaths to be converted for networks with arbitrary numbers of fibers at the links. A comparison with linear programming lower bounds reveals that the bounds coincide for problems with at most two links per lightpath. For meshed topologies, the cumulative lower bound over all star subnetworks equals the best known solution value for all realistic wavelength assignment instances available, by this proving optimality.}, language = {en} } @misc{AndrzejakHermannSahai2005, author = {Andrzejak, Artur and Hermann, Ulf and Sahai, Akhil}, title = {FeedbackFlow - An Adaptive Workflow Generator for System Management}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8467}, number = {05-12}, year = {2005}, abstract = {We describe a prototypical framework that further automates system management by composing complex management tasks from elementary actions, and executing composite tasks with feedback-awareness. {\sl FEEDBACKFLOW} implements a general closed control loop of \emph{planning - execution - result validation - replanning}, and generates workflows of system management actions in an adaptive manner. System-dependent behaviour of the loop is specified by declarative description of the domain (essentially descriptions of available actions), and statement of the goal. We evaluate the design of this framework on examples taken from resource construction in Utility Computing environments, and discuss the challenges we have encountered. Our implementation utilizes external components such as \emph{MBP}, a \emph{PDDL}-conform planner, and \emph{Triana}, a workflow specification and execution framework. An alternative approach involving \emph{BPEL4WS} is discussed.}, language = {en} } @misc{HelmbergRoehl2005, author = {Helmberg, Christoph and R{\"o}hl, Stefan}, title = {A Case Study of Joint Online Truck Scheduling and Inventory Management for Multiple Warehouses}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8454}, number = {05-11}, year = {2005}, abstract = {For a real world problem --- transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand --- we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost function that is based on minimizing the expected number of pallets that still need transportation. For speed, the convex relaxation is solved approximately by a bundle approach yielding an online schedule in 5 to 12 minutes for up to 3 warehouses and 40000 articles; in contrast, computation times of state of the art LP-solvers are prohibitive for online application. In extensive numerical experiments on a real world data stream, the approximate solutions exhibit negligible loss in quality; in long term simulations the proposed method reduces the average number of pallets needing transportation due to short term demand to less than half the number observed in the data stream.}, language = {en} } @misc{SchaedleLopezFernandezLubich2005, author = {Sch{\"a}dle, Achim and Lopez-Fernandez, Maria and Lubich, Christian}, title = {Fast and oblivious convolution quadrature}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8437}, number = {05-09}, year = {2005}, abstract = {We give an algorithm to compute \$N\$ steps of a convolution quadrature approximation to a continuous temporal convolution using only \$O(N\, \log N)\$ multiplications and \$O(\log N)\$ active memory. The method does not require evaluations of the convolution kernel, but instead \$O(\log N)\$ evaluations of its Laplace transform, which is assumed sectorial. The algorithm can be used for the stable numerical solution with quasi-optimal complexity of linear and nonlinear integral and integro-differential equations of convolution type. In a numerical example we apply it to solve a subdiffusion equation with transparent boundary conditions.}, language = {en} } @misc{LopezFernandezLubichPalenciaetal.2005, author = {Lopez-Fernandez, Maria and Lubich, Christian and Palencia, Cesar and Sch{\"a}dle, Achim}, title = {Fast Runge-Kutta approximation of inhomogeneous parabolic equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8443}, number = {05-10}, year = {2005}, abstract = {The result after \$N\$ steps of an implicit Runge-Kutta time discretization of an inhomogeneous linear parabolic differential equation is computed, up to accuracy \$\varepsilon\$, by solving only \$\$O\Big(\log N\, \log \frac1\varepsilon \Big) \$\$ linear systems of equations. We derive, analyse, and numerically illustrate this fast algorithm.}, language = {en} } @misc{Busch2005, author = {Busch, Hubert}, title = {Abschlußbericht des DFN-Projekts "Virtueller Supercomputer Berlin - Hannover"}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8337}, number = {04-57}, year = {2005}, abstract = {Mit der Installation des neuen Hochleistungsrechners f{\"u}r die norddeutschen L{\"a}nder (HLRN) steht den Wissenschaftlern ein außergew{\"o}hnlich leistungsf{\"a}higes System zur Verf{\"u}gung. Durch die Verteilung der Rechenelemente auf zwei verschiedene Standorte in Berlin (ZIB) und Hannover (RRZN) entstehen jedoch auch neue Herausforderungen f{\"u}r den Betrieb und die effiziente Nutzung des Rechners. Inhalt dieses Projektes ist die Erforschung und L{\"o}sung der durch die Verteilung des Systems hervorgerufenen Probleme (z.B. Scheduling, Kommunikation, I/O). Es werden effiziente L{\"o}sungen zur Bereitstellung eines virtuellen, hoch-performanten und transparenten Systems entwickelt, die auf vergleichbare Installationen {\"u}bertragbar sind.}, language = {de} } @misc{Wolf2005, author = {Wolf, Thomas}, title = {Partial and complete linearization of PDEs based on conservation laws}, arxiv = {http://arxiv.org/abs/nlin.SI/0501034}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8409}, number = {05-06}, year = {2005}, abstract = {A method based on infinite parameter conservation laws is described to factor linear differential operators out of nonlinear partial differential equations (PDEs) or out of differential consequences of nonlinear PDEs. This includes a complete linearization to an equivalent linear PDE (-system) if that is possible. Infinite parameter conservation laws can be computed, for example, with the computer algebra package {\sc ConLaw}.}, language = {en} } @misc{Wolf2005, author = {Wolf, Thomas}, title = {Integrable quadratic Hamiltonians with a linear Lie-Poisson bracket}, doi = {10.1007/s10714-006-0293-2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8414}, number = {05-07}, year = {2005}, abstract = {Quadratic Hamiltonians with a linear Lie-Poisson bracket have a number of applications in mechanics. For example, the Lie-Poisson bracket \$e(3)\$ includes the Euler-Poinsot model describing motion of a rigid body around a fixed point under gravity and the Kirchhoff model describes the motion of a rigid body in ideal fluid. Advances in computer algebra algorithms, in implementations and hardware, together allow the computation of Hamiltonians with higher degree first integrals providing new results in the search for integrable models. A computer algebra module enabling related computations in a 3-dimensional vector formalism is described.}, language = {en} } @misc{AncoWolf2005, author = {Anco, Stephen and Wolf, Thomas}, title = {Some classifications of hyperbolic vector evolution equations}, arxiv = {http://arxiv.org/abs/nlin.SI/0412015}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8429}, number = {05-08}, year = {2005}, abstract = {Motivated by recent work on integrable flows of curves and 1+1 dimensional sigma models, several \$O(N)\$-invariant classes of hyperbolic equations \$Utx=f(U,Ut,Ux)\$ for an \$N\$-component vector \$U(t,x)\$ are considered. In each class we find all scaling-homogeneous equations admitting a higher symmetry of least possible scaling weight. Sigma model interpretations of these equations are presented.}, language = {en} } @misc{TsuchidaWolf2005, author = {Tsuchida, Takayuki and Wolf, Thomas}, title = {Classification of polynomial integrable systems of mixed scalar and vector evolution equations. I}, arxiv = {http://arxiv.org/abs/nlin.SI/0412003}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8391}, number = {05-05}, year = {2005}, abstract = {We perform a classification of integrable systems of mixed scalar and vector evolution equations with respect to higher symmetries. We consider polynomial systems that are homogeneous under a suitable weighting of variables. This paper deals with the KdV weighting, the Burgers (or potential KdV or modified KdV) weighting, the Ibragimov--Shabat weighting and two unfamiliar weightings. The case of other weightings will be studied in a subsequent paper. Making an ansatz for undetermined coefficients and using a computer package for solving bilinear algebraic systems, we give the complete lists of \$2^{\mbox{\scriptsize nd }}\$order systems with a \$3^{\mbox{\scriptsize rd }}\$order or a \$4^{\mbox{\scriptsize th }}\$order symmetry and \$3^{\mbox{\scriptsize rd }}\$order systems with a \$5^{\mbox{\scriptsize th }}\$order symmetry. For all but a few systems in the lists, we show that the system (or, at least a subsystem of it) admits either a Lax representation or a linearizing transformation. A thorough comparison with recent work of Foursov and Olver is made.}, language = {en} } @misc{Bley2005, author = {Bley, Andreas}, title = {Inapproximability Results for the Inverse Shortest Paths Problem with Integer Length and Unique Shortest Paths}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8388}, number = {05-04}, year = {2005}, abstract = {We study the complexity of two Inverse Shortest Paths (ISP) problems with integer arc lengths and the requirement for uniquely determined shortest paths. Given a collection of paths in a directed graph, the task is to find positive integer arc lengths such that the given paths are uniquely determined shortest paths between their respective terminals. The first problem seeks for arc lengths that minimize the length of the longest of the prescribed paths. In the second problem, the length of the longest arc is to be minimized. We show that it is \$np-hard\$ to approximate the minimal longest path length within a factor less than \$8/7\$ or the minimal longest arc length within a factor less than \$9/8\$. This answers the (previously) open question whether these problems are \$np-hard\$ or not. We also present a simple algorithm that achieves an \$\mathcal{O}(|V|)\$-approximation guarantee for both variants. Both ISP problems arise in the planning of telecommunication networks with shortest path routing protocols. Our results imply that it is \$\mathcal{NP}\$-hard to decide whether a given path set can be realized with a real shortest path routing protocol such as OSPF, IS-IS, or RIP.}, language = {en} } @misc{HodoroabaImhofMalo2005, author = {Hodoroaba, Lavinia and Imhof, Andres and Malo, Markus}, title = {Das Profil des KOBV-Portals}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8292}, number = {04-54}, year = {2005}, abstract = {Zahlreiche lokale, nationale und internationale Informationsportale existieren mit zum Teil gleichen Angeboten und Dienstleistungen nebeneinander. Da der Aufbau und Betrieb von Portalen kostspielig ist, sollten die einzelnen Dienstleistungen abgestimmt und sinnvoll untereinander vernetzt werden. F{\"u}r eine solch anzustrebende Kooperation unter Portalen ist es notwendig, ein jeweils eigenes Portalprofil zu definieren, um bei einer Gegen{\"u}berstellung der Profile die Abgrenzungen und Verkn{\"u}pfungspunkte deutlich werden zu lassen. Die KOBV-Zentrale m{\"o}chte mit der Profilbeschreibung des KOBV-Portals beginnen und so die eigenen Angebote des regionalen Portals mit denen anderer auf sinnvolle Weise verkn{\"u}pfen. F{\"u}r diese Positionsbestimmung werden die Dienstleistungen, die Zielgruppe, die Kriterien f{\"u}r die Ressourcenauswahl sowie die Abgrenzung zu anderen Portalen dargelegt.}, language = {de} } @misc{Kanaeva2005, author = {Kanaeva, Zara}, title = {Ranking: Google und CiteSeer}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8315}, number = {04-55}, year = {2005}, abstract = {Im Rahmen des klassischen Information Retrieval wurden verschiedene Verfahren f{\"u}r das Ranking sowie die Suche in einer homogenen strukturlosen Dokumentenmenge entwickelt. Die Erfolge der Suchmas chine Google haben gezeigt, dass die Suche in einer zwar inhomogenen aber zusammenh{\"a}ngenden Dokumentenmenge wie dem Internet unter Ber{\"u}cksichtigung der Dokumentenverbindungen (Links) sehr ef fektiv sein kann. Unter den von der Suchmaschine Google realisierten Konzepten ist ein Verfahren zum Ranking von Suchergebnissen (PageRank), das in diesem Artikel kurz erkl{\"a}rt wird. \% Dar{\"u}ber hinaus wird auf die Konzepte eines Systems namens CiteSeer eingegangen, welches automatisch bibliographische Angaben indexiert (engl. \glqq Autonomous Citation Indexing\grqq, ACI). Letzteres erzeugt aus einer Menge von nicht-vernetzten wissenschaftlichen Dokumenten eine zusammenh{\"a}ngende Dokumentenmenge und erm{\"o}glicht den Einsatz von Ranking-Verfahren, die auf den von Google genutzten Verfahren basieren.}, language = {de} } @misc{Kanaeva2005, author = {Kanaeva, Zara}, title = {Verteilter Dokumenten Speicher: Erfahrungen mit der Suchmaschine Fast}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8326}, number = {04-56}, year = {2005}, abstract = {In diesem Bericht wurden Erfahrungen mit der Suchmaschine FAST im Rahmen des Projektes Verteilter Contentspeicher sowie die Suchmaschine FAST beschrieben. Das Ziel des Projektes Verteilter Contentspeicher war die Speicherung, Erschließung und das Angebot der digitalen Best{\"a}nde der Journale und Dokumente der KOBV-Bibliotheken zu erm{\"o}glichen. Die Eignung der Suchmaschine FAST f{\"u}r das Projektvorhaben wurde systematisch und gr{\"u}ndlich getestet, indem verschiedene Dokumentmengen mit FAST indexiert wurden.}, language = {de} } @misc{FrieseRambau2005, author = {Friese, Philipp and Rambau, J{\"o}rg}, title = {Online-Optimization of Multi-Elevator Transport Systems with Reoptimization Algorithms based on Set-Partitioning Models}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8373}, number = {05-03}, year = {2005}, abstract = {We develop and experimentally compare policies for the control of a system of \$k\$ elevators with capacity one in a transport environment with \$\ell\$ floors, an idealized version of a pallet elevator system in a large distribution center of the Herlitz PBS AG in Falkensee. Each elevator in the idealized system has an individual waiting queue of infinite capacity. On each floor, requests arrive over time in global waiting queues of infinite capacity. The goal is to find a policy that, without any knowledge about future requests, assigns an elevator to each req uest and a schedule to each elevator so that certain expected cost functions (e.g., the average or the maximal flow times) are minimized. We show that a reoptimization policy for minimizing average sq uared waiting times can be implemented to run in real-time (\$1\,s\$) using dynamic column generation. Moreover, in discrete event simulations with Poisson input it outperforms other commonly used polic ies like multi-server variants of greedy and nearest neighbor.}, language = {en} } @misc{Baum2004, author = {Baum, Daniel}, title = {Multiple Semi-flexible 3D Superposition of Drug-sized Molecules}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8278}, number = {04-52}, year = {2004}, abstract = {In this paper we describe a new algorithm for multiple semi-flexible superpositioning of drug-sized molecules. The algorithm identifies structural similarities of two or more molecules. When comparing a set of molecules on the basis of their three-dimensional structures, one is faced with two main problems. (1) Molecular structures are not fixed but flexible, i.e., a molecule adopts different forms. To address this problem, we consider a set of conformers per molecule. As conformers we use representatives of conformational ensembles, generated by the program ZIBMol. (2) The degree of similarity may vary considerably among the molecules. This problem is addressed by searching for similar substructures present in arbitrary subsets of the given set of molecules. The algorithm requires to preselect a reference molecule. All molecules are compared to this reference molecule. For this pairwise comparison we use a two-step approach. Clique detection on the correspondence graph of the molecular structures is used to generate start transformations, which are then iteratively improved to compute large common substructures. The results of the pairwise comparisons are efficiently merged using binary matching trees. All common substructures that were found, whether they are common to all or only a few molecules, are ranked according to different criteria, such as number of molecules containing the substructure, size of substructure, and geometric fit. For evaluating the geometric fit, we extend a known scoring function by introducing weights which allow to favor potential pharmacophore points. Despite considering the full atomic information for identifying multiple structural similarities, our algorithm is quite fast. Thus it is well suited as an interactive tool for the exploration of structural similarities of drug-sized molecules.}, language = {en} } @misc{BosseGroetschelHenk2004, author = {Bosse, Hartwig and Gr{\"o}tschel, Martin and Henk, Martin}, title = {Polynomial Inequalities Representing Polyhedra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8284}, number = {04-53}, year = {2004}, abstract = {Our main result is that every \$n\$-dimensional polytope can be described by at most \$2n-1\$ polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an \$n\$-dimensional pointed polyhedral cone we prove the bound \$2n-2\$ and for arbitrary polyhedra we get a constructible representation by \$2n\$ polynomial inequalities.}, language = {en} } @misc{Steidinger2004, author = {Steidinger, Alexander}, title = {Data Management for Processing Molecules}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8358}, number = {05-01}, year = {2004}, abstract = {Molecular dynamics simulations of possible ligands for proteins yield large amounts of data in the form of trajectories which are further processed in order to find metastable conformations. These conformations can then be used for docking between ligand and protein. Around this core computation procedure lots of other data have to be managed. It should also be possible for external users not involved in program development to perform computations. As a paradigm for other fields where a similar constitution of program usage and data processing is found we present a software architecture for data generation, access and management. Requirements for this system include: Ease of use, graphical user interface, persistent storage of data concerning molecules, users, programs, program parameters, metadata, and results. A mere storage in the file system would render a quick overview of data more or less impossible. On the other hand, storing large amounts of binary data in a database doesn't yield any advantage concerning speed of access. Therefore, a hybrid approach combining file system and database is appropriate. The system should be easily extensible by inserting new applications which can be controlled and whose results can be collected and stored. The software system described here consists of different components, the presentation layer (graphical user interface), the business logic, the persistence layer (relational database plus file system), and an interface to the compute cluster (batch system for parallel processing). We will discuss the alternatives and take a closer look at the components.}, language = {en} } @misc{SchmidtEhrenbergHege2004, author = {Schmidt-Ehrenberg, Johannes and Hege, Hans-Christian}, title = {Visual Analysis of Molecular Conformations by Means of a Dynamic Density Mixture Model}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8361}, number = {05-02}, year = {2004}, abstract = {We propose an approach for transforming the sampling of a molecular conformation distribution into an analytical model based on Hidden Markov Models. The model describes the sampled shape density as a mixture of multivariate unimodal densities. Thus, it delivers an interpretation of the sampled density as a set of typical shapes that appear with different probabilities and are characterized by their geometry, their variability and transition probabilities between the shapes. The gained model is used to identify atom groups of constant shape that are connected by metastable torsion angles. Based on this description an alignment for the original sampling is computed. As it takes into account the different shapes contained in the sampled set, this alignment allows to compute reasonable average shapes and meaningful shape density plots. Furthermore, it enables us to visualize typical conformations.}, language = {en} } @misc{Hochmuth2004, author = {Hochmuth, Reinhard}, title = {Homogenization for a Nonlocal Coupling Model}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8251}, number = {04-50}, year = {2004}, abstract = {In [7,8,12] homogenization techniques are applied to derive an anisotropic variant of the bio-heat transfer equation as asymptotic result of boundary value problems providing a microscopic description for microvascular tissue. In view of a future application on treatment planning in hyperthermia, we investigate here the homogenization limit for a coupling model, which takes additionally into account the influence of convective heat transfer in medium size blood vessels. This leads to second order elliptic boundary value problems with nonlocal boundary conditions on parts of the boundary. Moreover, we present asymptotic estimates for first order correctors.}, language = {en} } @misc{BaumeisterCordes2004, author = {Baumeister, Timm and Cordes, Frank}, title = {A new Model for the Free Energy of Solvation and its Application in Protein Ligand Scoring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8265}, number = {04-51}, year = {2004}, abstract = {A new and time efficient model to evaluate the free energy of solvation has been developed. The solvation free energy is separated into an electrostatic term, a hydrogen bond term, and a rest-term, combining both entropic and van der Waals effects. The electrostatic contribution is evaluated with a simplified boundary element method using the partial charges of the MMFF94 force field. The number of hydrogen bonds and the solvent excluded surface area over the surface atoms are used in a linear model to estimate the non-electrostatic contribution. This model is applied to a set of 213 small and mostly organic molecules, yielding an rmsd of 0.87kcal/mol and a correlation with experimental data of r=0.951. The model is applied as a supplementary component of the free energy of binding to estimate binding constants of protein ligand complexes. The intermolecular interaction energy is evaluated by using the MMFF94 force field.}, language = {en} } @misc{OrlowskiWessaely2004, author = {Orlowski, Sebastian and Wess{\"a}ly, Roland}, title = {An Integer Programming Model for Multi-Layer Network Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8248}, number = {04-49}, year = {2004}, abstract = {We present an integer linear programming model for the design of multi-layer telecommunication networks. The formulation integrates hardware, capacity, routing, and grooming decisions in \emph{any} n umber of network layers. Practical hardware restrictions and cost can accurately be taken into account for technologies based on connection-oriented routing protocols.}, language = {en} } @misc{PruefertTroeltzschWeiser2004, author = {Pr{\"u}fert, Uwe and Tr{\"o}ltzsch, Fredi and Weiser, Martin}, title = {The convergence of an interior point method for an elliptic control problem with mixed control-state constraints}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8223}, number = {04-47}, year = {2004}, abstract = {The paper addresses primal interior point method for state constrained PDE optimal control problems. By a Lavrentiev regularization, the state constraint is transformed to a mixed control-state constraint with bounded Lagrange multiplier. Existence and convergence of the central path are established, and linear convergence of a short-step pathfollowing method is shown. The behaviour of the regularizations are demonstrated by numerical examples.}, language = {en} } @misc{BurgschweigerGnaedigSteinbach2004, author = {Burgschweiger, Jens and Gn{\"a}dig, Bernd and Steinbach, Marc}, title = {Optimization Models for Operative Planning in Drinking Water Networks}, doi = {10.1007/s11081-008-9040-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8237}, number = {04-48}, year = {2004}, abstract = {The topic of this paper is minimum cost operative planning of pressurized water supply networks over a finite horizon and under reliable demand forecast. Since this is a very hard problem, it is desirable to employ sophisticated mathematical algorithms, which in turn calls for carefully designed models with suitable properties. The paper develops a nonlinear mixed integer model and a nonlinear programming model with favorable properties for gradient-based optimization methods, based on smooth component models for the network elements. In combination with further nonlinear programming techniques (to be reported elsewhere), practically satisfactory near-optimum solutions even for large networks can be generated in acceptable time using standard optimization software on a PC workstation. Such an optimization system is in operation at Berliner Wasserbetriebe.}, language = {en} } @misc{Steinbach2004, author = {Steinbach, Marc}, title = {On PDE Solution in Transient Optimization of Gas Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8215}, number = {04-46}, year = {2004}, abstract = {Operative planning in gas distribution networks leads to large-scale mixed-integer optimization problems involving a hyperbolic PDE defined on a graph. We consider the NLP obtained under prescribed combinatorial decisions---or as relaxation in a branch and bound framework, addressing in particular the KKT systems arising in primal-dual interior methods. We propose a custom solution algorithm using sparse local projections, based on the KKT systems' structual properties induced by the discretized gas flow equations in combination with the underlying network topology. The numerical efficiency and accuracy of the algorithm are investigated, and detailed computational comparisons with a control space method and with the multifrontal solver MA27 are provided.}, language = {en} } @misc{WolleKosterBodlaender2004, author = {Wolle, Thomas and Koster, Arie M.C.A. and Bodlaender, Hans L.}, title = {A Note on Contraction Degeneracy}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8180}, number = {04-43}, year = {2004}, abstract = {The parameter contraction degeneracy -- the maximum minimum degree over all minors of a graph -- is a treewidth lower bound and was first defined in (Bodlaender, Koster, Wolle, 2004). In experiments it was shown that this lower bound improves upon other treewidth lower bounds. In this note, we examine some relationships between the contraction degeneracy and connected components of a graph, block s of a graph and the genus of a graph. We also look at chordal graphs, and we study an upper bound on the contraction degeneracy and another lower bound for treewidth. A data structure that can be used for algorithms computing the degeneracy and similar parameters, is also described.}, language = {en} } @misc{KosterWolleBodlaender2004, author = {Koster, Arie M.C.A. and Wolle, Thomas and Bodlaender, Hans L.}, title = {Degree-Based Treewidth Lower Bounds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8193}, number = {04-44}, year = {2004}, abstract = {Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving treewidth lower bounds. In this paper, we investigate a total of nine graph parameters, providing lower bounds for treewidth. The parameters have in common that they all are the vertex-degree of some vertex in a subgra ph or minor of the input graph. We show relations between these graph parameters and study their computational complexity. To allow a practical comparison of the bounds, we developed heuristic algorithms for those parameters that are NP-hard to compute. Computational experiments show that combining the treewidth lower bounds with minors can considerably improve the lower bounds.}, language = {en} } @misc{BodlaenderKoster2004, author = {Bodlaender, Hans L. and Koster, Arie M.C.A.}, title = {On the Maximum Cardinality Search Lower Bound for Treewidth}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8201}, number = {04-45}, year = {2004}, abstract = {The Maximum Cardinality Search algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbors becomes visited. An MCS-ordering of a graph is an ordering of the vertices that can be generated by the Maximum Cardinality Search algorithm. The visited degree of a vertex \$v\$ in an MCS-ordering is the number of neighbors of \$v\$ that are before \$v\$ in the ordering. The visited degree of an MCS-ordering \$\psi\$ of \$G\$ is the maximum visited degree over all vertices \$v\$ in \$\psi\$. The maximum visited degree over all MCS-orderings of graph \$G\$ is called its {\em maximum visited degree}. Lucena (2003) showed that the treewidth of a graph \$G\$ is at least its maximum visited degree. We show that the maximum visited degree is of size \$O(\log n)\$ for planar graphs, and give examples of planar graphs \$G\$ with maximum visited degree \$k\$ with \$O(k!)\$ vertices, for all \$k\in \Bbb{N}\$. Given a graph \$G\$, it is NP-complete to determine if its maximum visited degree is at least \$k\$, for any fixed \$k\geq 7\$. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete. We also propose and experimentally analyses some heuristics for the problem. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.}, language = {en} } @misc{KochWessaely2004, author = {Koch, Thorsten and Wess{\"a}ly, Roland}, title = {Hierarchical Infrastructure Planning in Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8174}, number = {04-42}, year = {2004}, abstract = {In this article, strategical infrastructure planning problems in the design of large-scale telecommunication networks are discussed based on experiences from three projects with industrial partners: The access network planning of the German Gigabit-Wissenschaftsnetz (G-WiN) for DFN (Verein zur F{\"o}rderung eines Deutschen Forschungsnetzes e.V.), the mobile network switching center location planning project for E-Plus Mobilfunk, and the fixed network switching center location planning project for TELEKOM AUSTRIA. We introduce a mathematical model for a hierarchical multi-commodity capacitated facility location problem, present adaptions of this basic model to the specific requirements within the different projects and discuss the individual peculiarities and model decisions made. Eventually, we present and discuss computational results of three associated case studies, illustrating '"how we did the job`` with mathematical methods.}, language = {en} } @misc{KosterZymolka2004, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Provably Good Solutions for Wavelength Assignment in Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8155}, number = {04-40}, year = {2004}, abstract = {In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formula tion by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation approach. Computational experiments show that the value of the linear relaxation states a good lower bound and can often prove optimality of the best solution generated heuristically.}, language = {en} } @misc{KosterZymolka2004, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8160}, number = {04-41}, year = {2004}, abstract = {In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of the most promising formulation. In many cases, a non-zero lower bound on the number of required converters is generated this way. For several instances, we in fact prove optimality since the lower bound equals the best known solution value.}, language = {en} } @misc{WeberRungsarityotinSchliep2004, author = {Weber, Marcus and Rungsarityotin, Wasinee and Schliep, Alexander}, title = {Perron Cluster Analysis and Its Connection to Graph Partitioning for Noisy Data}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8140}, number = {04-39}, year = {2004}, abstract = {The problem of clustering data can be formulated as a graph partitioning problem. Spectral methods for obtaining optimal solutions have reveceived a lot of attention recently. We describe Perron Cluster Cluster Analysis (PCCA) and, for the first time, establish a connection to spectral graph partitioning. We show that in our approach a clustering can be efficiently computed using a simple linear map of the eigenvector data. To deal with the prevalent problem of noisy and possibly overlapping data we introduce the min Chi indicator which helps in selecting the number of clusters and confirming the existence of a partition of the data. This gives a non-probabilistic alternative to statistical mixture-models. We close with showing favorable results on the analysis of gene expressi on data for two different cancer types.}, language = {en} } @misc{JoswigPfetsch2004, author = {Joswig, Michael and Pfetsch, Marc}, title = {Computing Optimal Morse Matchings}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8120}, number = {04-37}, year = {2004}, abstract = {Morse matchings capture the essential structural information of discrete Morse functions. We show that computing optimal Morse matchings is NP-hard and give an integer programming formulation for the problem. Then we present polyhedral results for the corresponding polytope and report on computational results.}, language = {en} } @misc{LutzWestphal2004, author = {Lutz-Westphal, Brigitte}, title = {Die Mathematik der k{\"u}rzesten Wege. Inhalte und Methoden f{\"u}r den Unterricht}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8116}, number = {04-36}, year = {2004}, abstract = {Wie findet man den optimalen Weg im U-Bahnnetz? Das Problem wird als Graph modelliert und dann eine Breitensuche durchgef{\"u}hrt. Will man Wegl{\"a}ngen oder Fahrzeiten mitber{\"u}cksichtigen, so braucht man den Algorithmus von Dijkstra f{\"u}r gewichtige Graphen. Beim Nachdenken {\"u}ber diese Algorithmen werden auch Fragestellungen der Graphentheorie ber{\"u}hrt. In einem zweiten Abschnitt werden methodische Hinweise f{\"u}r den Unterricht in der Sekundarstufe I und II gegeben, insbesondere, wie man Lernende dazu bringen kann, ihre Ideen f{\"u}r Algorithmen pr{\"a}zise zu analysieren und zu Papier zu bringen.}, language = {de} } @misc{LutzWestphal2004, author = {Lutz-Westphal, Brigitte}, title = {Wie komme ich optimal zum Ziel? Unterricht {\"u}ber k{\"u}rzeste-Wege-Algorithmen f{\"u}r Graphen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8102}, number = {04-35}, year = {2004}, abstract = {K{\"u}rzeste Wege tauchen fast {\"u}berall im Alltag auf. Daher eignet sich dieses Optimierungsproblem gut f{\"u}r den Unterricht. Modellierung und heuristische Vorgehensweisen werden ge{\"u}bt, um schließlich die klassischen k{\"u}rzesten Wege-Algorithmen selbst zu erfinden. In diesem Artikel werden die Inhalte vorgestellt und konkrete Hinweise zum Unterricht in der Schule gegeben.}, language = {de} } @misc{SokolovWolf2004, author = {Sokolov, Vladimir V. and Wolf, Thomas}, title = {Integrable quadratic Hamiltonians on so(4) and so(3,1)}, arxiv = {http://arxiv.org/abs/nlin.SI/0405066}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8085}, number = {04-33}, year = {2004}, abstract = {We investigate a special class of quadratic Hamiltonians on \$so(4)\$ and \$so(3,1)\$ and describe Hamiltonians that have additional polynomial integrals. One of the main results is a new integrable case with an integral of sixth degree.}, language = {en} } @misc{LutzWestphal2004, author = {Lutz-Westphal, Brigitte}, title = {Unterrichtsideen zu Algorithmen der kombinatorischen Optimierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8094}, number = {04-34}, year = {2004}, abstract = {Im Rahmen von Problemstellungen der kombinatorischen Optimierung k{\"o}nnen Sch{\"u}lerinnen und Sch{\"u}ler lernen, Algorithmen selber zu entwickeln. Gleichzeitig lernen sie dabei moderne Mathematik in ihren Anwendungen kennen und erleben die Mathematik als lebendige Wissenschaft.}, language = {de} } @misc{Harks2004, author = {Harks, Tobias}, title = {Utility Proportional Fair Bandwidth Allocation - An Optimization Oriented Approach}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8079}, number = {04-32}, year = {2004}, abstract = {In this paper, we present a novel approach to the congestion control and resource allocation problem of elastic and real-time traffic in telecommunication networks. With the concept of utility functions, where each source uses a utility function to evaluate the benefit from achieving a transmission rate, we interpret the resource allocation problem as a global optimization problem. The solution to this problem is characterized by a new fairness criterion, \e{utility proportional fairness}. We argue that it is an application level performance measure, i.e. the utility that should be shared fairly among users. As a result of our analysis, we obtain congestion control laws at links and sources that are globally stable and provide a utility proportional fair resource allocation in equilibrium. We show that a utility proportional fair resource allocation also ensures utility max-min fairness for all users sharing a single path in the network. As a special case of our framework, we incorporate utility max-min fairness for the entire network. To implement our approach, neither per-flow state at the routers nor explicit feedback beside ECN (Explicit Congestion Notification) from the routers to the end-systems is required.}, language = {en} } @misc{HodoroabaImhofKuberek2004, author = {Hodoroaba, Lavinia and Imhof, Andres and Kuberek, Monika}, title = {Das KOBV-Portal, elektronische Ressourcen in Berlin-Brandenburg: Nachweis, parallele Suche und weiterf{\"u}hrende Dienste}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8064}, number = {04-31}, year = {2004}, abstract = {\documentclass[12pt]{article} \usepackage{german} \parindent=0pt \begin{document} Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) hat in den Jahren 2001 bis 2003 im Rahmen des Entwicklungsprojektes ''KOBV-Informationsportal`` ein regionales Portal aufgebaut, in dem integrierte Informationsdienste fr die regionalen Bibliotheken zur Verf{\"u}gung gestellt werden. Das ''KOBV-Portal - Digitale Bibliothek Berlin-Brandenburg`` wurde im Dezember 2003 in Betrieb genommen. Das KOBV-Portal bietet in seiner ersten Ausbaustufe den Nachweis {\"u}ber die in den großen Bibliotheken lizenzierten Ressourcen und elektronischen Zeitschriften, zudem die nahtlose Navigation mittels des Reference-Linking-Werkzeuges SFX zu verschiedenen Diensten wie Fernleihe, Subito und freien Volltexten im Internet sowie zu frei zug{\"a}nglichen elektronischen Zeitschriften. Realisiert wurden ferner die Remote-Authentifizierung, mit der sich ein Nutzer, der online eine Fernleih-Bestellung aufgeben m{\"o}chte, {\"u}ber das Internet in seiner Heimatbibliothek authentifizieren kann. Des weiteren ist der Zugriff auf lizenzierte Best{\"a}nde im Campus einer Hochschule mittels IP-Checking m{\"o}glich. Als weiteren wesentlichen Bestandteil des KOBV-Portals hat die KOBV-Zentrale mit den Bibliotheken einen Workflow f{\"u}r ein Metadata-Sharing abgestimmt und f{\"u}r die Adaption und Normalisierung lokaler Metadaten aus lokalen Bibliothekssystemen und -Portalen den KOBV-Metadaten-Austausch-Parser (KMA-Parser) entwickelt. Damit Bibliotheken, deren Metadaten bislang lediglich in unstrukturierter Form vorliegen, strukturierte Metadaten anlegen, liefern und nachnutzen k{\"o}nnen, hat die KOBV-Zentrale das mit einer Web-Katalogisierungsschnittstelle ausgestattete ''Metadata-Tool`` entwickelt. Die f{\"u}r das Metadata-Sharing entwickelten Komponenten und Module sollen den Bibliotheken die Mehrfacherfassung ersparen und ihnen die M{\"o}glichkeit der wechselseitigen Nachnutzung der Metadaten er{\"o}ffnen. Der vorliegende Projekt-Abschlussbericht gibt einen {\"U}berblick {\"u}ber die w{\"a}hrend der Projektlaufzeit realisierten Dienste des KOBV-Portals. \end{document}}, language = {de} } @misc{Luegger2004, author = {L{\"u}gger, Joachim}, title = {Zusammenarbeit mit vascoda im Rahmen des Verteilten Dokumentenservers (VDS)}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8058}, number = {04-30}, year = {2004}, abstract = {Die in der Arbeitsgemeinschaft der Verbundsysteme zusammengeschlossenen deutschen Verbundsysteme kooperieren zur Realisierung eines die L{\"a}nder und Verbundregionen {\"u}bergreifenden offenen Netzwerkes einer offenen digitalen Bibliothek, dem Verteilten Dokumentenserver (VDS). Wesentliche Bestandteile des VDS sind die in den lokalen Bibliotheken und Verbundsystemen verteilten Dokumentenspeicher. Beim Aufbau des VDS verfolgen die deutschen Verbundsysteme f{\"u}r ihre digitalen Ressourcen, Zeitschriften und Dokumente, folgende Ziele [AGV03]: \begin{itemize} \item{Erhalt und dauerhafte Sicherung einmal erworbener Rechte} \item{Bessere Erschließung und Integration in das eigene Angebot} \item{Nahtlose Navigation in lokalen Zeitschriften- und Dokumentenservern und zwischen digitalen Artikeln und Zeitschriften, Dokumenten und Servern} \item{Dauerhafte Sicherung des Zugriffs und perspektivisch Langzeitverf{\"u}gbarkeit} \end{itemize} Die Verbundsysteme streben an, die Speicherung, Erschließung und das Angebot ihrer digitalen Materialien in einer nationalen Kooperation durchzuf{\"u}hren. Sie entwickeln und betreiben zu diesem Zweck Portal- und Querschnittstechnologien zur Integration ihrer dezentral gespeicherten digitalen Ressourcen mittels Internet-Technologien.}, language = {de} } @misc{BodlaenderKosterWolle2004, author = {Bodlaender, Hans L. and Koster, Arie M.C.A. and Wolle, Thomas}, title = {Contraction and Treewidth Lower Bounds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8042}, number = {04-29}, year = {2004}, abstract = {Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the minimum degree. The degeneracy is polynomial time computable. We introduce the notion of contraction degeneracy: the maximum over all minors of the minimum degree. We show that the contraction degeneracy problem is NP-complete, even for bipartite graphs, but for fixed \$k\$, it is polynomial time decidable if a given graph \$G\$ has contraction degeneracy at least \$k\$. Heuristics for computing the contraction degeneracy are proposed and evaluated. It is shown that these can lead in practice to considerable improvements of the lower bound for treewidth, but can perform arbitrarily bad on some examples. A study is also made for the combination of contraction with Lucena's lower bound based on Maximum Cardinality Search (Lucena, 2003). Finally, heuristics for the treewidth are proposed and! evaluated that combine contraction with a treewidth lower bound technique by Clautiaux et al (2003).}, language = {en} } @misc{HodoroabaImhof2004, author = {Hodoroaba, Lavinia and Imhof, Andres}, title = {Das KOBV-Metadaten-Schema im KOBV-Portal}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8038}, number = {04-28}, year = {2004}, abstract = {Das KOBV-Metadaten-Schema ist von der KOBV-Zentrale entwickelt worden, um Ressourcen im Sinn von Informationskollektionen wie Datenbanken oder Fachportale zu beschreiben. Es ist ein wichtiger Bestandteil des KOBV-Portals, das die in der Region verf"ugbaren Ressourcen nachweist. Das KOBV-Metadaten-Schema dient den Bibliotheken zur Handreichung, um dem KOBV-Portal die Ressourcen mit den standardisierten und individuellen Angaben zu melden, so dass die Ressourcebeschreibungen einem austauschbaren Format entsprechen. Auf diese Weise k"onnen Ressourcebeschreibungen von anderen Bibliotheken mitgenutzt werden und ein Metadata-Sharing in der Region Berlin-Brandenburg praktiziert werden, um in diesem Bereich doppelte Arbeiten zu sparen.}, language = {de} } @misc{HildebrandtPolthier2004, author = {Hildebrandt, Klaus and Polthier, Konrad}, title = {Anisotropic Filtering of Non-Linear Surface Features}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8003}, number = {04-25}, year = {2004}, abstract = {A new method for noise removal of arbitrary surfaces meshes is presented which focuses on the preservation and sharpening of non-linear geometric features such as curved surface regions and feature lines. Our method uses a prescribed mean curvature flow (PMC) for simplicial surfaces which is based on three new contributions: 1. the definition and efficient calculation of a discrete shape operator and principal curvature properties on simplicial surfaces that is fully consistent with the well-known discrete mean curvature formula, 2. an anisotropic discrete mean curvature vector that combines the advantages of the mean curvature normal with the special anisotropic behaviour along feature lines of a surface, and 3. an anisotropic prescribed mean curvature flow which converges to surfaces with an estimated mean curvature distribution and with preserved non-linear features. Additionally, the PMC flow prevents boundary shrinkage at constrained and free boundary segments.}, language = {en} } @misc{KaelbererPolthierReitebuchetal.2004, author = {K{\"a}lberer, Felix and Polthier, Konrad and Reitebuch, Ulrich and Wardetzky, Max}, title = {Compressing Triangle Meshes using Geometric Infomation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8016}, number = {04-26}, year = {2004}, abstract = {We introduce FreeLence, a lossless single-rate connectivity compression algorithm for triangle surface meshes. Based upon a geometry-driven traversal scheme we present two novel and simple concepts: free-valence connectivity encoding and entropy coding based on geometric context. Together these techniques yield significantly smaller rates for connectivity compression than current state of the art approaches - valence-based algorithms and Angle- Analyzer, with an average of \$36\\%\$ improvement over the former and an average of \$18\\%\$ over the latter on benchmark 3D models, combined with the ability to well adapt to the regularity of meshes. We also prove that our algorithm exhibits a smaller worst case entropy for a class of "'well-behaved"' triangle meshes than valence-driven connectivity encoding approaches.}, language = {en} } @misc{BraschossHansmannHesseetal.2004, author = {Braschoß, Katja and Hansmann, Sabine and Hesse, Thomas and Joosten-Wilke, Ulrike and Ristau, Ute and Rusch, Beate and Taylor, Viola}, title = {Indexierung von Online-Katalogen: Ein gemeinsames Konzept der ALEPH-Anwender in Berlin}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7998}, number = {04-24}, year = {2004}, abstract = {Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) verzichtet auf eine einheitliche zentrale Verbunddatenbank zugunsten einer dezentralen, verteilten Struktur. In dieser Architektur erh{\"a}lt die Art der Indexierung der angesprochenen Online-Kataloge eine besondere Bedeutung. So werden sowohl Bibliotheksmitarbeiter als auch Bibliotheksbenutzer immer wieder mit der Recherche in fremden Katalogen konfrontiert, in denen unterschiedliche Indexierungsverfahren realisiert sein k{\"o}nnen. Ein abgestimmtes Indexierungskonzept verfolgt zwei grunds{\"a}tzliche Ziele. Einerseits soll durch eine vereinheitlichte Indexierung die Qualit{\"a}t und Zuverl{\"a}ssigkeit der Rechercheergebnisse in der parallelen Suche in mehreren Katalogen {\"u}ber die KOBV-Suchmaschine erh{\"o}ht werden. Gleichzeitig soll durch eine vereinheitlichte Indexierung die Akzeptanz von Suchen in entfernten Katalogen prinzipiell gesteigert und damit die Bedingungen f{\"u}r die gegenseitige {\"U}bernahme von Titeldaten erleichtert werden. F{\"u}r die Indexierung muss zun{\"a}chst die Art und der Umfang der im OPAC aufzubauenden Indices festgelegt werden. Aus Sicht des Nutzers entspricht diese Definition den m{\"o}glichen Sucheinstiegen. Hat man dann entschieden, welche Indexterme aus welchen Feldern in die jeweiligen Indices einfließen sollen, muss bestimmt werden, nach welchen Regeln die Terme behandelt werden. Hier stellt sich insbesondere das Problem der Sonderzeichen wie Bindestriche, Apostrophe und Punkte oder Ziffern in Zeichenketten. Das vorliegende Konzept entstand in Zusammenarbeit der großen Universit{\"a}tsbibliotheken in Berlin (der Freien Universit{\"a}t, der Humboldt-Universit{\"a}t, der Technischen Universit{\"a}t, der Universit{\"a}t der K{\"u}nste) mit der KOBV-Verbundzentrale am ZIB.}, language = {de} } @misc{OrlowskiWessaely2004, author = {Orlowski, Sebastian and Wess{\"a}ly, Roland}, title = {The Effect of Hop Limits on Optimal Cost in Survivable Network Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7980}, number = {04-23}, year = {2004}, abstract = {We investigate the impact of hop-limited routing paths on the total cost of a telecommunication network. For different survivability settings (dedicated protection, link and path restoration), the optimal network cost without restrictions on the admissible path set is compared to the results obtained with two strategies to impose hop limits on routing paths. In a thorough computational study on optimal solutions for nine real-world based problem instances, we show that hop limits should be avoided if the technology allows it and network cost is a major planning issue. In this case, column generation should be employed to deal with all routing paths. If hop-limits are required, these should be defined for each demand individually and as large as possible.}, language = {en} } @misc{Steinbach2004, author = {Steinbach, Marc}, title = {Robust Process Control by Dynamic Stochastic Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7959}, number = {04-20}, year = {2004}, abstract = {Unnecessarily conservative behavior of standard process control techniques can be avoided by stochastic programming models when the distribution of random disturbances is known. In an earlier study we have investigated such an approach for tank level constraints of a distillation process. Here we address techniques that have accelerated the numerical solution of the large and expensive stochastic programs by a factor of six, and then present a refined optimization model for the same application.}, language = {en} } @misc{EhrhardtSteinbach2004, author = {Ehrhardt, Klaus and Steinbach, Marc}, title = {KKT Systems in Operative Planning for Gas Distribution Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7962}, number = {04-21}, year = {2004}, abstract = {Operative planning in gas networks with prescribed binary decisions yields large scale nonlinear programs defined on graphs. We study the structure of the KKT systems arising in interior methods and present a customized direct solution algorithm. Computational results indicate that the algorithm is suitable for optimization in small and medium-sized gas networks.}, language = {en} } @misc{DraheimNeunSuliman2004, author = {Draheim, Dirk and Neun, Winfried and Suliman, Dima}, title = {Searching and Classifying Differential Equations on the Web}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7975}, number = {04-22}, year = {2004}, abstract = {In this paper we describe the semantic analysis of differential equations given in the ubiquitous semi-structured formats MathML and OpenMath. The analysis is integrated in a deployed Web indexing framework. Starting from basic classifications for differential equations the proposed system architecture is amenable to extensions for further reconstruction of mathematical content on the Web. The syntactic analysis of mathematical formulae given in the considered formats must overcome ambiguities that stem from the fact that formula particles may have different encodings, which are in principle completely arbitrary. However, it turns out that the syntactic analysis can be done straightforward given some natural heuristic assumptions.}, language = {en} } @misc{Lukac2004, author = {Lukac, Sascha}, title = {Holes, Antiholes and Maximal Cliques in a Railway Model for a Single Track}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7939}, number = {04-18}, year = {2004}, abstract = {We present a graph theoretical model for scheduling trains on a single unidirectional track between two stations. The set of departures of all possible train types at all possible (discrete) points of time is turned into an undirected graph \$\Gneu\$ by joining two nodes if the corresponding departures are in conflict. This graph \$\Gneu\$ has no odd antiholes and no \$k\$-holes for any integer \$k\geq 5\$. In particular, any finite, node induced subgraph of \$\Gneu\$ is perfect. For any integer \$r\geq 2\$ we construct minimal headways for \$r\$ train types so that the resulting graph \$\Gneu\$ has \$2r\$-antiholes and \$4\$-holes at the same time. Hence, \$\Gneu\$ is neither a chordal graph nor the complement of a chordal graph, in general. At the end we analyse the maximal cliques in \$G\$.}, language = {en} } @misc{Achterberg2004, author = {Achterberg, Tobias}, title = {SCIP - a framework to integrate Constraint and Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7947}, number = {04-19}, year = {2004}, abstract = {Constraint Programs and Mixed Integer Programs are closely related optimization problems originating from different scientific areas. Today's state-of-the-art algorithms of both fields have several strategies in common, in particular the branch-and-bound process to recursively divide the problem into smaller sub problems. On the other hand, the main techniques to process each sub problem are different, and it was observed that they have complementary strenghts. We propose a programming framework {\sffamily SCIP} that integrates techniques from both fields in order to exploit the strenghts of both, Constraint Programming and Mixed Integer Programming. In contrast to other proposals of recent years to combine both fields, {\sffamily SCIP} does not focus on easy implementation and rapid prototyping, but is tailored towards expert users in need of full, in-depth control and high performance.}, language = {en} } @misc{HillerKrumkeRambau2004, author = {Hiller, Benjamin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7928}, number = {04-17}, year = {2004}, abstract = {Under high load, the automated dispatching of service vehicles for the German Automobile Association (ADAC) must reoptimize a dispatch for 100--150 vehicles and 400 requests in about ten seconds to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within ten seconds. One way-out are simplified reoptimization models. These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new model ZIBDIP{\footnotesize dummy} can keep up with ZIBDIP.}, language = {en} } @misc{OPUS4-978, title = {Jahresbericht 2003}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9781}, number = {2003}, year = {2004}, language = {de} } @misc{EisenblaetterGeerdesKochetal.2004, author = {Eisenbl{\"a}tter, Andreas and Geerdes, Hans-Florian and Koch, Thorsten and Martin, Alexander and Wess{\"a}ly, Roland}, title = {UMTS Radio Network Evaluation and Optimization beyond Snapshots}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7903}, number = {04-15}, year = {2004}, abstract = {This paper is concerned with UMTS radio network design. Our task is to reconfigure antennas and the related cells as to improve network quality. In contrast to second generation GSM networks, \emph{interference} plays a paramount role when designing third generation radio networks. A known compact formulation for assessing the interference characteristics of a radio network as coupling relations between cells based on user snapshots is generalized to statistical average load. This enables us to overcome the notorious difficulties of snapshot-based network optimization approaches. We recall a mixed-integer programming model for the network design problem that is based on user snapshots and contrast it with a new network design model based on the average coupling formulation. Exemplarily focusing on the important problem of optimizing antenna tilts, we give computational results for a fast local search algorithm and the application of a MIP solver to both models. These results demonstrate that our new average-based approaches outperform state-of-the-art snapshot models for UMTS radio network optimization.}, language = {en} } @misc{AchterbergKochMartin2004, author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander}, title = {Branching rules revisited}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7886}, number = {04-13}, year = {2004}, abstract = {Mixed integer programs are commonly solved with linear programming based branch-and-bound algorithms. The success of the algorithm strongly depends on the strategy used to select the variable to branch on. We present a new generalization called {\sl reliability branching} of today's state-of-the-art {\sl strong branching} and {\sl pseudocost branching} strategies for linear programming based branch-and-bound algorithms. After reviewing commonly used branching strategies and performing extensive computational studies we compare different parameter settings and show the superiority of our proposed newstrategy.}, language = {en} } @misc{BorndoerferLoebelWeider2004, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7898}, number = {04-14}, year = {2004}, abstract = {This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction.}, language = {en} } @misc{Lutz2004, author = {Lutz, Frank H.}, title = {Triangulated Manifolds with Few Vertices: Centrally Symmetric Spheres and Products of Spheres}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7863}, number = {04-11}, year = {2004}, abstract = {The aim of this paper is to give a survey of the known results concerning centrally symmetric polytopes, spheres, and manifolds. We further enumerate nearly neighborly centrally symmetric spheres and centrally symmetric products of spheres with dihedral or cyclic symmetry on few vertices, and we present an infinite series of vertex-transitive nearly neighborly centrally symmetric 3-spheres.}, language = {en} } @misc{LameckerLangeSeebass2004, author = {Lamecker, Hans and Lange, Thomas and Seebass, Martin}, title = {Segmentation of the Liver using a 3D Statistical Shape Model}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7847}, number = {04-09}, year = {2004}, abstract = {This paper presents an automatic approach for segmentation of the liver from computer tomography (CT) images based on a 3D statistical shape model. Segmentation of the liver is an important prerequisite in liver surgery planning. One of the major challenges in building a 3D shape model from a training set of segmented instances of an object is the determination of the correspondence between different surfaces. We propose to use a geometric approach that is based on minimizing the distortion of the correspondence mapping between two different surfaces. For the adaption of the shape model to the image data a profile model based on the grey value appearance of the liver and its surrounding tissues in contrast enhanced CT data was developed. The robustness of this method results from a previous nonlinear diffusion filtering of the image data. Special focus is turned to the quantitative evaluation of the segmentation process. Several different error measures are discussed and implemented in a study involving more than 30 livers.}, language = {en} } @misc{JoswigLutz2004, author = {Joswig, Michael and Lutz, Frank H.}, title = {One-Point Suspensions and Wreath Products of Polytopes and Spheres}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7836}, number = {04-08}, year = {2004}, abstract = {It is known that the suspension of a simplicial complex can be realized with only one additional point. Suitable iterations of this construction generate highly symmetric simplicial complexes with a various interesting combinatorial and topological properties. In particular, infinitely many non-PL spheres as well as contactible simplicial complexes with a vertex-transitive group of automorphisms cab be contained in this way.}, language = {en} } @misc{Baum2004, author = {Baum, Daniel}, title = {Finding All Maximal Cliques of a Family of Induced Subgraphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7758}, number = {03-53}, year = {2004}, abstract = {Many real world problems can be mapped onto graphs and solved with well-established efficient algorithms studied in graph theory. One such problem is to find large sets of points satisfying some mutual relationship. This problem can be transformed to the problem of finding all cliques of an undirected graph by mapping each point onto a vertex of the graph and connecting any two vertices by an edge whose corresponding points satisfy our desired relationship. Clique detection has been widely studied and there exist efficient algorithms. In this paper we study a related problem, where all points have a set of binary attributes, each of which is either 0 or 1. This is only a small limitation, since all discrete properties can be mapped onto binary attributes. In our case, we want to find large sets of points not only satisfying some mutual relationship; but, in addition, all points of a set also need to have at least one common attribute with value 1. The problem we described can be mapped onto a set of induced subgraphs, where each subgraph represents a single attribute. For attribute \$i\$, its associated subgraph contains those vertices corresponding to the points with attribute \$i\$ set to 1. We introduce the notion of a maximal clique of a family, \$\mathcal{G}\$, of induced subgraphs of an undirected graph, and show that determining all maximal cliques of \$\mathcal{G}\$ solves our problem. Furthermore, we present an efficient algorithm to compute all maximal cliques of \$\mathcal{G}\$. The algorithm we propose is an extension of the widely used Bron-Kerbosch algorithm.}, language = {en} } @misc{Wagler2004, author = {Wagler, Annegret}, title = {The Normal Graph Conjecture is true for Circulants}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7813}, number = {04-06}, year = {2004}, abstract = {Normal graphs are defined in terms of cross-intersecting set families: a graph is normal if it admits a clique cover \$\cal Q\$ and a stable set cover \$\cal S\$ s.t.~every clique in \$\cal Q\$ intersects every stable set in \$\cal S\$. Normal graphs can be considered as closure of perfect graphs by means of co-normal products (K{\"o}rner 1973) and graph entropy (Czisz\'ar et al. 1990). Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs (Strong Perfect Graph Theorem, Chudnovsky et al. 2002). K{\"o}rner and de Simone observed that \$C_5\$, \$C_7\$, and \$\overline C_7\$ are minimal not normal and conjectured, as generalization of the Strong Perfect Graph Theorem, that every \$C_5\$, \$C_7\$, \$\overline C_7\$- free graph is normal (Normal Graph Conjecture, K{\"o}rner and de Simone 1999). We prove this conjecture for a first class of graphs that generalize both odd holes and odd antiholes, the circulants, by characterizing all the normal circulants.}, language = {en} } @misc{EisenblaetterGeerdesKochetal.2004, author = {Eisenbl{\"a}tter, Andreas and Geerdes, Hans-Florian and Koch, Thorsten and T{\"u}rke, Ulrich}, title = {MOMENTUM Data Scenarios for Radio Network Planning and Simulation (Extended Abstract)}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7829}, number = {04-07}, year = {2004}, abstract = {We present publicly available data sets related to research on wireless networks. The scenarios contain a wide range of data and are detailed in all aspects. To our knowledge, this is the most realistic, comprehensive, and detailed \emph{public} data collection on mobile networking. We indicate example uses of this data collection in applications related tu UMTS.}, language = {en} } @misc{HelmesRoehl2004, author = {Helmes, Kurt and R{\"o}hl, Stefan}, title = {A Geometrical Characterization of the Multidimensional Hausdorff and Dale Polytopes with Applications to Exit Time Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7807}, number = {04-05}, year = {2004}, abstract = {We present formulae for the corner points of the multidimensional Hausdorff and Dale Polytopes and show how these results can be used to improve linear programming models for computing e.\,g.\ moments of exit distribution of diffusion processes. Specifically, we compute the mean exit time of twodimensional Brownian motion from the unit square and the unit triangle, as well as higher moments of the exit time of time space Brownian motion from a triangle.}, language = {en} } @misc{BleyKochWessaely2004, author = {Bley, Andreas and Koch, Thorsten and Wess{\"a}ly, Roland}, title = {Large-scale hierarchical networks: How to compute an optimal architecture?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7799}, number = {04-04}, year = {2004}, abstract = {In this article, we present a mathematical model and an algorithm to support one of the central strategic planning decisions of network operators: How to organize a large number of locations into a hierarchical network? We propose a solution approach that is based on mixed-integer programming and Lagrangian relaxation techniques. As major advantage, our approach provides not only solutions but also worst-case quality guarantees. Real-world scenarios with more than 750 locations have been solved within 30 minutes to less than 1\\% off optimality.}, language = {en} } @misc{Luegger2004, author = {L{\"u}gger, Joachim}, title = {Vorhaben: Offene Navigation und Suchmaschinen in Verb{\"u}nden, Konsortien und den Wissenschaften; Schlussbericht zumTeilprojekt des BMBF-Vorhabens: Kompetenznetzwerk NeueDienste, Standardisierung, Metadaten.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7737}, number = {03-51}, year = {2004}, abstract = {Die harmonische Integration der Navigation und Suche in lizenzierten Journalen und gleichzeitig in freien digitalen Dokumenten unter einer einheitlichen konsistenten Nutzeroberflache ist eines der ungel{\"o}sten F\&E-Probleme der Fachinformation. Hierf{\"u}r sollen Elemente des Invisible Web und des Visible Web unter Ber{\"u}cksichtigung offener Standards nahtlos \#I miteinander verbunden werden. Dem Projekt liegt ein Modell mit Internet-Index, Metasuche und Open Linking {\"u}ber verteilten heterogenen Speichern \#I zu Grunde: Verschiedenste Server, digitale Referenzen in Artikeln und Dokumenten, Links in Datenbanken und auf Bestelldienste sollen unter Ber{\"u}cksichtigung von Standort-, Studien- und Lernbedingungen kooperativ miteinander vernetzt werden. Die Leistungsf{\"a}higkeit des Modells soll in Pilotimplementierungen getestet und f{\"u}r eine breite Anwendung vorbereitet werden. Auf dieser Basis soll das Vorhaben Verteilter Zeitschriftenserver der AG der Verbundsysteme in eigenen Teilprojekten kooperativ initiiert werden, das jetzt in das Vorhaben Verteilter Dokumentenserver von vascoda integriert ist.}, language = {de} } @misc{NowakGrahSchreier2004, author = {Nowak, Ulrich and Grah, Aleksander and Schreier, Manfred}, title = {Parameter Estimation and Accuracy Matching Strategies for 2-D Reactor Models}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7749}, number = {03-52}, year = {2004}, abstract = {The mathematical modeling of a special modular catalytic reactor kit leads to a system of partial differential equation in two space dimensions. As customary, this model contains unconfident physical parameters, which may be adapted to fit experimental data. To solve this nonlinear least squares problem we apply a damped Gauss-Newton method. A method of lines approach is used to evaluate the associated model equations. By an a priori spatial discretization a large DAE system is derived and integrated with an adaptive, linearly-implicit extrapolation method. For sensitivity evaluation we apply an internal numerical differentiation technique, which reuses linear algebra information from the model integration. In order not to interfere the control of the Gauss-Newton iteration these computations are done usually very accurately and, therefore, very costly. To overcome this difficulty, we discuss several accuracy adaptation strategies, e.g., a master-slave mode. Finally, we present some numerical experiments.}, language = {en} } @misc{KroellerWessaely2003, author = {Kr{\"o}ller, Alexander and Wess{\"a}ly, Roland}, title = {Integrated Optimization of Hardware Configuration and Capacity. Dimensioning in SDH and opaque WDM networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7714}, number = {03-49}, year = {2003}, abstract = {We suggest a new model for the design of telecommunication networks which integrates decisions about the topology, configuration of the switching hardware, link dimensioning, and protected routing of communication demands. Applying the branch-and-cut-algorithm implemented in our network planning and optimization tool DISCNET, we demonstrate that real-world based network planning instances of such an enhanced model can be solved.}, language = {en} } @misc{Koch2003, author = {Koch, Thorsten}, title = {Verteilter Dokumenten-Speicher, Erfahrungen mit den Kluwer-Daten des Friedrich-Althoff-Konsortiums}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7726}, number = {03-50}, year = {2003}, abstract = {Dieser Bericht beschreibt die Erfahrungen und Schlussfolgerungen,die im Rahmen der VDS-Vorstudie bei der Speicherung der vom Friedrich-Althoff-Konsortium lizenzierten Zeitschriften des Kluwer-Verlages gewonnen wurden.}, language = {de} } @misc{Weber2003, author = {Weber, Marcus}, title = {Clustering by using a simplex structure}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7782}, number = {04-03}, year = {2003}, abstract = {In this paper we interpret clustering as a mapping of data into a simplex. If the data itself has simplicial struture this mapping becomes linear. Spectral analysis is an often used tool for clustering data. We will show that corresponding singular vectors or eigenvectors comprise simplicial structure. Therefore they lead to a cluster algorithm, which consists of a simple linear mapping. An example for this kind of algorithms is the Perron cluster analysis (PCCA). We have applied it in practice to identify metastable sets of molecular dynamical systems. In contrast to other algorithms, this kind of approach provides an a priori criterion to determine the number of clusters. In this paper we extend the ideas to more general problems like clustering of bipartite graphs.}, language = {en} } @misc{MayEisenhardtSchmidtEhrenbergetal.2003, author = {May, Andreas and Eisenhardt, Steffen and Schmidt-Ehrenberg, Johannes and Cordes, Frank}, title = {Rigid body docking for Virtual Screening}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7690}, number = {03-47}, year = {2003}, abstract = {A recently developed algorithm allows Rigid Body Docking of ligands to proteins, regardless of the accessibility and location of the binding site. The Docking procedure is divided into three subsequent optimization phases, two of which utilize rigid body dynamics. The last one is applied with the ligand already positioned inside the binding pocket and accounts for full flexibility. Initially, a combination of geometrical and force-field based methods is used as a Coarse Docking strategy, considering only Lennard-Jones interactions between the target and pharmaceutically relevant atoms or functional groups. The protein is subjected to a Hot Spot Analysis, which reveals points of high affinity in the protein environment towards these groups. The hot spots are distributed into different subsets according to their group affiliation. The ligand is described as a complementary point set, consisting of the same subsets. Both sets are matched in \$\mathrm{I\!R}^{3}\$, by superimposing members of the same subsets. In the first instance, steric inhibition is nearly neglected, preventing the system's trajectory from trapping in local minima and thus from finding false positive solutions. Hence the exact location of the binding site can be determined fast and reliably without any additional information. Subsequently, errors resulting from approximations are minimized via finetuning, this time considering both Lennard-Jones and Coulomb forces. Finally, the potential energy of the whole complex is minimized. In a first evaluation, results are rated by a reduced scoring function considering only noncovalent interaction energies. Exemplary Screening results will be given for specific ligands.}, language = {en} } @misc{BoitCordes2003, author = {Boit, Alice and Cordes, Frank}, title = {RNA 3D-Modeling}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7708}, number = {03-48}, year = {2003}, abstract = {This article presents a new computational approach to the three-dimensional (3D) modeling of ribonucleic acid (RNA) sequences with unknown spatial structure. The main concept is a mapping of the query sequence onto the 3D structures of a suitable template RNA molecule. This technique called \textit{threading} has originally been developed for the modeling of protein 3D structures. The application to RNA systems bridges the information gap between the growing mass of RNA sequence data and the relatively limited number of available 3D structures. The new RNA threading method is demonstrated on a tRNA model system because sufficient representative 3D structures have experimentally been elucidated and deposited in the public databases. Nevertheless, the method is in principle transferable on all other RNA species. Algorithms are developed that decompose these template structures into their secondary structure elements and gather this information in a specific template database. The best template is chosen with public alignment and secondary structure prediction tools which are integrated in the RNA modeling module. The structural information gathered from the template and the best alignment is combined to establish a comprehensive 3D model of the query sequence. A range of complete tRNA structures has successfully been modeled with the RNA threading method. The prototype module visualizes the models and provides convenient access to the proposed 3D structures. Therefore, the method could give new insight into a variety of RNA systems which in the recent years have become increasingly important as potential new pharmaceutical agents.}, language = {en} } @misc{DeuflhardChairs2003, author = {Deuflhard, Peter and (Chairs), Hyung Yong Ra}, title = {Korean-German Bilateral Symposium on Scientific Computing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7778}, number = {04-02}, year = {2003}, abstract = {Collection of abstracts of the Korean-German Bilateral Symposium on Scientific Computing, Berlin January 15/16, 2004}, language = {en} } @misc{EhrhardtSteinbach2003, author = {Ehrhardt, Klaus and Steinbach, Marc}, title = {Nonlinear Optimization in Gas Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7687}, number = {03-46}, year = {2003}, abstract = {The operative planning problem in natural gas distribution networks is addressed. An optimization model focusing on the governing PDE and other nonlinear aspects is presented together with a suitable discretization for transient optimization in large networks by SQP methods. Computational results for a range of related dynamic test problems demonstrate the viability of the approach.}, language = {en} } @misc{KosterZymolka2003, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Minimum Converter Wavelength Assignment in All-Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7673}, number = {03-45}, year = {2003}, abstract = {Finding conflict-free wavelength assignments with a minimum number of required conversions for a routing of the lightpaths is one of the important tasks within the design of all-optical networks. We consider this problem in multi-fiber networks with different types of WDM systems. We give a detailed description of the problem and derive its theoretical complexity. For practical application, we propose several sequential algorithms to compute appropriate wavelength assignments. We also perform computational experiments to evaluate their performance. For the iterative algorithms, we identify characteristic patterns of progression. Two of these algorithms qualify for application in practice.}, language = {en} } @misc{ZschiedrichKloseSchaedleetal.2003, author = {Zschiedrich, Lin and Klose, Roland and Sch{\"a}dle, Achim and Schmidt, Frank}, title = {A new Finite Element realization of the Perfectly Matched Layer Method for Helmholtz scattering problems on polygonal domains in 2D}, doi = {10.1016/j.cam.2005.03.047}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7662}, number = {03-44}, year = {2003}, abstract = {In this paper we propose a new finite element realization of the Perfectly Matched Layer method (PML-method). Our approach allows to deal with arbitrary shaped polygonal domains and with certain types of inhomogeneous exterior domains. Among the covered inhomogeneities are open waveguide structures playing an essential role in integrated optics. We give a detailed insight to implementation aspects. Numerical examples show exponential convergence behavior to the exact solution with the thickness of the PML sponge layer.}, language = {en} } @misc{GeerdesKarl2003, author = {Geerdes, Hans-Florian and Karl, Holger}, title = {The Potential of Relaying in Cellular Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7641}, number = {03-42}, year = {2003}, abstract = {Relaying is a protocol extension for cellular wireless computer networks; in order to utilize radio resources more efficiently, several hops are allowed within one cell. This paper investigates the principle potential of relaying by casting transmission scheduling as a mathematical optimization problem, namely, a linear program. We analyze the throughput gains showing that, irrespective of the concrete scheduling algorithm, performance gains of up to 30\\% on average for concrete example networks are achievable.}, language = {en} } @misc{Geerdes2003, author = {Geerdes, Hans-Florian}, title = {Assessing Capacity Improvements by Relaying in Cellular Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7651}, number = {03-43}, year = {2003}, abstract = {Relaying -- allowing multiple wireless hops -- is a protocol extension for cellular networks conceived to improve data throughput. Its benefits have only been quantified for small example networks. For assessing its general potential, we define a complex resource allocation\slash{}scheduling problem. Several mathematical models are presented for this problem; while a time-expanded MIP approach turns out intractable, a sophisticated column generation scheme leads to good computational results. We thereby show that for selected cases relaying can increase data throughput by 30\\% on the average.}, language = {en} } @misc{EisenblaetterFuegenschuhGeerdesetal.2003, author = {Eisenbl{\"a}tter, Andreas and F{\"u}genschuh, Armin and Geerdes, Hans-Florian and Junglas, Daniel and Koch, Thorsten and Martin, Alexander}, title = {Optimization Methods for UMTS Radio Network Planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7637}, number = {03-41}, year = {2003}, abstract = {The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimization model for this problem that is based on comprehensive planning data of the EU project MOMENTUM. We present heuristic mathematical methods for this realistic model, including computational results.}, language = {en} } @misc{HegeHutanuKaehleretal.2003, author = {Hege, Hans-Christian and Hutanu, Andrei and K{\"a}hler, Ralf and Merzky, Andr{\´e} and Radke, Thomas and Seidel, Edward and Ullmer, Brygg}, title = {Progressive Retrieval and Hierarchical Visualization of Large Remote Data}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7623}, number = {03-40}, year = {2003}, abstract = {\noindent The size of data sets produced on remote supercomputer facilities frequently exceeds the processing capabilities of local visualization workstations. This phenomenon increasingly limits scientists when analyzing results of large-scale scientific simulations. That problem gets even more prominent in scientific collaborations, spanning large virtual organizations, working on common shared sets of data distributed in Grid environments. In the visualization community, this problem is addressed by distributing the visualization pipeline. In particular, early stages of the pipeline are executed on resources closer to the initial (remote) locations of the data sets. \noindent This paper presents an efficient technique for placing the first two stages of the visualization pipeline (data access and data filter) onto remote resources. This is realized by exploiting the ``extended retrieve'' feature of GridFTP for flexible, high performance access to very large HDF5 files. We reduce the number of network transactions for filtering operations by utilizing a server side data processing plugin, and hence reduce latency overhead compared to GridFTP partial file access. The paper further describes the application of hierarchical rendering techniques on remote uniform data sets, which make use of the remote data filtering stage.}, language = {en} } @misc{BurgerKloseSchaedleetal.2003, author = {Burger, Sven and Klose, Roland and Sch{\"a}dle, Achim and Zschiedrich, Lin}, title = {HelmPole - A finite element solver for scattering problems on unbounded domains: Implementation based on PML}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7609}, number = {03-38}, year = {2003}, abstract = {The solution of scattering problems described by the Helmholtz equation on unbounded domains is of importance for a wide variety of applications, for example in electromagnetics and acoustics. An implementation of a solver for scattering problems based on the programming language Matlab is introduced. The solver relies on the finite-element-method and on the perfectly-matched-layer-method, which allows for the simulation of scattering problems on complex geometries surrounded by inhomogeneous exterior domains. This report gives a number of detailed examples and can be understood as a user manual to the freely accessible code of the solver HelmPole.}, language = {en} }