TY - GEN
A1 - Bley, Andreas
T1 - A Lagrangian Approach for Integrated Network Design and Routing in IP Networks
N2 - We consider the problem of designing a network that employs a non-bifurcated shortest path routing protocol. The network's nodes and the set of potential links are given together with a set of forecasted end-to-end traffic demands. All relevant hardware components installable at links or nodes are considered. The goal is to simultaneously choose the network's topology, to decide which hardware components to install on which links and nodes, and to find appropriate routing weights such that the overall network cost is minimized. In this paper, we present a mathematical optimization model for this problem and an algorithmic solution approach based on a Lagrangian relaxation. Computational results achieved with this approach for several real-world network planning problems are reported.
T3 - ZIB-Report - 03-29
KW - Network Planning
KW - Routing
KW - IP Routing
KW - Lagrangian relaxation
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7515
ER -
TY - GEN
A1 - Lutz, Frank H.
T1 - Small Examples of Non-Constructible Simplicial Balls and Spheres
N2 - We construct non-constructible simplicial $d$-spheres with $d+10$ vertices and non-constructible, non-realizable simplicial $d$-balls with $d+9$ vertices for $d\geq 3$.
T3 - ZIB-Report - 03-28
KW - simplicial balls and spheres
KW - constructibility
KW - shellability
KW - vertex-decomposability
KW - knots in 3-balls and 3-spheres
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7500
ER -
TY - GEN
A1 - Fleuren, Maria
A1 - Stüben, Hinnerk
A1 - Zegwaard, Gideon
T1 - MoDySim - A parallel dynamical UMTS simulator
N2 - UMTS is a 3rd generation mobile telecommunication system which enables multi-service and multi-bit rate communication going beyond the possibilities of previous systems. The simulator MoDySim models UMTS in great detail. Characteristics of UMTS such as soft hand-over and the interdependency of load and capacity among neighbouring cells are challenges for the parallelisation of such a system. In this paper we explain how the software was parallelised and present performance results of a UMTS simulation for the city of Berlin.
T3 - ZIB-Report - 03-26
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7489
ER -
TY - GEN
A1 - Ilgenfritz, Ernst-Michael
A1 - Kerler, Werner
A1 - Müller-Preussker, Michael
A1 - Sternbeck, André
A1 - Stüben, Hinnerk
T1 - A numerical reinvestigation of the Aoki phase with $N_f=2$ Wilson fermions at zero temperature
N2 - We report on a numerical reinvestigation of the Aoki phase in lattice QCD with two flavors of Wilson fermions where the parity-flavor symmetry is spontaneously broken. For this purpose the Hybrid Monte Carlo algorithm was used and an explicit symmetry-breaking source term $h\bar{\psi} i \gamma_{5} \tau^{3}\psi$ was added to the Wilson fermion action. The order parameter $\langle\bar{\psi}i\gamma_{5}\tau^{3}\psi\rangle$ was studied at several values of $(\beta,\kappa,h)$ on lattices of sizes $4^4$ to $12^4$. Our largest lattices can be considered as infintely large allowing to extrapolate to $h=0$. The existence of a parity-flavor-breaking phase can be confirmed at $\beta=4.0$ and $\beta=4.3$ while we find no sign of parity-flavor-breaking at $\beta=4.6$ and $\beta=5.0$.
T3 - ZIB-Report - 03-27
KW - Wilson fermions
KW - phase diagram
KW - parity-flavor symmetry
KW - Aoki phase
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7492
ER -
TY - GEN
A1 - Bosse, Hartwig
A1 - Grötschel, Martin
A1 - Henk, Martin
T1 - Polynomial Inequalities Representing Polyhedra
N2 - 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.
T3 - ZIB-Report - 03-25
KW - polyhedra and polytopes
KW - semi-algebraic sets
KW - polyhedral combinatorics
KW - polynomial inequalities
KW - stability index
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7473
ER -
TY - GEN
A1 - Koster, Arie M.C.A.
A1 - Zymolka, Adrian
A1 - Jäger, Monika
A1 - Hülsermann, Ralf
A1 - Gerlach, Christoph
T1 - Demand-wise Shared Protection for Meshed Optical Networks
N2 - In this paper, a new shared protection mechanism for meshed optical networks is presented. Significant network design cost reductions can be achieved in comparison to the well-known 1+1 protection scheme. Demand-wise Shared Protection (DSP) bases on the diversification of demand routings and exploits the network connectivity to restrict the number of backup lightpaths needed to provide the desired level of prorection. Computational experiments approve the benefits of the concept DSP for cost efficient optical network designs.
T3 - ZIB-Report - 03-24
KW - optical network design
KW - shared protection
KW - meshed optical networks
KW - diversification
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7461
ER -
TY - GEN
A1 - Kober, Cornelia
A1 - Erdmann, Bodo
A1 - Sader, Robert
A1 - Zeilhofer, Hans-Florian
T1 - Simulation of the Human Mandible: Comparison of Bone Mineral Density and Stress/Strain Profiles due to Masticatory
Muscles' Traction
N2 - The correlation of the inner architecture of bone and its functional loading was already stated by Wolff in 1892. Our objective is to demonstrate this interdependence in the case of the human mandible. For this purpose, stress/strain profiles occuring at a human lateral bite were simulated. Additionally, by a combination of computer graphics modules, a three--dimensional volumetric visualization of bone mineral density could be given. Qualitative correspondences between the density profile of the jaw and the simulated stress/strain profiles could be pointed out. In the long run, this might enable the use of the simulation for diagnosis and prognosis. The solution of the underlying partial differential equations describing linear elastic material behaviour was provided by an adaptive finite element method. Estimates of the discretization errors, local grid refinement, and multilevel techniques guaranteed the reliability and efficiency of the method.
T3 - ZIB-Report - 03-23
KW - linear elasticity
KW - finite element method
KW - adaptive grid refinement
KW - stress/strain analysis
KW - human mandible
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7458
ER -
TY - GEN
A1 - Wagler, Annegret
T1 - Critical and Anticritical Edges with respect to Perfectness
N2 - We call an edge $e$ of a perfect graph $G$ critical if $G-e$ is imperfect and call $e$ anticritical if $G+e$ is imperfect. The present paper surveys several questions in this context. We ask in which perfect graphs critical and anticritical edges occur and how to detect such edges. The main result by [{\sl Wagler, PhD thesis 2000}] shows that a graph does not admit any critical edge if and only if it is Meyniel. The goal is to order the edges resp.~non-edges of certain perfect graphs s.t. deleting resp.~adding all edges in this order yields a sequence of perfect graphs only. Results of [{\sl Hayward 1985}] and [{\sl Spinrad & Sritharan 1995}] show the existence of such edge orders for weakly triangulated graphs; the line-perfect graphs are precisely these graphs where all edge orders are perfect [{\sl Wagler 2001}]. Such edge orders cannot exist for every subclass of perfect graphs that contains critically resp.~anticritically perfect graphs where deleting resp.~adding an arbitrary edge yields an imperfect graph. We present several examples and properties of such graphs, discuss constructions and characterizations from [{\sl Wagler 1999, Wagler PhD thesis 2000}]. An application of the concept of critically and anticritically perfect graphs is a result due to [{\sl Hougardy & Wagler 2002}] showing that perfectness is an elusive graph property.
T3 - ZIB-Report - 03-22
KW - Perfect graphs
KW - critical edges
KW - perfect edge orders
KW - critically perfect graphs
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7446
ER -
TY - GEN
A1 - Pêcher, Arnaud
A1 - Wagler, Annegret
T1 - A construction for non-rank facets of stable set polytopes of webs
N2 - Graphs with circular symmetry, called webs, are relevant for describing the stable set polytopes of two larger graph classes, quasi-line graphs [{\sl Giles and Trotter 1981, Oriolo 2001}] and claw-free graphs [{\sl Galluccio and Sassano 1997, Giles and Trotter 1981}]. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem [{\sl Grötschel, Lov\'asz, and Schrijver 1988}]. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number $\leq 3$ have rank facets only [{\sl Dahl 1999, Trotter 1975}] while there are examples with clique number $\geq 4$ having non-rank facets [{\sl e.g. Liebling et al. 2003, Oriolo 2001, P\^echer and Wagler 2003}]. In this paper, we provide a construction for non-rank facets of stable set polytopes of webs. We use this construction to prove, for several fixed values of $\omega$ including all odd values at least 5, that there are only finitely many webs with clique number $\omega$ whose stable set polytopes admit rank facets only.
T3 - ZIB-Report - 03-21
KW - web
KW - rank-perfect graph
KW - stable set polytope
KW - (non-)rank facet
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7437
ER -
TY - GEN
A1 - Deuflhard, Peter
A1 - Schütte, Christof
T1 - Molecular Conformation Dynamics and Computational Drug Design
N2 - The paper surveys recent progress in the mathematical modelling and simulation of essential molecular dynamics. Particular emphasis is put on computational drug design wherein time scales of $msec$ up to $min$ play the dominant role. Classical long-term molecular dynamics computations, however, would run into ill-conditioned initial value problems already after time spans of only $psec=10^{-12} sec$. Therefore, in order to obtain results for times of pharmaceutical interest, a combined deterministic-stochastic model is needed. The concept advocated in this paper is the direct identification of metastable conformations together with their life times and their transition patterns. It can be interpreted as a {\em transfer operator} approach corresponding to some underlying hybrid Monte Carlo process, wherein short-term trajectories enter. Once this operator has been discretized, which is a hard problem of its own, a stochastic matrix arises. This matrix is then treated by {\em Perron cluster analysis}, a recently developed cluster analysis method involving the numerical solution of an eigenproblem for a Perron cluster of eigenvalues. In order to avoid the 'curse of dimension', the construction of appropriate boxes for the spatial discretization of the Markov operator requires careful consideration. As a biomolecular example we present a rather recent SARS protease inhibitor.
T3 - ZIB-Report - 03-20
KW - conformation dynamics
KW - Monte Carlo methods
KW - transfer operations
KW - Hamiltonian dynamics
KW - Smoluchowski dynamics
KW - metastable sets
KW - Perron cluster an
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7427
ER -
TY - GEN
A1 - Deuflhard, Peter
A1 - Weber, Marcus
T1 - Robust Perron Cluster Analysis in Conformation Dynamics
N2 - The key to molecular conformation dynamics is the direct identification of metastable conformations, which are almost invariant sets of molecular dynamical systems. Once some reversible Markov operator has been discretized, a generalized symmetric stochastic matrix arises. This matrix can be treated by Perron cluster analysis, a rather recent method involving a Perron cluster eigenproblem. The paper presents an improved Perron cluster analysis algorithm, which is more robust than earlier suggestions. Numerical examples are included.
T3 - ZIB-Report - 03-19
KW - Markov chains
KW - cluster algorithms
KW - Perron cluster analysis
KW - conformation dynamics
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7415
ER -
TY - GEN
A1 - Brandt, Andreas
A1 - Brandt, Manfred
T1 - A sample path relation for the sojourn times in G/G/1-PS systems and its applications
N2 - For the general G/G/1 processor sharing (PS) system a sample path result for the sojourn times in a busy period is proved, which yields a relation between the sojourn times under PS and FCFS discipline. In particular, the result provides a formula for the mean sojourn time in G/D/1-PS in terms of the mean sojourn time in the corresponding G/D/1-FCFS, generalizing known results for GI/M/1 and M/GI/1. Extensions of the formula provide the basis for a two-moment approximation of the mean sojourn time in G/GI/1-PS in terms of a related G/D/1-FCFS.
T3 - ZIB-Report - 03-18
KW - G/G/1
KW - G/GI/1
KW - G/D/1
KW - G/M/1
KW - processor sharing
KW - sojourn time
KW - waiting time
KW - busy period
KW - sample path
KW - first come first served
KW - two-moment ap
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7401
ER -
TY - GEN
A1 - Kähler, Ralf
A1 - Hege, Hans-Christian
T1 - Visualization of Time-Dependent Adaptive Mesh Refinement Data
N2 - Analysis of phenomena that simultaneously occur on quite different spatial and temporal scales require adaptive, hierarchical schemes to reduce computational and storage demands. For data represented as grid functions, the key are adaptive, hierarchical, time-dependent grids that resolve spatio-temporal details without too much redundancy. Here, so-called AMR grids gain increasing popularity. For visualization and feature identification/tracking, the underlying continuous function has to be faithfully reconstructed by spatial and temporal interpolation. Well designed interpolation methods yield better results and help to reduce the amount of data to be stored. We address the problem of temporal interpolation of AMR grid data, e.g.\ for creation of smooth animations or feature tracking. Intermediate grid hierarchies are generated by merging the cells on all refinement levels that are present in the key frames considered. Utilizing a clustering algorithm a structure of nested grids is induced on the resulting collection of cells. The grid functions are mapped to the intermediate hierarchy, thus allowing application of appropriate interpolation techniques.
T3 - ZIB-Report - 03-16
KW - AMR
KW - non-conforming hexahedral grids
KW - multi-resolution techniques
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7384
ER -
TY - GEN
A1 - Benger, Werner
A1 - Hege, Hans-Christian
T1 - Tensor Splats
N2 - An improved general-purpose technique for the visualization of symmetric positive definite tensor fields of rank two is described. It is based on a splatting technique that is built from tiny transparent glyph primitives which are capable to incorporate the full directional information content of a tensor. The result is an information-rich image that allows to read off the preferred directions in a tensor field at each point of a three-dimensional volume or two-dimensional surface. It is useful for analyzing slices or volumes of a three-dimensional tensor field and can be overlayed with standard volume rendering or color mapping. The application of the rendering technique is demonstrated on general relativistic data and the diffusion tensor field of a human brain.
T3 - ZIB-Report - 03-17
KW - tensor field visualization
KW - metric
KW - splatting
KW - volume rendering
KW - general relativity
KW - diffusion tensor images
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7393
ER -
TY - GEN
A1 - Dalitz, Wolfgang
A1 - Neun, Winfried
A1 - Sperber, Wolfram
T1 - Semantic Annotation in Mathematics and Math-Net
N2 - The Web of the future will provide a huge amount of information. We need better ways for dealing with and managing the information. A qualified semantic annotation of the information plays a key role for the Web of the future. This article gives an overview about the efforts of the mathematical community to build up a distributed and open information and communication system for mathematics: the Math-Net. The Math-Net Initiative has developed metadata schemas for some classes of Web resources which are relevant in mathematics. Math-Net Services process this information and enable the user to efficiently search and access the information.
T3 - ZIB-Report - 03-15
KW - information and communication system for mathematics
KW - Math-Net Semantic Webdata schemas
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7379
ER -
TY - GEN
A1 - Becchetti, Luca
A1 - Leonardi, Stefano
A1 - Marchetti-Spaccamela, Alberto
A1 - Schäfer, Guido
A1 - Vredeveld, Tjark
T1 - Smoothening Helps: A Probabilistic Analysis of the Multi-Level Feedback Algorithm
N2 - In this paper we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by [{\sl Spielman and Teng} STOC 2001] to explain the behaviour of algorithms that work well in practice while performing very poorly from a worst case analysis point of view. We apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range $[1,2^K]$. We use a partial bit randomization model, where the initial processing times are smoothened by changing the $k$ least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of $O(max((2^k/\sigma)^3, (2^k/\sigma)^2 2^K-k))$, where $\sigma$ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of $O(2^K-k)$ if $\sigma = \Theta(2^k)$. %The analysis holds for an oblivious as well as for a stronger adaptive %adversary. We also prove an $\Omega(2^{K-k})$ lower bound for any deterministic algorithm that is run on processing times smoothened according to the partial bit randomization model. For various other smoothening models, including the additive symmetric smoothening model used by [{\sl Spielman and Teng}], we give a higher lower bound of $\Omega(2^K)$. A direct consequence of our result is also the first average case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform distribution.
T3 - ZIB-Report - 03-14
KW - smoothed analysis
KW - competitive analysis
KW - scheduling
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7366
ER -
TY - GEN
T1 - Jahresbericht 2002
T3 - Jahresbericht - 2002
KW - Annual Report
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9776
SN - 0934-5892
ER -
TY - GEN
A1 - Coja-Oghlan, Amin
A1 - Krumke, Sven
A1 - Nierhoff, Till
T1 - Average Case Analysis of a Hard Dial-a-Ride Problem
N2 - In the dial-a-ride-problem (DARP) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find a shortest transportation for the server. We study the DARP when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm which almost surely finds an optimal solution. Moreover, with high probability the optimality of the solution found can be certified efficiently. We also examine the complexity of the DARP in a semi-random setting and in the unweighted case.
T3 - ZIB-Report - 03-12
KW - dial-a-ride-problem
KW - average case analysis
KW - MST-heuristic
KW - Steiner trees
KW - NP-hardness
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7348
ER -
TY - GEN
A1 - Weiser, Martin
A1 - Schiela, Anton
A1 - Deuflhard, Peter
T1 - Asymptotic Mesh Independence of Newton's Method Revisited
N2 - The paper presents a new affine invariant theory on asymptotic mesh independence of Newton's method in nonlinear PDEs. Compared to earlier attempts, the new approach is both much simpler and more natural from the algorithmic point of view. The theory is exemplified at collocation methods for ODE boundary value problems and at finite element methods for elliptic PDE problems.
T3 - ZIB-Report - 03-13
KW - mesh independence
KW - nonlinear partial differential equations
KW - Newton method
KW - finite element method
KW - collocation method
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7352
ER -
TY - GEN
A1 - Woitke, Peter
A1 - Helling, Christiane
T1 - Formation and structure of quasi-static cloud-layers in brown dwarf atmospheres
N2 - In this paper, first solutions of the dust moment equations developed in [{\sl Woitke & Helling 2002}] for the description of dust formation and precipitation in brown dwarf and giant gas planet atmospheres are presented. We consider the special case of a static brown dwarf atmosphere, where dust particles continuously nucleate from the gas phase, grow by the accretion of molecules, settle gravitationally and re-evaporate thermally. Applying a kinetic description of the relevant microphysical and chemical processes for TiO$_2$-grains, the model makes predictions about the large-scale stratification of dust in the atmosphere, the depletion of molecules from the gas phase, the supersaturation of the gas in the atmosphere as well as the mean size and the mass fraction of dust grains as function of depth. Our results suggest that the nucleation occu in the upper atmosphere where the gas is cool, strongly depleted, but nevertheless highly supersaturated ($S\!\gg\!1$). These particles settle gravitationally and populate the warmer layers below, where the in-situ formation (nucleation) is ineffective or even not possible. During their descent, the particles grow up to radii $\approx\!0.3\,\mu{\rm m}\,...\,150\,\mu{\rm m}$, depending gas around the cloud base. The particles finally sink into layers which are sufficiently hot to cause their thermal evaporation. Hence, an effective transport mechanism for condensable elements exi considered solid/liquid material. In the stationary case studied here, this downward directed element transport by precipitating dust grains is balanced by an upward directed flux of condensable elements from the deep interior of the star via convective mixing (no dust without mixing). We find a self-regulation mechanism which leads to an approximate phase equilibrium ($S\!\approx\!1$) around the cloud base. The mass fraction of dust present in the atmosphere results be to approximately given by the mass fraction of condensable elements in the gas being mixed up.
T3 - ZIB-Report - 03-11
KW - dust
KW - precipitation
KW - clouds
KW - atmosphere
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7338
ER -
TY - GEN
A1 - Koster, Arie M.C.A.
A1 - Zymolka, Adrian
T1 - Polyhedral Investigations on Stable Multi-Sets
N2 - Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in [{\sl Koster and Zymolka 2002}] and present results of three types: on the relation to other combinatorial problems, on the polyhedral structure of the stable multi-set polytope, and on the computational impact of the polyhedral results. First of all, we embed stable multi-sets in a framework of generalized set packing problems and point out several relations. The second part discusses properties of the stable multi-set polytope. We show that the vertices of the linear relaxation are half integer and have a special structure. Moreover, we strengthen the conditions for cycle inequalities to be facet defining, show that the separation problem for these inequalities is polynomial time solvable, and discuss the impact of chords in cycles. The last result allows to interpret cliques as cycles with many chords. The paper is completed with a computational study to the practical importance of the cycle inequalities. The computations show that the performance of state-of-the-art integer programming solvers can be improved significantly by including these inequalities.
T3 - ZIB-Report - 03-10
KW - stable multi-sets
KW - polyhedral combinatorics
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7324
ER -
TY - GEN
A1 - Orlowski, Sebastian
A1 - Wessäly, Roland
T1 - Comparing Restoration Concepts using Optimal Network Configurations with Integrated Hardware and Routing
Decisions
N2 - We investigate the impact of link and path restoration on the cost of telecommunication networks. The surprising result is the following: the cost of an optimal network configuration is almost independent of the restoration concept if (i) the installation of network elements (ADMs, DXCs, or routers) and interface cards, (ii) link capacities, and (iii) working and restoration routings are simultaneously optimized. We present a mixed-integer programming model which integrates all these decisions. Using a branch-and-cut algorithm (with column generation to deal with all potential routing paths), we solve structurally different real-world problem instances and show that the cost of optimal solutions is almost independent of the used restoration concept. In addition, we optimize spare capacities for given shortest working paths which are predetermined with respect to different link metrics. In comparison to simultaneous optimization of working and restoration routings, it turns out that this approach does not allow to obtain predictably good results.
T3 - ZIB-Report - 03-09
KW - survivable network design
KW - link and path restoration
KW - hardware configuration
KW - branch-and-cut algorithm
KW - routing
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7316
ER -
TY - GEN
A1 - Hochmuth, Reinhard
A1 - Deuflhard, Peter
T1 - Multiscale Analysis for the Bio-Heat Transfer Equation
N2 - The bio-heat transfer equation is a macroscopic model for describing the heat transfer in microvascular tissue. In [{\sl Deuflhard, Hochmuth 2002}] the authors applied homogenization techniques to derive the bio-heat transfer equation as asymptotic result of boundary value problems which provide a microscopic description for microvascular tissue. Here those results are generalized to a geometrical setting where the regions of blood are allowed to be connected. Moreover, asymptotic corrector results are derived.
T3 - ZIB-Report - 03-08
KW - bio-heat equation
KW - hyperthermia
KW - homogenization
KW - correctors
KW - heat transfer
KW - Robin boundary conditions
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7302
ER -
TY - GEN
A1 - Helling, Christiane
A1 - Klein, Rupert
A1 - Woitke, Peter
A1 - Sedlmayr, Erwin
T1 - Dust formation in brown dwarf atmospheres under conditions of driven turbulence
N2 - Based on the knowledge gained from direct numerical simulations which are only possible in the microscale regime, a concept of driven turbulence is presented which allows to enter the mesoscopic scale regime. Here, dust formation under stochastic hydro- and thermodynamic conditions is studied: constructively superimposed stochastic waves initiate dust formation by the creation of singular nucleation events. It, hence, results a varying mean grain size and dust density in space and time. The newly formed dust changes the thermodynamic behavior from almost isotherm to adiabatic and chemically depletes the gas phase.
T3 - ZIB-Report - 03-07
KW - dust formation
KW - turbulence modelling
KW - stochastic boundaries
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7294
ER -
TY - GEN
A1 - Weber, Marcus
T1 - Improved Perron Cluster Analysis
N2 - The problem of clustering data can often be transformed into the problem of finding a hidden block diagonal structure in a stochastic matrix. Deuflhard et al. have proposed an algorithm that state s the number $k$ of clusters and uses the sign structure of $k$ eigenvectors of the stochastic matrix to solve the cluster problem. Recently Weber and Galliat discovered that this system of eigenvectors can easily be transformed into a system of $k$ membership functions or soft characteristic functions describing the clusters. In this article we explain the corresponding cluster algorithm and point out the underlying theory. By means of numerical examples we explain how the grade of membership can be interpreted.
T3 - ZIB-Report - 03-04
KW - cluster analysis
KW - stochastic matrices
KW - almost invariant sets
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7260
ER -
TY - GEN
A1 - Koch, Thorsten
T1 - The final NETLIB-LP results
N2 - The NETLIB has now served for 18 years as a repository of LP problem instances. From the beginning to the present day there was some uncertainness about the precise values of the optimal solutions. We implemented a program using exact rational arithmetic to compute proofs for the feasibility and optimality of an LP solution. This paper reports the \emph{exact} optimal objective values for all NETLIB problems.
T3 - ZIB-Report - 03-05
KW - Linear Programming
KW - Simplex
KW - Netlib
KW - rational arithmetic
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7274
ER -
TY - GEN
A1 - Borndörfer, Ralf
T1 - Combinatorial Packing Problems
N2 - This article investigates a certain class of combinatorial packing problems and some polyhedral relations between such problems and the set packing problem.
T3 - ZIB-Report - 03-03
KW - Packing problems
KW - polyhedral combinatorics
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7255
ER -
TY - GEN
A1 - Sander, Oliver
A1 - Krause, Rolf
T1 - Automatic Construction of Boundary Parametrizations for Geometric Multigrid Solvers
N2 - We present an algorithm that constructs parametrizations of boundary and interface surfaces automatically. Starting with high-resolution triangulated surfaces describing the computational domains, we iteratively simplify the surfaces yielding a coarse approximation of the boundaries with the same topological type. While simplifying we construct a function that is defined on the coarse surface and whose image is the original surface. This function allows access to the correct shape and surface normals of the original surface as well as to any kind of data defined on it. Such information can be used by geometric multigrid solvers doing adaptive mesh refinement. Our algorithm runs stable on all types of input surfaces, including those that describe domains consisting of several materials. We have used our method with success in different fields and we discuss examples from structural mechanics and biomechanics.
T3 - ZIB-Report - 03-02
KW - boundary parametrization
KW - surface simplification
KW - multigrid
KW - geometry
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7240
ER -
TY - GEN
A1 - Pecher, Arnaud
A1 - Wagler, Annegret
T1 - On Non-Rank Facets of Stable Set Polytopes of Webs with Clique Number Four
N2 - Graphs with circular symmetry, called webs, are relevant w.r.t. describing the stable set polytopes of two larger graph classes, quasi-line graphs and claw-free graphs. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number $\leq 3$ have rank facets only while there are examples with clique number $>4$ having non-rank facets.
T3 - ZIB-Report - 03-01
KW - web
KW - rank-perfect graph
KW - stable set polytope
KW - (non-)rank facet
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7238
ER -
TY - GEN
A1 - Kuberek, Monika
A1 - Lohrum, Stefan
A1 - Rascanu, Raluca
T1 - Endnutzerbasierte Online-Fernleihe im KOBV - Kurzbeschreibung
N2 - Der KOBV setzt für die endnutzerbasierte Online-Fernleihe den Sisis ZFL-Server (Zentraler Fernleih-Server) ein. Mit dem Einsatz des ZFL-Servers können in den Bibliotheken echte Rationalisierungseffekte erzielt werden: Der Server ist in der Lage, Fernleih-Bestellungen an lokale Systeme zu übergeben, so dass sie im lokalen System automatisch - ohne Eingreifen von Bibliotheksmitarbeitern - weiterverarbeitet werden können. Im KOBV können derzeit Sisis- und Aleph-Lokalsysteme diese Schnittstelle voll bedienen. Andere Bibliothekssysteme im KOBV, die diese Schnittstelle nicht bedienen können, werden mittels eines E-Mail-Verfahrens in die Online-Fernleihe integriert. Die vorliegende Kurzbeschreibung der Online-Fernleihe im KOBV soll - im Gegensatz zur Spezifikation, die möglichst vollständig sein sollte - einen leicht verständlichen Einblick in die Abläufe der Online-Fernleihe vermitteln. Nach einem Überblick über zu erwartende Rationalisierungseffekte ist der Ablauf einer Online-Fernleih-Bestellung - veranschaulicht durch eine Graphik mit dem technischen Aufbau im KOBV - kurz dargestellt. \vspace{6mm} {\it Hinweis:} Die von einer Arbeitsgruppe des KOBV erstellte Spezifikation zur Online-Fernleihe ist als ZIB Report 02-30 auf dem Preprint-Server des ZIB veröffentlicht. Siehe: Monika Kuberek (Red.) {\begin{rawhtml} Spezifikation für eine Verbund-Fernleih-Software im KOBV \end{rawhtml}}
T3 - ZIB-Report - 02-55
KW - Bibliotheksverbund
KW - Fernleihe
KW - KOBV
KW - Kooperativer Bibliotheksverbund Berlin-Brandenburg
KW - Online-Fernleihe
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7221
ER -
TY - GEN
A1 - Brodersen, Maren
A1 - Hodoroaba, Lavinia
T1 - Navigation in the KOBV-Informationsportal Conceptual View
N2 - The KOBV Informationsportal aims to be a universal gateway to the sources of information hosted by the partner libraries from the Berlin-Brandenburg area. Due to the large number of these sources, an intuitive navigation is an essential component of the portal. The navigation-component should preserve the partner libraries? independence and overcome their administrative and technical differences. This paper proposes a collection-level navigation with four dimensions: the sources? subject areas (e.g. the first two levels of DDC), the sources? type (e.g. e-journals, databases, OPACs, etc.), the sources? location (e.g. Berlin, Brandenburg) / the library that hosts that source and the sources? accessing state (e.g. free, restricted, etc.).
T3 - ZIB-Report - 02-54
KW - Portale
KW - KOBV
KW - Navigation
KW - Collection-level
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7216
ER -
TY - GEN
A1 - Litsche, Stefan
T1 - Zur Zugriffskontrolle im KOBV
N2 - Mit der Entwicklung des KOBV-Informationsportals soll den Benutzern in der Region Berlin-Brandenburg ein verbesserter Zugang zu Informationsressourcen geboten werden. Einen wesentlichen Anteil diese Auf der Grundlage der Analyse der Rahmenbedingungen werden Anforderungen an die Zugriffskontrolle im KOBV definiert und Lösungsmöglichkeiten auf der Ebene allgemeiner Modelle diskutiert.
T3 - ZIB-Report - 02-53
KW - Zugriffskontrolle
KW - Access Management
KW - Informationssysteme
KW - KOBV
KW - Authentisierung
KW - Autorisierung
Y1 - 2003
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7203
ER -
TY - THES
A1 - Galliat, Tobias
T1 - Adaptive Multilevel Cluster Analysis by Self-Organizing Box Maps
N2 - Als Cluster Analyse bezeichnet man den Prozess der Suche und Beschreibung von Gruppen (Clustern) von Objekten, so daß die Objekte innerhalb eines Clusters bezüglich eines gegebenen Maßes maximal homogen sind. Die Homogenität der Objekte hängt dabei direkt oder indirekt von den Ausprägungen ab, die sie für eine Anzahl festgelegter Attribute besitzen. Die Suche nach Clustern läßt sich somit als Optimierungsproblem auffassen, wobei die Anzahl der Cluster vorher bekannt sein muß. Wenn die Anzahl der Objekte und der Attribute groß ist, spricht man von komplexen, hoch-dimensionalen Cluster Problemen. In diesem Fall ist eine direkte Optimierung zu aufwendig, und man benötigt entweder heuristische Optimierungsverfahren oder Methoden zur Reduktion der Komplexität. In der Vergangenheit wurden in der Forschung fast ausschließlich Verfahren für geometrisch basierte Clusterprobleme entwickelt. Bei diesen Problemen lassen sich die Objekte als Punkte in einem von den Attributen aufgespannten metrischen Raum modellieren; das verwendete Homogenitätsmaß basiert auf der geometrischen Distanz der den Objekten zugeordneten Punkte. Insbesondere zur Bestimmung sogenannter metastabiler Cluster sind solche Verfahren aber offensichtlich nicht geeignet, da metastabile Cluster, die z.B. in der Konformationsanalyse von Biomolekülen von zentraler Bedeutung sind, nicht auf einer geometrischen, sondern einer dynamischen Ähnlichkeit beruhen. In der vorliegenden Arbeit wird ein allgemeines Clustermodell vorgeschlagen, das zur Modellierung geometrischer, wie auch dynamischer Clusterprobleme geeignet ist. Es wird eine Methode zur Komplexitätsreduktion von Clusterproblemen vorgestellt, die auf einer zuvor generierten Komprimierung der Objekte innerhalb des Datenraumes basiert. Dabei wird bewiesen, daß eine solche Reduktion die Clusterstruktur nicht zerstört, wenn die Komprimierung fein genug ist. Mittels selbstorganisierter neuronaler Netze lassen sich geeignete Komprimierungen berechnen. Um eine signifikante Komplexitätsreduktion ohne Zerstörung der Clusterstruktur zu erzielen, werden die genannten Methoden in ein mehrstufiges Verfahren eingebettet. Da neben der Identifizierung der Cluster auch deren effiziente Beschreibung notwendig ist, wird ferner eine spezielle Art der Komprimierung vorgestellt, der eine Boxdiskretisierung des Datenraumes zugrunde liegt. Diese ermöglicht die einfache Generierung von regelbasierten Clusterbeschreibungen. Für einen speziellen Typ von Homogenitätsfunktionen, die eine stochastische Eigenschaft besitzen, wird das mehrstufige Clusterverfahren um eine Perroncluster Analyse erweitert. Dadurch wird die Anzahl der Cluster, im Gegensatz zu herkömmlichen Verfahren, nicht mehr als Eingabeparameter benötigt. Mit dem entwickelten Clusterverfahren kann erstmalig eine computergestützte Konformationsanalyse großer, für die Praxis relevanter Biomoleküle durchgeführt werden. Am Beispiel des HIV Protease Inhibitors VX-478 wird dies detailliert beschrieben.
KW - Biochemical conformations
KW - cluster analysis
KW - molecular dynamics
KW - Perron cluster analysis
KW - Self-Organizing Maps
KW - Biochemical conformations
KW - cluster analysis
KW - molecular dynamics
KW - Perron cluster analysis
KW - Self-Organizing Maps
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:188-2002001258
ER -
TY - THES
A1 - Schütt, Thorsten
T1 - Synchronisation von verteilten Verzeichnisstrukturen
N2 - Das Management von großen Datenmengen spielt eine immer wichtigere Rolle, wie aktuelle Entwicklungen in der Hochenergiephysik [2] zeigen. Für das DataGrid-Projekt zum Beispiel ist es notwendig, große Datenmengen auf mehrere Rechenzentren in Europa zu verteilen und die Daten untereinander zu synchronisieren. Auch innerhalb von Clustern gewinnen mit zunehmender Anzahl der Knoten Werkzeuge zur effizienten Synchronisation und Verteilung von Daten an Bedeutung. Im Rahmen dieser Arbeit wurde ein effizientes Verfahren zur Synchronisation von verteilten Verzeichnisstrukturen entwickelt und implementiert. Mit diesem Verfahren ist es möglich, unabhängige Änderungen an beliebigen Repositories gleichzeitig durchzuführen. Das Verfahren benötigt keine zentrale Instanz, wodurch eine gegenüber vielen existierenden Verfahren verbesserte Skalierbarkeit erreicht werden konnte. Dabei wurden Erkenntnisse aus der Graphentheorie eingesetzt und weiterentwickelt, um die Netzwerktopolo-gie und -handbreiten zwischen den Rechnern zu berücksichtigen. Durch die Verwendung einer Offline-Synchronisation werden Änderungen erst dann an andere Rechner propagiert, wenn der Nutzer dies anstößt. Das kann zum Beispiel nach einer abgeschlossenen Transaktion, die Änderungen an mehreren Dateien beinhaltet, angemessen sein.
N2 - Current developments in high energy physics [2] show that the management of large datasets plays an important role. For the DataGrid project it is necessary to distribute large datasets over several computing centers all over Europe and to synchronize these datasets. Within clusters tools for efficient synchronization and distribution of data become more important, too. In this thesis, a method to synchronize distributed directory structures was developed and implemented which makes it possible to perform independent changes to arbitrary repositories simultaneously. This method needs no central instance and therefore the presented system achieves a better scalability than many existing systems. Knowledge from graph theory was used and improved to take the network topology and the network bandwidth between the computers into account. By using offline synchronization, changes will only be propagated when the user initiates it. This can be reasonable after a completed transaction which consists of changes on several files.
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10071
ER -
TY - GEN
A1 - Schintke, Florian
A1 - Reinefeld, Alexander
T1 - On the Cost of Reliability in Large Data Grids
N2 - Global grid environments do not only provide massive aggregated computing power but also an unprecedented amount of distributed storage space. Unfortunately, dynamic changes caused by component failures, local decisions, and irregular data updates make it difficult to efficiently use this capacity. In this paper, we address the problem of improving data availability in the presence of unreliable components. We present an analytical model for determining an optimal combination of distributed replica catalogs, catalog sizes, and replica servers. Empirical simulation results confirm the accuracy of our theoretical analysis. Our model captures the characteristics of highly dynamic environments like peer-to-peer networks, but it can also be applied to more centralized, less dynamic grid environments like the European {\em DataGrid}.
T3 - ZIB-Report - 02-52
KW - replication
KW - availability
KW - reliability
KW - distributed catalog
KW - data grid
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7195
ER -
TY - GEN
A1 - Eisenblätter, Andreas
A1 - Koster, Arie M.C.A.
A1 - Wallbaum, Randolf
A1 - Wessäly, Roland
T1 - Load Balancing in Signaling Transfer Points
N2 - Signaling is crucial to the operation of modern telecommunication networks. A breakdown in the signaling infrastructure typically causes customer service failures, incurs revenue losses, and hampers the company image. Therefore, the signaling network has to be highest reliability and survivability. This in particular holds for the routers in such a network, called \textit{signaling transfer points\/} (STPs). The robustness of an STP can be improved by equally distributing the load over the internal processing units. Several constraints have to be taken into account. The load of the links connected to a processing unit changes over time introducing an imbalance of the load. In this paper, we show how integer linear programming can be applied to reduce the imbalance within an STP, while keeping the number of changes small. Two alternative models are presented. Computational experiments validate the integer programming approach in practice. The GSM network operator E-Plus saves substantial amounts of time and money by employing the proposed approach.
T3 - ZIB-Report - 02-50
KW - Signaling network
KW - STP
KW - load-balancing
KW - integer programming
KW - computations
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7179
ER -
TY - GEN
A1 - Woitke, Peter
A1 - Helling, Christiane
T1 - Dust in brown dwarfs II. The coupled problem of dust formation and sedimentation
N2 - In this paper, we quantify and discuss the physical and surface chemical processes leading to the formation, temporal evolution and sedimentation of dust grains in brown dwarf and giant gas planet atmospheres: nucleation, growth, evaporation and gravitational settling. Considering dust particles of arbitrary sizes in the different hydrodynamical regimes (free molecular flow, laminar flow, turbulent flow), we evaluate the equilibrium drift velocities (final fall speeds) and the growth rates of the particles due to accretion of molecules. We show that a depth-dependent maximum size of the order of $a_{\rm max}\!\approx\!1\,\mu{\rm m\,(upper\ regions)} \ldots 100\,\mu{\rm m\,(lower\ regions)}$ exists, which depends on the condensate and the stellar parameters, beyond which gravitational settling is faster than growth. Larger particles can probably not be formed and sustained in brown dwarf atmospheres. We furthermore argue that the acceleration towards equilibrium drift is always very fast and that the temperature increase of the grains due to the release of latent heat during the growth process is negligible. Based on these findings, we formulate the problem of dust formation coupled to the local element depletion/enrichment of the gas in brown dwarf atmospheres by means of a system of partial differential equations. These equations state an extension of the moment method developed by Gail\plus Sedlmayr\,(1988) with an additional advective term to account for the effect of size-dependent drift velocities of the grains. A dimensionless analysis of the new equations reveals a hierarchy of nucleation $\to$ growth $\to$ drift $\to$ evaporation, which characterises the life cycle of dust grains in brown dwarf atmospheres. The developed moment equations can be included into hydrodynamics or classical stellar atmosphere models. Applications of this description will be presented in a forthcoming paper of this series.
T3 - ZIB-Report - 02-51
KW - dust formation
KW - precipitation
KW - brown dwarfs
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7186
ER -
TY - GEN
A1 - Wolf, Thomas
T1 - Applications of CRACK in the Classification of Integrable Systems
N2 - The talk given by the author at the CRM workshop on Superintegrability in Sep.\ 2002 and this related paper report on work in two subjects. One is the collaboration with Vladimir Sokolov and Takayuki Tsuchida in an effort to classify polynomial integrable vector evolution equations. The other is the computer algebra package {\sc Crack} which did the main computations in solving large bi-linear algebraic systems. Although originally designed to solve over-determined systems of partial differential equations a number of extensions made {\sc Crack} a powerful tool for solving systems of bi-linear algebraic equations. Such systems turn up in many different classification problems some of which were investigated by other participants of this workshop. Two additional applications are outlined. In the talk on which this article is based a method to reduce the length of equations was presented which proved to be useful in solving the bi-linear algebraic systems. Due to numerous asked questions about the computer program, a more complete overview is given in the appendix.
T3 - ZIB-Report - 02-48
KW - Integrability
KW - evolution equations
KW - quadratic Hamiltonians
KW - Computer algebra
KW - Bi-linear algebraic systems
KW - conservation laws
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7159
ER -
TY - GEN
A1 - Eijkhof, Frank van den
A1 - Bodlaender, Hans L.
A1 - Koster, Arie M.C.A.
T1 - Safe reduction rules for weighted treewidth
N2 - Several sets of reductions rules are known for preprocessing a graph when computing its treewidth. In this paper, we give reduction rules for a weighted variant of treewidth, motivated by the analysis of algorithms for probabilistic networks. We present two general reduction rules that are safe for weighted treewidth. They generalise many of the existing reduction rules for treewidth. Experimental results show that these reduction rules can significantly reduce the problem size for several instances of real-life probabilistic networks.
T3 - ZIB-Report - 02-49
KW - weighted treewidth
KW - preprocessing
KW - probabilistic networks
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7164
ER -
TY - GEN
A1 - Helling, Christiane
T1 - Circuit of Dust in Substellar Atmopsheres
N2 - Substellar atmospheres are cool and dense enough that dust forms very efficiently. As soon as these particles are formed, they sizedependently precipitate due to the large gravity of the objects. Arriving in hot atmospheric layers, the dust evaporates and enriches the gas by those elements from which it has formed. The upper atmospheric layers are depleted by the same elements. Non-continuous and spatially inhomogeneous convective element replenishment, generating a turbulent fluid field, completes the circuit of dust. The formation of dust in substellar atmosphere is described by extending the classical theory of Gail\plus Sedlmayr for the case of different gas and dust velocities. Turbulence is modeled in different scale regimes which reveals turbulence as trigger for dust formation in hot environments. Both mechanisms cause the dust to be present in else wise dust-hostile region: precipitation transports the dust into hot regions, and turbulence allows the formation of dust in there.
T3 - ZIB-Report - 02-47
KW - dust formation
KW - drift
KW - turbulence modelling
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7142
ER -
TY - GEN
A1 - Deuflhard, Peter
T1 - A Comparison of Related Concepts in Computational Chemistry and Mathematics
N2 - This article studies the relation of the two scientific languages Chemistry and Mathematics via three selected comparisons: (a) QSSA versus dynamic ILDM in reaction kinetics, (b) lumping versus discrete Galerkin methods in polymer chemistry, and (c) geometrical conformations versus metastable conformations in drug design. The common clear message from these comparisons is that chemical intuition may pave the way for mathematical concepts just as chemical concepts may gain from mathematical precisioning. Along this line, significant improvements in chemical research and engineering have already been possible -- and can be further expected in the future from the dialogue between the two scientific languages.
T3 - ZIB-Report - 02-46
KW - dimension reduction
KW - model reduction
KW - QSSA
KW - ILDM
KW - reaction kinetics
KW - polyreaction kinetics
KW - Hamilton systems
KW - conformations
KW - metastability
KW - d
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7138
ER -
TY - THES
A1 - Schmidt, Frank
T1 - A New Approach to Coupled Interior-Exterior Helmholtz-Type Problems: Theory and Algorithms
N2 - The work presents a new approach to the numerical solution of time-harmonic and time-dependent scattering problems. We replace Sommerfeld's radiation condition valid for the Helmholtz equation by a more general concept called pole condition. The pole condition is based on the Laplace transform of the exterior solution and allows a characterization of outgoing waves. Both new insight into the analysis of scattering problems as well as new numerical algorithms are obtained.
T3 - ZIB-Report - 02-45
KW - Pole condition
KW - Helmholtz equation
KW - Wide angle one-way equation
KW - Schroedinger equation
KW - Transparent boundary conditions
KW - Unbounded domains
KW - Fini
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7128
ER -
TY - GEN
A1 - Krumke, Sven
A1 - Rambau, Jörg
A1 - Torres, Luis Miguel
T1 - Online-Dispatching of Automobile Service Units
N2 - We present an online algorithm for a real-world vehicle dispatching problem at ADAC, the German Automobile Association.
T3 - ZIB-Report - 02-44
KW - vehicle dispatching
KW - soft time windows
KW - online
KW - real-time
KW - ADAC
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7117
ER -
TY - GEN
A1 - Hansmann, Sabine
A1 - Loesch, Sandra
A1 - Morstein, Gabriele
A1 - Müller, Werner
A1 - Müntner, Kathrin
A1 - Ristau, Ute
A1 - Rusch, Beate
A1 - Todt, Günter
A1 - Wagenknecht, Petra
T1 - Fremddatennutzung im KOBV: Eine Evaluation vom Mai / Juni 2002
N2 - Eine fremddatengestützte Katalogisierung bedeutet für die einzelne Bibliothek unbestritten eine Zeit- und Kostenersparnis. Dieser Report beleuchtet die unterschiedlichen Faktoren technischer und organisatorischer Natur, die die Fremddatennutzung in der dezentralen Struktur des Kooperativen Bibliotheksverbundes Berlin-Brandenburg (KOBV) beeinflussen. Die Ausführungen stützen sich im Wesentlichen auf eine Umfrage, die die Autoren im Mai / Juni 2002 unter KOBV-Mitgliedsbibliotheken zum Thema Fremddatennutzung durchgeführt haben. Dargelegt wird, wie komfortabel die in den KOBV-Bibliotheken eingesetzten Bibliotheksinformationssysteme eine fremddatengestützte Katalogisierung erlauben. Diskutiert wird zudem die Software ZACK, die sich als Alternative zu einem eigenen Z39.50-Client zur Datenübernahme anbietet. Erstmals seit Bestehen des Verbundes werden Zahlen veröffentlicht über den Anteil der Bibliotheken, die Fremddaten nutzen und denjenigen, die dieses Angebot nicht wahrnehmen. Dabei wird die Fremddatenutzung differenziert sowohl für den Bereich der Neuaufnahmen als auch für die Retrokatalogisierung. In der weiteren Analyse werden zusätzliche Aspekte betrachtet wie z.B. die verfügbaren bzw. gewünschten Datenbanken im Verhältnis zum sprachlichen Spektrum des erworbenen Katalogisierungsgutes. Eingegangen wird auch auf die von den Bibliotheken genannten Hauptproblemen und die gewünschten zusätzlichen Serviceleistungen auf Seiten der KOBV-Verbundzentrale. Als Ergebnis dieses Status-Quo-Berichts legt das Autorenteam eine Reihe von Empfehlungen vor, die darauf abzielen, auch für KOBV-Bibliotheken in Zukunft eine Fremddatennutzungsquote von 70 - 75 % zu erreichen.
T3 - ZIB-Report - 02-43
KW - KOBV
KW - Kooperativer Bibliotheksverbund Berlin-Brandenburg
KW - Bibliotheken
KW - Bibliotheksverbund
KW - Fremddaten
KW - Fremddatennutzung
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7104
ER -
TY - GEN
A1 - Erdmann, Bodo
A1 - Lang, Jens
A1 - Roitzsch, Rainer
T1 - KARDOS - User"s Guide
N2 - The adaptive finite element code {\sc Kardos} solves nonlinear parabolic systems of partial differential equations. It is applied to a wide range of problems from physics, chemistry, and engineering in one, two, or three space dimensions. The implementation is based on the programming language C. Adaptive finite element techniques are employed to provide solvers of optimal complexity. This implies a posteriori error estimation, local mesh refinement, and preconditioning of linear systems. Linearely implicit time integrators of {\em Rosenbrock} type allow for controlling the time steps adaptively and for solving nonlinear problems without using {\em Newton's} iterations. The program has proved to be robust and reliable. The user's guide explains all details a user of {\sc Kardos} has to consider: the description of the partial differential equations with their boundary and initial conditions, the triangulation of the domain, and the setting of parameters controlling the numerical algorithm. A couple of examples makes familiar to problems which were treated with {\sc Kardos}. We are extending this guide continuously. The latest version is available by network: {\begin{rawhtml} Downloads. \end{rawhtml}}
T3 - ZIB-Report - 02-42
KW - nonlinear parabolic systems
KW - Rosenbrock methods
KW - adaptivity in time and space
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7096
ER -
TY - GEN
A1 - Bley, Andreas
A1 - Koch, Thorsten
T1 - Integer programming approaches to access and backbone IP-network planning
N2 - In this article we study the problem of designing a nation-wide communication network. Such networks usually consist of an access layer, a backbone layer, and maybe several intermediate layers. The nodes of each layer must be connected to those of the next layer in a tree-like fashion. The backbone layer has to satisfy certain survivability and routing constraints. Given the node locations, the demands between them, the possible connections and hardware configurations, and various other technical and administrational constraints, the goal is to decide, which node is assigned to which network level, how the nodes are connected, what hardware must be installed, and how traffic is routed in the backbone. Mixed integer linear programming models and solution methods are presented for both the access and the backbone network design problem. The focus is on the design of IP-over-SDH networks, but the access network design model and large parts of the backbone network design models are general and also applicable for other types of communication networks. Results obtained with these methods in the planning of the German research network are presented.
T3 - ZIB-Report - 02-41
KW - Network design
KW - Traffic enineering
KW - Internet routing
KW - Mixed-integer programming
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7081
ER -
TY - GEN
A1 - Cordes, Frank
A1 - Weber, Marcus
A1 - Schmidt-Ehrenberg, Johannes
T1 - Metastable Conformations via successive Perron-Cluster Cluster Analysis of dihedrals
N2 - Decomposition of the high dimensional conformational space of bio-molecules into metastable subsets is used for data reduction of long molecular trajectories in order to facilitate chemical analysis and to improve convergence of simulations within these subsets. The metastability is identified by the Perron-cluster cluster analysis of a Markov process that generates the thermodynamic distribution. A necessary prerequisite of this analysis is the discretization of the conformational space. A combinatorial approach via discretization of each degree of freedom will end in the so called ''curse of dimension''. In the following paper we analyze Hybrid Monte Carlo simulations of small, drug-like biomolecules and focus on the dihedral degrees of freedom as indicators of conformational changes. To avoid the ''curse of dimension'', the projection of the underlying Markov operator on each dihedral is analyzed according to its metastability. In each decomposition step of a recursive procedure, those significant dihedrals, which indicate high metastability, are used for further decomposition. The procedure is introduced as part of a hierarchical protocol of simulations at different temperatures. The convergence of simulations within metastable subsets is used as an ''a posteriori'' criterion for a successful identification of metastability. All results are presented with the visualization program AmiraMol.
T3 - ZIB-Report - 02-40
KW - metastability
KW - Perron-Cluster Cluster Analysis
KW - curse of dimension
KW - Hybrid Monte Carlo
KW - significant dihedrals
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7074
ER -
TY - GEN
A1 - Grötschel, Martin
T1 - Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes
N2 - A subset ${\cal C}$ of the power set of a finite set $E$ is called cardinality homogeneous if, whenever ${\cal C}$ contains some set $F$, ${\cal C}$ contains all subsets of $E$ of cardinality $|F|$. Examples of such set systems ${\cal C}$ are the sets of circuits and the sets of cycles of uniform matroids and the sets of all even or of all odd cardinality subsets of $E$. With each cardinality homogeneous set system ${\cal C}$, we associate the polytope $P({\cal C})$, the convex hull of the incidence vectors of all sets in ${\cal C}$, and provide a complete and nonredundant linear description of $P({\cal C})$. We show that a greedy algorithm optimizes any linear function over $P({\cal C})$, give an explicit optimum solution of the dual linear program, and provide a polynomial time separation algorithm for the class of polytopes of type $P({\cal C})$.
T3 - ZIB-Report - 02-19
KW - Cycles in Matroids
KW - cardinality homogeneous set systems
KW - polytopes
KW - greedy algorithm
KW - polyhedral combinatorics
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6868
ER -
TY - GEN
A1 - Hoffmann, Hans Falk
A1 - Putzer, Alois
A1 - Reinefeld, Alexander
T1 - Vom World Wide Web zum World Wide Grid - Eine neue Informationsinfrastruktur für wissenschaftliche Anwendungen
N2 - In Analogie zu den Elektrizitätsnetzen electricity grid), von denen die technische Revolution ausging, wurde der Begriff Computational Grid (kurz Grid) geprägt. Ein wichtiger Bestandteil des Systems liegt im benutzerfreundlichen Zugang und der koordinierten Nutzung der weltweit verteilten Speicherressourcen und Rechnerkapazitäten. Bei der Entwicklung dazu notwendiger Technologien und Software (Middleware) profitiert man von Kenntnissen und Erfahrungen bei der Entwicklung verteilter Algorithmen, dem Software-Engineering und dem Supercomputing.
T3 - ZIB-Report - 02-39
KW - Grid-Computing
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7069
ER -
TY - GEN
A1 - Schlegel, Martin
A1 - Marquardt, Wolfgang
A1 - Ehrig, Rainald
A1 - Nowak, Ulrich
T1 - Sensitivity analysis of linearly-implicit differential-algebraic systems by one-step extrapolation
N2 - In this work we present an approach for the sensitivity analysis of linearly-implicit differential-algebraic equation systems. Solutions for both, states and sensitivities are obtained by applying an extrapolated linearly implicit Euler discretization scheme. This approach is compared to the widely used sensitivity extensions of multi-step BDF methods by means of case studies. Especially, we point out the benefit of this method in the context of dynamic optimization using the sequential approach.
T3 - ZIB-Report - 02-38
KW - sensitivity evaluation
KW - differential-algebraic systems
KW - extrapolation methods
KW - dynamic optimization
KW - optimal control
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7052
ER -
TY - GEN
A1 - Litsche, Stefan
A1 - Otto, Dagmar
T1 - Dynamisches Verlinken mit SFX und MetaLib
N2 - Zeitschriften und andere Medien werden in wachsendem Maße elektronisch publiziert. Hier entsteht für die Bibliotheken, welche diese Online-Publikationen ihren Lesern zur Verfügung stellen, ein neuer Bereich der Informationsvermittlung. Mit dem aufkommenden Standard der OpenURL ergeben sich neue Möglichkeiten, dem Benutzer weiterführende Links und Dienste anzubieten. Das Document-Linking-System SFX der Firma Ex Libris ist die erste und bekannteste Anwendung, die ein Managementsystem fr die Auswertung der OpenURL implementiert. Im Rahmen eines Projektes hat die Zentrale des Kooperativen Bibliotheksverbundes Berlin-Brandenburg (KOBV) eine Evaluation von SFX durchgeführt. Als Ergebnis der Evaluation sollten Einsatzmöglichkeiten von SFX für die KOBV-Suchmaschine und in den lokalen Bibliothekssystemen und Informationsportalen aufgezeigt werden. Im Verlauf des Projektes hat sich das Produkt SFX als eine stabile Anwendung erwiesen, die dem Benutzer interessante zusätzliche Dienste bieten kann.
T3 - ZIB-Report - 02-37
KW - Informationssysteme
KW - Dynamisches Verlinken
KW - OpenURL
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7045
ER -