@misc{HorenkoWeiser2002, author = {Horenko, Illia and Weiser, Martin}, title = {Adaptive Integration of Multidimensional Molecular Dynamics with Quantum Initial Conditions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6967}, number = {02-29}, year = {2002}, abstract = {The paper presents a particle method framework for resolving molecular dynamics. Error estimators for both the temporal and spatial discretization are advocated and facilitate a fully adaptive propagation. For time integration, the implicit trapezoidal rule is employed, where an explicit predictor enables large time steps. The framework is developed and exemplified in the context of the classical Liouville equation, where Gaussian phase-space packets are used as particles. Simplified variants are discussed shortly, which should prove to be easily implementable in common molecular dynamics codes. A concept is illustrated by numerical examples for one-dimensional dynamics in double well potential.}, language = {en} } @misc{BrandtBrandt2002, author = {Brandt, Andreas and Brandt, Manfred}, title = {On the Two-Class M/M/1 System under Preemptive Resume and Impatience of the Prioritized Customers}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6953}, number = {02-28}, year = {2002}, abstract = {The paper deals with the two-class priority M/M/1 system, where the prioritized class-1 customers are served under FCFS preemptive resume discipline and may become impatient during their waiting for service with generally distributed maximal waiting times but finite expectation. The class-2 customers have no impatience. The required mean service times may depend on the class of the customer. As the dynamics of class-1 customers are related to the well analyzed M/M/1+GI system, our aim is to derive characteristics for class-2 customers and for the whole system. The solution of the balance equations for the partial probability generating functions of the detailed system state process is given in terms of the weak solution of a family of boundary value problems for ordinary differential equations. By means of this solution formulae for the joint occupancy distribution and for the sojourn and waiting times of class-2 customers are derived generalizing results recently obtained by Choi et al. in case of deterministic maximal waiting times. For deterministic maximal waiting times partially new explicit formulae are given.}, language = {en} } @misc{Rusch2002, author = {Rusch, Beate}, title = {Towards an Internet Based Information Portal for Berlin and Brandenburg}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6949}, number = {02-27}, year = {2002}, abstract = {The Cooperative Library Network Berlin-Brandenburg (KOBV) has set the development of a genuine library information portal for the two German Lander (federal states) Berlin and Brandenburg as its main task for the next years. This joined effort is driven by the vision of an user friendly Internet information portal which is accessible anytime, from anywhere in the world. The idea of a regional information portal can be understood as the logically consistent development of the basic ideas of the KOBV. Starting in 1997, the consortia has set the implementation of a virtual OPAC instead of a physical union catalogue as its goal. The result was the KOBV-Search Engine which already has some qualities of a portal itself. The paper begins with initial remarks about the German library world, which do form the background for the project and its initiator - the KOBV consortia. After this preliminary part, different types of portals are introduced. The basic features of the KOBV-Search Engine as one of the cornerstones of the future portal are discussed in the following. The information portal will be much richer in content and services for the end-user. Two aspects are focused on in more detail: the presentation of resources, which becomes a compelling requirement because of the broader range of content and the personalization of services, as one important feature to suit user's individual needs.}, language = {en} } @misc{Groetschel2002, author = {Gr{\"o}tschel, Martin}, title = {P=NP?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6939}, number = {02-26}, year = {2002}, abstract = {Hinter der f{\"u}r den Uneingeweihten etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexit{\"a}tstheorie. Dieser Artikel erl{\"a}utert einige Aspekte der Theorie und erkl{\"a}rt informell, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grunds{\"a}tzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es f{\"u}r viele Probleme unseres Alltags keine effizienten L{\"o}sungsmethoden gibt?}, language = {de} } @phdthesis{Krumke2002, author = {Krumke, Sven}, title = {Online Optimization: Competitive Analysis and Beyond}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6925}, number = {02-25}, year = {2002}, abstract = {Traditional optimization techniques assume, in general, knowledge of all data of a problem instance. There are many cases in practice, however, where decisions have to be made before complete information about the data is available. In fact, it may be necessary to produce a part of the problem solution as soon as a new piece of information becomes known. This is called an \emph{online situation}, and an algorithm is termed \emph{online}, if it makes a decision (computes a partial solution) whenever a new piece of data requests an action. \emph{Competitive analysis} has become a standard yardstick to measure the quality of online algorithms. One compares the solution produced by an online algorithm to that of an optimal (clairvoyant) offline algorithm. An online algorithm is called \$c\$-competitive if on every input the solution it produces has cost'' at most \$c\$~times that of the optimal offline algorithm. This situation can be imagined as a game between an online player and a malicious adversary. Although competitive analysis is a worst-case analysis and henceforth pessimistic, it often allows important insights into the problem structure. One can obtain an idea about what kind of strategies are promising for real-world systems and why. On the other hand there are also cases where the offline adversary is simply too powerful and allows only trivial competitiveness results. This phenomenon is called hitting the triviality barrier''. We investigate several online problems by means of competitive analysis. We also introduce new concepts to overcome the weaknesses of the standard approach and to go beyond the triviality barrier.}, language = {en} } @misc{OPUS4-976, title = {Jahresbericht 2001}, issn = {0934-5892}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9764}, number = {2001}, year = {2002}, language = {de} } @misc{KrumkePoensgen2002, author = {Krumke, Sven and Poensgen, Diana}, title = {Online Call Admission in Optical Networks with Larger Wavelength Demands}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6890}, number = {02-22}, year = {2002}, abstract = {In the problem of \emph{Online Call Admission in Optical Networks}, briefly called \textsc{oca}, we are given a graph \$G=(V,E)\$ together with a set of wavelengths~\$W\$ and a finite sequence \$\sigma=r_1,r_2,\dots\$ of calls which arrive in an online fashion. Each call~\$r_j\$ specifies a pair of nodes to be connected and an integral demand indicating the number of required lightpaths. A lightpath is a path in~\$G\$ together with a wavelength~\$\lambda \in W\$. Upon arrival of a call, an online algorithm must decide immediately and irrevocably whether to accept or to reject the call without any knowledge of calls which appear later in the sequence. If the call is accepted, the algorithm must provide the requested number of lightpaths to connect the specified nodes. The essential restriction is the wavelength conflict constraint: each wavelength is available only once per edge, which implies that two lightpaths sharing an edge must have different wavelengths. Each accepted call contributes a benefit equal to its demand to the overall profit. The objective in \textsc{oca} is to maximize the overall profit. Competitive algorithms for \textsc{oca} have been known for the special case where every call requests just a single lightpath. In this paper we present the first competitive online algorithms for the general case of larger demands.}, language = {en} } @misc{KrumkeLipmannPaepeetal.2002, author = {Krumke, Sven and Lipmann, Maarten and Paepe, Willem de and Poensgen, Diana and Rambau, J{\"o}rg and Stougie, Leen and Woeginger, Gerhard}, title = {How to Cut a Cake Almost Fairly}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6905}, number = {02-23}, year = {2002}, abstract = {In the cake cutting problem, \$n\ge2\$ players want to cut a cake into \$n\$ pieces so that every player gets a ``fair'' share of the cake by his own measure. We describe a protocol with \$n-1\$~cuts in which each player can enforce to get a share of at least~\$1/(2n-2)\$. Moreover we show that no protocol with \$n-1\$~cuts can guarantee a better fraction.}, language = {en} } @misc{KrumkeMarathePoensgenetal.2002, author = {Krumke, Sven and Marathe, Madhav and Poensgen, Diana and Ravi, Sekharipuram S. and Wirth, Hans-Christoph}, title = {Budgeted Maximal Graph Coverage}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6918}, number = {02-24}, year = {2002}, abstract = {An instance of the \emph{maximum coverage} problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total cost of at most that of a given budget maximizing the weight of the covered elements. We formulate the problem on graphs: In this situation the set of ground elements is specified by the nodes of a graph, while the family of covering sets is restricted to connected subgraphs. We show that on general graphs the problem is polynomial time solvable if restricted to sets of size at most~\$2\$, but becomes NP-hard if sets of size~\$3\$ are permitted. On trees, we prove polynomial time solvability if each node appears in a fixed number of sets. In contrast, if vertices are allowed to appear an unbounded number of times, the problem is NP-hard even on stars. We finally give polynomial time algorithms for special cases where the subgraphs form paths and the host graph is a line, a cycle or a star.}, language = {en} } @misc{LitscheOtto2002, author = {Litsche, Stefan and Otto, Dagmar}, title = {Evaluation ausgew{\"a}hlter Portalsysteme}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6882}, number = {02-21}, year = {2002}, abstract = {Die Bibliotheken des KOBV haben im Jahr 2001 die Entwicklung der KOBV-Suchmaschine zu einem gemeinsamen Informationsportal Berlin-Brandenburg und den Aufbau lokaler Bibliotheksportale als Hauptentwicklungsziele des KOBV definiert. Diese Informationsportale sollen mit Standardsoftware realisiert werden. Um die Auswahl eines Systems zu unterst{\"u}tzen, wurde in der Zentrale des KOBV ausgew{\"a}hlte Systeme untersucht. In der Arbeit werden zahlreiche Kriterien vorgestellt, auf Grund derer die betreffenden Systeme beurteilt werden. Die Kriterien umfassen sowohl Aspekte aus der Sicht der Benutzer als auch Kriterien aus der Sicht der Betreiber eines solchen Systems. Wesentliche Funktionen und die Realisierung von verschiedenen Merkmalen werden im Bericht ausf{\"u}hrlich beschrieben. Daneben liefert eine Tabelle mit allen betrachteten Kriterien eine {\"U}bersicht {\"u}ber vorhandene Merkmale und der Art der Realisierung.}, language = {de} } @misc{Deuflhard2002, author = {Deuflhard, Peter}, title = {From Molecular Dynamics to Conformational Dynamics in Drug Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6878}, number = {02-20}, year = {2002}, abstract = {Computational drug design studies molecular recognition in the {\em virtual lab}. The arising Hamiltonian dynamics is known to be chaotic and ill-conditioned already after picoseconds, whereas times are \$msec\$ up to \$min\$. Classical molecular dynamics with long term trajectory computation gives, at best, information about time and statistical ensemble averages. The present paper surveys a recent new modeling approach called {\em conformational dynamics}, which is due to the author and Ch. Sch{\"u}tte. This approach achieves information about the dy time scales by telescoping a short term deterministic model with a statistical model. Examples of small biomolecules are included.}, language = {en} } @misc{Rambau2002, author = {Rambau, J{\"o}rg}, title = {TOPCOM: Triangulations of Point Configurations and Oriented Matroids}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6849}, number = {02-17}, year = {2002}, abstract = {TOPCOM is a package for computing triangulations of point configurations and oriented matroids. For example, for a point configuration one can compute the chirotope, components of the flip graph of triangulations, enumerate all triangulations. The core algorithms implemented in TOPCOM are described, and implentation issues are discussed.}, language = {en} } @misc{GroetschelKrumkeRambauetal.2002, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Torres, Luis Miguel}, title = {Making the Yellow Angels Fly: Online Dispatching Of Service Vehicles in Real Time}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6858}, number = {02-18}, year = {2002}, abstract = {Combinatorial online optimization is an area with lots of applications and potential for significant progress, both in theory and practice. In this short note we sketch the ADACproblem, a typical large-scale online optimization problem, discuss some theoretical and pratical issues coming up, and explain, very briefly, how we approach this problem mathematically. Online problems are a battlefield of heuristics with many strong claims about their solution quality. We indicate that a stronger problem orientation and the use of a little more mathematics may yield.}, language = {en} } @misc{EisenblaetterFuegenschuhKochetal.2002, author = {Eisenbl{\"a}tter, Andreas and F{\"u}genschuh, Armin and Koch, Thorsten and Koster, Arie M.C.A. and Martin, Alexander and Pfender, Tobias and Wegel, Oliver and Wess{\"a}ly, Roland}, title = {Modelling Feasible Network Configurations for UMTS}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6837}, number = {02-16}, year = {2002}, abstract = {A model for the optimisation of the location and configuration of base stations in a UMTS network is described. The focus is primarily on modelling the configuration problem sufficiently accurate using mixed-integer variables and (essentially) linear constraints. These constraints reflect the limited downlink code capacity in each cell, the interference limitations for successful up- and downlink transmissions, the need for sufficiently strong (cell) pilot signals, and the potential gain for mobiles from being in soft(er) hand-over. It is also explained how to use the model as a basis for rating network configurations.}, language = {en} } @misc{GroetschelHenk2002, author = {Gr{\"o}tschel, Martin and Henk, Martin}, title = {On the Representation of Polyhedra by Polynomial Inequalities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6826}, number = {02-15}, year = {2002}, abstract = {A beautiful result of Br{\"o}cker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every \$d\$-dimensional polyhedron admits a representation as the set of solutions of at most \$d(d+1)/2\$ polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the 2- and 3-dimensional case we get the expected number \$d(d+1)/2\$.}, language = {en} } @misc{Deuflhard2002, author = {Deuflhard, Peter}, title = {Adaptive Pseudo-transient Continuation for Nonlinear Steady State Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6814}, number = {02-14}, year = {2002}, abstract = {Pseudo--transient continuation methods are quite popular for the numerical solution of steady state problems, typically in PDEs. They are based on an embedding into a time dependent initial value problem. In the presence of dynamical invariants the Jacobian matrix of the nonlinear equation system is bound to be singular. The paper presents a convergence analysis which takes this property into account -- in contrast to known approaches. On the basis of the new analysis adaptive algorithms are suggested in detail. These include a variant with Jacobian approximations as well as inexact pseudo--transient continuation, both of which play an important role in discretized PDEs. Numerical experiments are left to future work.}, language = {en} } @misc{WeberGalliat2002, author = {Weber, Marcus and Galliat, Tobias}, title = {Characterization of Transition States in Conformational Dynamics using Fuzzy Sets}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6791}, number = {02-12}, year = {2002}, abstract = {Recently, a novel approach for the analysis of molecular dynamics on the basis of a transfer operator has been introduced. Therein conformations are considered to be disjoint metastable clusters within position space of a molecule. These clusters are defined by almost invariant characteristic functions that can be computed via {\em Perron Cluster} analysis. The present paper suggests to replace crisp clusters with {\em fuzzy} clusters, i.e. to replace characteristic functions with membership functions. This allows a more sufficient characterization of transiton states between different confor conformations and therefore leads to a better understanding of molecular dynamics. Fur thermore, an indicator for the uniqueness of metastable fuzzy clusters and a fast algorithm for the computation of these clusters are described. Numerical examples are included.}, language = {en} } @misc{Weiser2002, author = {Weiser, Martin}, title = {Linear convergence of an interior point method for linear control constrained optimal control problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6809}, number = {02-13}, year = {2002}, abstract = {The paper provides a detailed analysis of a short step interior point algorithm applied to linear control constrained optimal control problems. Using an affine invariant local norm and an inexact Newton corrector, the well-known convergence results from finite dimensional linear programming can be extended to the infinite dimensional setting of optimal control. The present work complements a recent paper of Weiser and Deuflhard, where convergence rates have not been derived. The choice of free parameters, i.e. the corrector accuracy and the number of corrector steps, is discussed.}, language = {en} } @misc{Hupfeld2002, author = {Hupfeld, Felix}, title = {Hierarchical Structures in Attribute-based Namespaces and their Application to Browsing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7280}, number = {03-06}, year = {2002}, abstract = {While attribute-value pairs are a popular method to name objects, information retrieval from those attribute-based namespaces is not an easy task. The user has to recall correct attribute names and values and master the syntax and semantics of query formulation. This paper describes hierarchical structures in attribute-based namespaces, shows how to extract them efficiently and evaluates the quality of these structures in an user experiment. It proposes an user interface for browsing attribute-named object sets which makes this task resemble todays file-system browsers and compares the usability of this interface to normal form-based methods in an user study.}, language = {en} } @misc{HougardyWagler2002, author = {Hougardy, Stefan and Wagler, Annegret}, title = {Perfectness is an Elusive Graph Property}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6787}, number = {02-11}, year = {2002}, abstract = {A graph property is called elusive (or evasive) if every algorithm for testing this property has to read in the worst case \$n\choose 2\$ entries of the adjacency matrix of the given graph. Several graph properties have been shown to be elusive, e.g. planarity (Best et al) or \$k\$-colorability (Bollobas). A famous conjecture of Karp says that every non-trivial monotone graph property is elusive. We prove that a non-monotone but hereditary graph property is elusive: perfectness.}, language = {en} } @misc{BorndoerferLoebelWeider2002, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {Integrierte Umlauf- und Dienstplanung im {\"O}ffentlichen Nahverkehr}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6773}, number = {02-10}, year = {2002}, abstract = {Wir beschreiben einen Ansatz zur integrierten Umlauf- und Dienstplanung im {\"o}ffentlichen Nahverkehr. Der Ansatz zielt auf die Verbesserung des Gesamtwirkungsgrades dieser beiden Planungsschritte und auf die besondere Planungsproblematik im Regionalverkehr. Wir entwickeln dazu mathematische Optimierungstechniken f{\"u}r den Einsatz in den Planungssystemen MICROBUS II und DIVA.}, language = {de} } @misc{EisenblaetterGroetschelKoster2002, author = {Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Koster, Arie M.C.A.}, title = {Frequenzplanung im Mobilfunk}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6762}, number = {02-09}, year = {2002}, abstract = {Telekommunikation ist seit Jahren \glqq in\grqq. Zun{\"a}chst gab es einen enormen Aufschwung; neue Technologien und Dienste haben eine {\"u}berw{\"a}ltigende, nicht vorhersehbare Akzeptanz gefunden. Derzeit ist -- ausgel{\"o}st durch die UMTS-Lizenzversteigerungen, Rezessions- und S{\"a}ttigungstendenzen -- eine Krise zu verzeichnen. Viele (auch wir) sind davon {\"u}berzeugt, dass technischer Fortschritt und n{\"u}tzliche Dienste demn{\"a}chst die Stimmung wieder {\"a}ndern werden. Wenigen ist allerdings bewusst, welche Rolle Mathematik bei der Entwicklung und dem effizienten Einsatz vieler der neuen Kommunikationstechnologien spielt. In diesem Artikel soll kein {\"U}berblick {\"u}ber diesen umfangreichen Themenkreis gegeben werden. Wir zeigen lediglich an einem konkreten Beispiel aus dem Mobilfunk, der Frequenzplanung in GSM-Funknetzen, was man durch geeignete Modellierung der praktischen Fragestellung und den Einsatz problemad{\"a}quater Algorithmen erreichen kann.}, language = {de} } @misc{Wagler2002, author = {Wagler, Annegret}, title = {Antiwebs are Rank-Perfect}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6742}, number = {02-07}, year = {2002}, abstract = {\We discuss a nested collection of three superclasses of perfect graphs: near-perfect, rank-perfect, and weakly rank-perfect graphs. For that, we start with the description of the stable set polytope for perfect graphs and allow stepwise more general facets for the stable set polytopes of the graphs in each superclass. Membership in those three classes indicates how far a graph is away from being perfect. We investigate for webs and antiwebs to which of the three classes they belong. We provide a complete description of the facets of the stable set polytope for antiwebs (with help of a result due to Shepherd on near-bipartite graphs). The main result is that antiwebs are rankperfect.}, language = {en} } @misc{Wolf2002, author = {Wolf, Thomas}, title = {The integration of systems of linear PDEs using conservation laws of syzygies}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6751}, number = {02-08}, year = {2002}, abstract = {The purpose of the paper is to formulate and use syzygies for systems of linear PDEs. The computation of an equivalent of a GCD for linear partial differential operators will save us their factorization which is otherwise only possible algorithmically in special cases. After showing the computation with the new and the traditional method and comparing both in the next three sections, the algorithm is explained in general and an overview is given.}, language = {en} } @misc{ReinefeldStuebenSchintkeetal.2002, author = {Reinefeld, Alexander and St{\"u}ben, Hinnerk and Schintke, Florian and Din, George}, title = {GuiGen: A Toolset for Creating Customized Interfaces for Grid User Communities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6737}, number = {02-06}, year = {2002}, abstract = {\textsf{\itshape{GuiGen}} is a comprehensive set of tools for creating customized graphical user interfaces (GUIs). It draws from the concept of computing portals, which are here seen as interfaces to application-specific computing services for user communities. While \textsf{\itshape{GuiGen}} was originally designed for the use in computational grids, it can be used in client/server environments as well. Compared to other GUI generators, \textsf{\itshape{GuiGen}} is more versatile and more portable. It can be employed in many different application domains and on different target platforms. With \textsf{\itshape{GuiGen}}, application experts (rather than computer scientists) are able to create their own individually tailored GUIs.}, language = {en} } @misc{KrumkeRambau2002, author = {Krumke, Sven and Rambau, J{\"o}rg}, title = {Probieren geht {\"u}ber Studieren? Entscheidungshilfen f{\"u}r kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6723}, number = {02-05}, year = {2002}, abstract = {Die Automatisierung von innerbetrieblicher Logistik erfordert -- {\"u}ber die physikalische Steuerung von Ger{\"a}ten hinaus -- auch eine effiziente Organisation der Transporte: ein Aufgabenfeld der kombinatorischen Optimierung. Dieser Artikel illustriert anhand von konkreten Aufgabenstellungen die Online-Problematik (unvollst{\"a}ndiges Wissen) sowie die Echtzeit-Problematik (beschr{\"a}nkte Rechenzeit), auf die man in der innerbetrieblichen Logistik trifft. Der Text gibt einen {\"U}berblick {\"u}ber allgemeine Konstruktionsprinzipien f{\"u}r Online-Algorithmen und Bewertungsmethoden, die bei der Entscheidung helfen, welche Algorithmen f{\"u}r eine vorliegende Problemstellung geeignet sind.}, language = {de} } @misc{KuberekLillLitscheetal.2002, author = {Kuberek, Monika and Lill, Monika and Litsche, Stefan and Lohrum, Stefan and L{\"u}gger, Joachim and Otto, Dagmar and Rusch, Beate}, title = {Entwicklungsprojekt "KOBV-Informationsportal" : Teilprojekte der 1. Stufe}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6678}, number = {01-41}, year = {2002}, abstract = {Die KOBV-Suchmaschine hat seit ihrer Inbetriebnahme Ende 1999 entscheidend zur Verbesserung der Informationsinfrastruktur in Berlin und Brandenburg beigetragen. Auf der Basis der offenen Plattform KOBV-Suchmaschine wird die KOBV-Zentrale gemeinsam mit den Bibliotheken in den n{\"a}chsten Jahren das Dienstleistungsangebot des KOBV und seiner Bibliotheken kontinuierlich erweitern. Dabei sollen die Prinzipien des KOBV - Offenheit, Heterogenit{\"a}t und Dezentralit{\"a}t auf technischer und organisatorischer Ebene - gewahrt bleiben. Die einzelnen KOBV-Bibliotheken werden sich mit ihren Angeboten in unterschiedlicher Weise im Web positionieren. Die Integration auf regionaler Ebene kann und soll die lokalen Angebote nicht k{\"u}nstlich vereinheitlichen. Das kooperative Portal, das in der Region aufgebaut wird, ist als System geplant, in dem zentrales Portal und lokale Portale nicht hierarchisch einander zugeordnet, sondern miteinander vernetzt sind. Das \glqq KOBV-Informationsportal \grqq soll in der KOBV-Zentrale im Rahmen eines wissenschaftlichen Projektes von Mitte 2001 bis Ende 2003 aufgebaut werden. Das vorliegende Papier gibt einen ersten allgemeinen Einblick, welche Funktionen das \glqq KOBV-Informationsporta \grqq umfassen soll und stellt die Teilprojekte der 1. Stufe vor.}, language = {de} } @misc{HohageSchmidt2002, author = {Hohage, Thorsten and Schmidt, Frank}, title = {On the Numerical Solution of Nonlinear Schr{\"o}dinger type equations in fiber optics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6715}, number = {02-04}, year = {2002}, abstract = {The aim of this paper is to develop fast methods for the solution of nonlinear Schr{\"o}dinger type equations in fiber optics. Using the method of lines we have to solve a stiff system of ordinary differential equations where the eigenvalues of the Jacobian are close to the imaginary axis. This is usually done by a Split Step method. Here we consider the extrapolation of Split Step methods with adaptive order and step size control. For more complicated nonlinearities, in particular stimulated Raman scattering, Split Step methods are less efficient since symmetry is either destroyed or requires much additional effort. In this case we use implicit Runge Kutta formulas of Gauß type. The key point for the efficient implementation of these methods is that the system of nonlinear algebraic equations can be solved without setting up the Jacobian. The proposed methods are compared to other methods, in particular exponential integrators, the method of Marcuse, and the method of Blow and Wood.}, language = {en} } @misc{Wagler2002, author = {Wagler, Annegret}, title = {Relaxing Perfectness: Which Graphs are 'Almost' Perfect?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6700}, number = {02-03}, year = {2002}, abstract = {For all perfect graphs, the stable set polytope STAB\$(G)\$ coincides with the fractional stable set polytope QSTAB\$(G)\$, whereas STAB\$(G) \subset\$ QSTAB\$(G)\$ holds iff \$G\$ is imperfect. Padberg asked in the early seventies for ``almost'' perfect graphs. He characterized those graphs for which the difference between STAB\$(G)\$ and QSTAB\$(G)\$ is smallest possible. We develop this idea further and define three polytopes between STAB\$(G)\$ and QSTAB\$(G)\$ by allowing certain sets of cutting planes only to cut off all the fractional vertices of QSTAB\$(G)\$. The difference between QSTAB\$(G)\$ and the largest of the three polytopes coinciding with STAB\$(G)\$ gives some information on the stage of imperfectness of the graph~\$G\$. We obtain a nested collection of three superclasses of perfect graphs and survey which graphs are known to belong to one of those three superclasses. This answers the question: which graphs are ``almost'' perfect?}, language = {en} } @misc{PfeifleRambau2002, author = {Pfeifle, Julian and Rambau, J{\"o}rg}, title = {Computing Triangulations Using Oriented Matroids}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6692}, number = {02-02}, year = {2002}, abstract = {Oriented matroids are combinatorial structures that encode the combinatorics of point configurations. The set of all triangulations of a point configuration depends only on its oriented matroid. We survey the most important ingredients necessary to exploit oriented matroids as a data structure for computing all triangulations of a point configuration, and report on experience with an implementation of these concepts in the software package TOPCOM. Next, we briefly overview the construction and an application of the secondary polytope of a point configuration, and calculate some examples illustrating how our tools were integrated into the {\sc polymake} framework.}, language = {en} } @misc{HohageSchmidtZschiedrich2002, author = {Hohage, Thorsten and Schmidt, Frank and Zschiedrich, Lin}, title = {A new method for the solution of scattering problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6683}, number = {02-01}, year = {2002}, abstract = {We present a new efficient algorithm for the solution of direct time-harmonic scattering problems based on the Laplace transform. This method does not rely on an explicit knowledge of a Green function or a series representation of the solution, and it can be used for the solution of problems with radially symmetric potentials and problems with waveguides. The starting point is an alternative characterization of outgoing waves called \emph{pole condition}, which is equivalent to Sommerfeld's radiation condition for problems with radially symmetric potentials. We obtain a new representation formula, which can be used for a numerical evaluation of the exterior field in a postprocessing step. Based on previous theoretical studies, we discuss the numerical realization of our algorithm and compare its performance to the PML method.}, language = {en} } @phdthesis{Eisenblaetter2001, author = {Eisenbl{\"a}tter, Andreas}, title = {Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10132}, year = {2001}, abstract = {Mobile cellular communcication is a key technology in today's information age. Despite the continuing improvements in equipment design, interference is and will remain a limiting factor for the use of radio communication. This Ph. D. thesis investigates how to prevent interference to the largest possible extent when assigning the available frequencies to the base stations of a GSM cellular network. The topic is addressed from two directions: first, new algorithms are presented to compute "good" frequency assignments fast; second, a novel approach, based on semidef inite programming, is employed to provide lower bounds for the amount of unavoidable interference. The new methods proposed for automatic frequency planning are compared in terms of running times and effectiveness in computational experiments, where the planning instances are taken from practice. For most of the heuristics the running time behavior is adequate for inter active planning; at the same time, they provide reasonable assignments from a practical point of view (compared to the currently best known, but substantially slower planning methods). In fact, several of these methods are successfully applied by the German GSM network operator E-Plus. The currently best lower bounds on the amount of unavoidable (co-channel) interference are obtained from solving semidefinite programs These programs arise as nonpolyhedral relaxation of a minimum /c-parti tion problem on complete graphs. The success of this approach is made plausible by revealing structural relations between the feasible set of the semidefinite program and a polytope associated with an integer linear programming formulation of the minimum ^-partition problem. Comparable relations are not known to hold for any polynomial time solvable polyhedral relaxation of the minimum ^-partition problem. The appli cation described is one of the first of semidefinite programming for large industrial problems in combinatorial optimization.}, language = {en} } @misc{AardalHoeselKosteretal.2001, author = {Aardal, Karen I. and Hoesel, Stan P.M. van and Koster, Arie M.C.A. and Mannino, Carlo and Sassano, Antonio}, title = {Models and Solution Techniques for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6667}, number = {01-40}, year = {2001}, abstract = {{\begin{rawhtml} Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0 \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.}, language = {en} } @misc{BodlaenderKosterEijkhofetal.2001, author = {Bodlaender, Hans L. and Koster, Arie M.C.A. and Eijkhof, Frank van den and Gaag, Linda C. van der}, title = {Pre-processing for Triangulation of Probabilistic Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6655}, number = {01-39}, year = {2001}, abstract = {The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.}, language = {en} } @misc{KosterBodlaenderHoesel2001, author = {Koster, Arie M.C.A. and Bodlaender, Hans L. and Hoesel, Stan P.M. van}, title = {Treewidth: Computational Experiments}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6644}, number = {01-38}, year = {2001}, abstract = {Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed \$k\$, linear time algorithms exist to solve the decision problem ``treewidth \$\leq k\$'', their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.}, language = {en} } @misc{Helmberg2001, author = {Helmberg, Christoph}, title = {Numerical Evaluation of SBmethod}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6637}, number = {01-37}, year = {2001}, abstract = {We report numerical results for SBmethod --- a publically available implementation of the spectral bundle method --- applied to the 7\$^{th}\$ DIMACS challenge test sets that are semidefinite relaxations of combinatorial optimization problems. The performance of the code is heavily influenced by parameters that control bundle update and eigenvalue computation. Unfortunately, no mathematically sound guidelines for setting them are known. Based on our experience with SBmethod, we propose heuristics for dynamically updating the parameters as well as a heuristc for improving the starting point. These are now the default settings of SBmethod Version 1.1. We compare their performance on the DIMACS instances to our previous best choices for Version 1.0. SBmethod Version 1.1 is also part of the independent DIMACS benchmark by H.~Mittelmann. Based on these results we try to analyze strengths and weaknesses of our approach in comparison to other codes for large scale semidefinite programming.}, language = {en} } @misc{Kuberek2001, author = {Kuberek, Monika}, title = {Der KOBV - eine regionale Service-Einrichtung f{\"u}r Nutzer und Bibliothekare}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6620}, number = {01-36}, year = {2001}, abstract = {Dem vorliegenden Aufsatz liegt ein Vortrag zugrunde, den die Verfasserin auf der Ersten Gemeinsamen Fachtagung der DBV-Landesverb{\"a}nde Berlin und Brandenburg "Wir machen den Weg frei : Fusionen - Kooperationen in Berlin und Brandenburg" am 17. Oktober 2001 gehalten hat, in der Vortragsreihe "M{\"o}glichkeiten und Grenzen von Ausleih- und bibliographischen Verb{\"u}nden - V{\"O}B Berlin, V{\"O}B Brandenburg, KOBV". Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) ist angetreten, um auf der Basis neuer Technologien zeitgem{\"a}ße, nutzerorientierte Dienstleistungen f{\"u}r den Informationsbereich zu entwickeln und die Informationsinfrastruktur in der Region Berlin-Brandenburg neu zu organisieren. Dabei setzt der KOBV insbesondere auf das Internet. Die Verfasserin beschreibt die einzelnen Stufen, in denen die Dienste des KOBV aufgebaut wurden und kontinuierlich weiter ausgebaut werden. Dabei zeigt sie Vorteile auf, die Nutzern und Bibliotheken durch den Verbund entstehen, und lotet gleichzeitig die Grenzen aus, die dem Verbund gesetzt sind.}, language = {de} } @misc{BrandtBrandt2001, author = {Brandt, Andreas and Brandt, Manfred}, title = {Individual Overflow and Freed Carried Traffics for a Link with Trunk Reservation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6615}, number = {01-35}, year = {2001}, abstract = {Two traffic streams \$\Phi_1\$, \$\Phi_2\$ are offered a link. The calls of \$\Phi_i\$ require exponential holding times with parameter \$\mu\$ and are accepted if less than \$C_i\$ trunks are occupied. Approximating the \$\Phi_i\$ by appropriate renewal processes meeting their first two moments, defined as the moments of the numbers of calls in virtual links of infinite capacity to which the traffic streams as freed traffics are virtually directed and where the calls get fresh exponential i.i.d.\ holding times with parameter \$\mu\$, stable recursive algorithms of complexity \$O(\max(C_1,C_2))\$ are derived for the first two defined as above moments of the individual overflow and freed carried traffics. The results offer a unified handling of both overflow and carried traffics in circuit switching networks with trunk reservation, providing a basis for new two-moment network dimensioning algorithms.}, language = {en} } @misc{SokolovWolf2001, author = {Sokolov, Vladimir V. and Wolf, Thomas}, title = {Classification of integrable polynomial vector evolution equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6601}, number = {01-34}, year = {2001}, abstract = {Several classes of systems of evolution equations with one or two vector unknowns are considered. We investigate also systems with one vector and one scalar unknown. For these classes all equations having the simplest higher symmetry are listed.}, language = {en} } @misc{IlgenfritzKerlerMuellerPreusskeretal.2001, author = {Ilgenfritz, Ernst-Michael and Kerler, Werner and M{\"u}ller-Preussker, Michael and St{\"u}ben, Hinnerk}, title = {Parallel tempering in full QCD with Wilson fermions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6593}, number = {01-33}, year = {2001}, abstract = {We study the performance of QCD simulations with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering on \$10^4\$ and \$12^4\$ lattices. In order to compare tempered with standard simulations, covariance matrices between sub-ensembles have to be formulated and evaluated using the general properties of autocorrelations of the parallel tempering algorithm. We find that rendering the hopping parameter \$\kappa\$ dynamical does not lead to an essential improvement. We point out possible reasons for this observation and discuss more suitable ways of applying parallel tempering to QCD.}, language = {en} } @misc{ZoecklerReinBrandtetal.2001, author = {Z{\"o}ckler, Malte and Rein, Karlheinz and Brandt, Robert and Stalling, Detlev and Hege, Hans-Christian}, title = {Creating Virtual Insect Brains with Amira}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6589}, number = {01-32}, year = {2001}, abstract = {By combining techniques of preparation, histology, confocal microscopy, data visualization and data processing, we have created and recently published a standard brain model for drosophila and honey bee brains. This report describes the algorithms and implementation of the corresponding software modules. At the same time it serves as a user's guide for scientist who want to reproduce the results for differerent species or mutants.}, language = {en} } @misc{KoberSaderZeilhoferetal.2001, author = {Kober, Cornelia and Sader, Robert and Zeilhofer, Hans-Florian and Prohaska, Steffen and Zachow, Stefan and Deuflhard, Peter}, title = {Anisotrope Materialmodellierung f{\"u}r den menschlichen Unterkiefer}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6574}, number = {01-31}, year = {2001}, abstract = {Im Rahmen der biomechanischen Simulation kn{\"o}cherner Organe ist die Frage nach einer befriedigenden Materialbeschreibung nach wie vor ungel{\"o}st. Computertomographische Datens{\"a}tze liefern eine r{\"a}umliche Verteilung der (R{\"o}ntgen-)Dichte und erm{\"o}glichen damit eine gute Darstellung der individuellen Geometrie. Weiter k{\"o}nnen die verschiedenen Materialbestandteile des Knochens, Spongiosa und Kortikalis, voneinander getrennt werden. Aber die richtungsab{\"a}ngige Information der Materialanisotropie ist verloren. In dieser Arbeit wird ein Ansatz f{\"u}r eine anisotrope Materialbeschreibung vorgestellt, die es erm{\"o}glicht, den Einfluss der individuellen kn{\"o}chernen Struktur auf das makroskopische Materialverhalten abzusch{\"a}tzen.}, language = {de} } @misc{KaehlerHege2001, author = {K{\"a}hler, Ralf and Hege, Hans-Christian}, title = {Interactive Volume Rendering of Adaptive Mesh Refinement Data}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6561}, number = {01-30}, year = {2001}, abstract = {Many phenomena in nature and engineering happen simultaneously on rather diverse spatial and temporal scales, i.e.\ exhibit a multi-scale character. Therefore various hierarchical data structures and numerical schemes have been devised to represent quantitatively such phenomena. A special numerical multilevel technique, associated with a particular hierarchical data structure, is so-called Adaptive Mesh Refinement (AMR). This scheme achieves locally very high spatial and temporal resolutions. Due to its popularity, many scientists are in need of interactive visualization tools for AMR data. In this article we present a 3D texture-based volume rendering algorithm for AMR data, that directly utilizes the hierarchical structure. Thereby interactive rendering even for large data sets is achieved. In particular the problems of interpolation artifacts, opacity corrections, and texture memory limitations are addressed. The algorithm's value in practice is demonstrated with simulation and image data.}, language = {en} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Telota - was soll das?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6538}, number = {01-27}, year = {2001}, abstract = {Telota ist ein Kunstwort, das f{\"u}r alle Aktivit{\"a}ten der Berlin-Brandenburgischen Akademie der Wissenschaften steht, die der F{\"o}rderung von Forschung, Kommunikation und Pr{\"a}sentation durch elektronische Medien dienen. In diesem Artikel werden die Entstehung des Telota-Projektes geschildert und die Ziele diskutiert, die mit diesem Projekt erreicht werden sollen. Es geht darum, moderne Informationstechnik bewusst, geplant und nachhaltig f{\"u}r alle Belange der {\rm BBAW} einzusetzen. Informationstechnische Werkzeuge sollen f{\"u}r die wissenschaftliche Arbeit effizient genutzt werden; die Information nach innen und nach außen soll deutlich verbessert werden; eine bessere Kommunikationsinfrastuktur soll die Zusammenarbeit f{\"o}rdern.}, language = {de} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Empfehlungen des Wissenschaftsrates zur digitalen Informationsversorgung durch Hochschulbibliotheken}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6546}, number = {01-28}, year = {2001}, abstract = {Der Wissenschaftsrat hat in seiner Juli-Sitzung 2001 \glqq Empfehlungen zur digitalen Informationsversorgung durch Hochschulbibliotheken \grqq verabschiedet. Einige der Vorschl{\"a}ge des Wissenschaftsrates k{\"o}nnen, falls sie von den angesprochenen Institutionen aufgenommen werden, zu einer nachhaltigen Ver{\"a}nderung der wissenschaftlichen Informationslandschaft f{\"u}hren. In meinem kurzen Kommentar zu diesem Papier m{\"o}chte ich auf einige dieser Anregungen hinweisen.}, language = {de} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Mein digitaler Traum}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6558}, number = {01-29}, year = {2001}, abstract = {Von welcher "Informationsumwelt" tr{\"a}umt jemand, der f{\"u}r seine wissenschaftliche (und sonstige) Arbeit digitale Informationstechnologie intensiv einsetzt? In diesem Artikel beschreibe ich meinen "digitalen Traum". Er ist ganz einfach zu formulieren:"Ich will alles und zwar sofort, jederzeit, "{\"u}berall" und kostenlos zur Verf{\"u}gung haben." Ich schildere, was davon heute schon (fast) realisiert ist und was noch fehlt. Ich skizziere einige zentrale Schwierigkeiten der vollst{\"a}ndigen Realisierung und skizziere m{\"o}gliche L{\"o}sungen.}, language = {de} } @misc{Helmberg2001, author = {Helmberg, Christoph}, title = {A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6527}, number = {01-26}, year = {2001}, abstract = {The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges to the optimal solution under reasonable assumptions on the separation oracle and the feasible set. We have implemented a practical variant of the cutting plane algorithm for improving semidefinite relaxations of constrained quadratic 0-1 programming problems by odd-cycle inequalities. We also consider separating odd-cycle inequalities with respect to a larger support than given by the cost matrix and present a heuristic for selecting this support. Our preliminary computational results for max-cut instances on toroidal grid graphs and balanced bisection instances indicate that warm start is highly efficient and that enlarging the support may sometimes improve the quality of relaxations considerably.}, language = {en} } @misc{Steinbach2001, author = {Steinbach, Marc}, title = {General Information Constraints in Stochastic Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6502}, number = {01-24}, year = {2001}, abstract = {Scenario tree models of stochastic programs arise naturally under standard nonanticipativity assumptions. We demonstrate how tree-sparse programs cover the general case, with \emph{arbitrary} information constraints. Detailed examples and intuitive interpretations illuminate the basic thoughts behind the abstract but elementary construction.}, language = {en} } @misc{KaehlerSimonHege2001, author = {K{\"a}hler, Ralf and Simon, Mark and Hege, Hans-Christian}, title = {Fast Volume Rendering of Sparse High-Resolution Datasets Using Adaptive Mesh Refinement Hierarchies}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6516}, number = {01-25}, year = {2001}, abstract = {In this paper we present an algorithm that accelerates 3D texture-based volume rendering of large and sparse data sets. A hierarchical data structure (known as AMR tree) consisting of nested uniform grids is employed in order to efficiently encode regions of interest. The hierarchies resulting from this kind of space partitioning yield a good balance between the amount of volume to render and the number of texture bricks -- a prerequisite for fast rendering. Comparing our approach to an octree based algorithm we show that our algorithm increases rendering performance significantly for sparse data. A further advantage is that less parameter tuning is necessary.}, language = {en} } @misc{HohageSchmidtZschiedrich2001, author = {Hohage, Thorsten and Schmidt, Frank and Zschiedrich, Lin}, title = {Solving time-harmonic scattering problems based on the pole condition: Convergence of the PML method}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6494}, number = {01-23}, year = {2001}, abstract = {In this paper we study the PML method for Helmholtz-type scattering problems with radially symmetric potential. The PML method consists in surrounding the computational domain by a \textbf{P}erfectly \textbf{M}atched sponge \textbf{L}ayer. We prove that the approximate solution obtained by the PML method converges exponentially fast to the true solution in the computational domain as the thickness of the sponge layer tends to infinity. This is a generalization of results by Lassas and Somersalo based on boundary integral eqaution techniques. Here we use techniques based on the pole condition instead. This makes it possible to treat problems without an explicitly known fundamental solution.}, language = {en} } @misc{KrumkeRambauTorres2001, author = {Krumke, Sven and Rambau, J{\"o}rg and Torres, Luis Miguel}, title = {Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6484}, number = {01-22}, year = {2001}, abstract = {Given a set of service requests (events), a set of guided servers (units), and a set of unguided service contractors (conts), the vehicle dispatching problem {\sl vdp} is the task to find an assignment of events to units and conts as well as tours for all units starting at their current positions and ending at their home positions (dispatch) such that the total cost of the dispatch is minimized. The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit costs consist of driving costs, service costs and overtime costs; cont costs consist of a fixed cost per service; event costs consist of late costs linear in the late time, which occur whenever the service of the event starts later than its deadline. The program \textsf{ZIBDIP} based on dynamic column generation and set partitioning yields solutions on heavy-load real-world instances (215 events, 95 units) in less than a minute that are no worse than 1\\% from optimum on state-of-the-art personal computers.}, language = {en} } @misc{Otto2001, author = {Otto, Dagmar}, title = {Informationsportale und Digitale Bibliotheken}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6479}, number = {01-21}, year = {2001}, abstract = {Im ersten Teil des folgenden Aufsatzes werden allgemeine {\"U}berlegungen zur Entwicklung von Bibliotheken hin zu Informationsvermittlungsstellen f{\"u}r sowohl elektronische wie auch gedruckte Medien angestellt. Basierend auf den Ergebnissen der Evaluation digitaler Bibliotheken und Informationsportale in Deutschland wird ein erster Kriterienkatalog f{\"u}r ein Verbund-Informationsportal f{\"u}r den Kooperativen Bibliotheksverbund Berlin-Brandenburg entwickelt. Im Anhang befindet sich der Statusbericht {\"u}ber Informationsportale und digitale Bibliotheken in Deutschland. Dazu wurden sieben digitale Bibliotheken auf Verbundebene und 21 Bibliotheken nach Bundesl{\"a}ndern evaluiert.}, language = {de} } @misc{Koch2001, author = {Koch, Thorsten}, title = {ZIMPL User Guide}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6466}, number = {01-20}, year = {2001}, abstract = {{\sc Zimpl} is a little language to translate the mathematical model of a problem into a linear or (mixed-)integer mathematical program expressed in {\tt lp} or {\tt mps} file format which can be read by a LP or MIP solver.}, language = {en} }