Library

Description: 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.

Description: 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.

Description: 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} 〈A href="http://www.zib.de/Numerik/software/kardos/"〉 〈i〉 Downloads.〈/i〉〈/a〉 \end{rawhtml}}

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: The bio-heat transfer equation is a macroscopic model for describing the heat transfer in microvascular tissue. So far the deduction of the Helmholtz term in the bio-heat transfer equation is not co role. In view of a future numerical application of this new mathematical model to treatment planning in hyperthermia we derive asymptotic estimates for first and second order correctors.

Description: Mixed integer programs ($MIPs$) are commonly solved with branch and bound algorithms based on linear programming. The success and the speed of the algorithm strongly depends on the strategy used to select the branching variables. Today's state-of-the-art strategy is called \emph{pseudocost branching} and uses information of previous branchings to determine the current branching. We propose a modification of \emph{pseudocost branching} which we call \emph{history branching}. This strategy has been implemented in $SIP$, a state-of-the-art $MIP$ solver. We give computational results that show the superiority of the new strategy.

Description: We consider the design of transparent optical networks from a practical perspective. Network operators aim at satisfying the communication demands at minimum cost. Such an optimization involves three interdependent planning issues: the dimensioning of the physical topology, the routing of lightpaths, and the wavelength assignment. Further topics include the reliability of the configuration and sparse wavelength conversion for efficient use of the capacities. In this paper, we investigate this extensive optical network design task. Using a flexible device-based model, we present an integer programming formulation that supports greenfield planning as well as expansion planning on top of an existing network. As solution method, we propose a suitable decomposition approach that separates the wavelength assignment from the dimensioning and routing. Our method in particular provides a lower bound on the total cost which allows to rate the solution quality. Computational experiments on realistic networks approve the solution approach to be appropriate.

Description: Today's telecommunication networks are configured statically. Whenever a connection is established, the customer has permanent access to it. However, it is observed that usually the connection is not used continuously. At this point, dynamic provisioning could increase the utilization of network resources. WDM based Optical Transport Networks (OTNs) will shortly allow for fast dynamic network reconfiguration. This enables optical broadband leased line services on demand. Since service requests competing for network resources may lead to service blocking, it is vital to use appropriate strategies for routing and wavelength assignment in transparent optical networks. We simulate the service blocking probabilities of various dynamic algorithms for this problem using a well-founded traffic model for two realistic networks. One of the algorithms using shortest path routings performs best on all instances. Surprisingly, the tie-breaking rule between equally short paths in different wavelengths decides between success or failure.

Description: In the online traveling salesman problem $OLTSP$ requests for visits to cities arrive online while the salesman is traveling. We study the $F{\_max}-OLTSP$ where the objective is to minimize the maximum flow time. This objective is particularly interesting for applications. Unfortunately, there can be no competitive algorithm, neither deterministic nor randomized. Hence, competitive analysis fails to distinguish online algorithms. Not even resource augmentation which is helpful in scheduling works as a remedy. This unsatisfactory situation motivates the search for alternative analysis methods. We introduce a natural restriction on the adversary for the $F{\_max}-OLTSP$ on the real line. A \emph{non-abusive adversary} may only move in a direction if there are yet unserved requests on this side. Our main result is an algorithm which achieves a constant competitive ratio against the non-abusive adversary.

Description: 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.

Description: 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.

Description: 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}.

Description: 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.

Description: 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.

Description: 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.

Description: The paper deals with three different Newton algorithms that have recently been worked out in the general frame of affine invariance. Of particular interest is their performance in the numerical solution of discretized boundary value problems (BVPs) for nonlinear partial differential equations (PDEs). Exact Newton methods, where the arising linear systems are solved by direct elimination, and inexact Newton methods, where an inner iteration is used instead, are synoptically presented, both in affine invariant convergence theory and in numerical experiments. The three types of algorithms are: (a) affine covariant (formerly just called affine invariant) Newton algorithms, oriented toward the iterative errors, (b) affine contravariant Newton algorithms, based on iterative residual norms, and (c) affine conjugate Newton algorithms for convex optimization problems and discrete nonlinear elliptic PDEs.

Description: 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.

Description: We present an online algorithm for a real-world vehicle dispatching problem at ADAC, the German Automobile Association.

Description: 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.

Description: 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.

Description: 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.

Description: 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?

Description: \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.

Description: \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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: 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.

Description: A beautiful result of Brö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$.

Description: 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.

Description: 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.

Description: 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ü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.

Description: 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.

Description: 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})$.

Description: 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.

Description: 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.

Description: The aim of this paper is to develop fast methods for the solution of nonlinear Schrö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.

Description: 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.

Description: One important step in the fabrication of silicon-based integrated circuits is the creation of semiconducting areas by diffusion of dopant impurities into silicon. Complex models have been developed to investigate the redistribution of dopants and point defects. In general, numerical analysis of the resulting PDEs is the central tool to assess the modelling process. We present an adaptive approach which is able to judge the quality of the numerical approximation and which provides an automatic mesh improvement. Using linearly implicit methods in time and multilevel finite elements in space, we are able to integrate efficiently the arising reaction-drift-diffusion equations with high accuracy. Two different diffusion processes of practical interest are simulated.

Description: Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. By determining almost invariant sets of the associated Markov operator, the Monte Carlo sampling splits by a hierarchical annealing process into the essential regions of the state space; therefore UCMC aims at avoiding the typical metastable behavior of Monte Carlo techniques. From the viewpoint of Monte Carlo, a slowly converging long-time Markov chain is replaced by a limited number of rapidly mixing short-time ones. The correct weighting factors for the various Markov chains are obtained via a coupling matrix, that connects the samplings from the different almost invariant sets. The underlying mathematical structure of this approach is given by a general examination of the uncoupling-coupling procedure. Furthermore, the overall algorithmic scheme of UCMC is applied to the $n$-pentane molecule, a well-known example from molecular dynamics.

Description: The traveling repairman problem (TRP) is a variant of the famous traveling salesman problem (TSP). The objective for the TRP is to minimize the latency, that is the the weighted sum of completion times of the cities, where the completion time of a city is defined to be the time in the tour before the city is reached. In the online traveling repairman problem (OLTRP) requests for visits to cities (points in a metric space) arrive online while the repairman is traveling. We analyze the performance of algorithms using competitive analysis, where the cost of an online algorithm is compared to that of an optimal offline algorithm. An optimal offline algorithm knows the entire request sequence in advance and can serve it with minimum cost. Recently, Feuerstein and Stougie presented a $9$-competitive algorithm for the OLTRP on the real line. In this paper we show how to use techniques from online-scheduling to obtain an $8$-competitive deterministic algorithm which works for any metric space. We also present a randomized algorithm which has a competitive ratio of $\frac{4}{\ln 2}\approx 5.7708$ against an oblivious adversary. All of our results also hold for the ``dial-a-ride'' generalization of the OLTRP, where objects have to be picked up and delivered by a server.

Description: In the online traveling salesman problem requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman which finishes as early as possible. Performance of algorithms is measured through their competitive ratio, comparing the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline solution. Objections against such omnipotent adversaries have lead us to devise an adversary that is in a natural way, in the context of routing problems, more restricted in power. For the exposition we consider the online traveling salesman problem on the metric space given by the non-negative part of the real line. We show that a very natural strategy is~$3/2$-competitive against the conventional adversary, which matches the lower bound on competitive ratios achievable for algorithms for this problem. Against the more ``\emph{fair adversary}'', that we propose, we show that there exists an algorithm with competitive ratio $\frac{1+\sqrt{17}}{4}\approx 1.28$ and provide a matching lower bound. We also show competitiveness results for a special class of algorithms (called zealous algorithms) that do not allow waiting time for the server as long as there are requests unserved.

Description: Regional hyperthermia, a clinical cancer therapy, is the main topic of the Sonderforschungsbereich Hyperthermia: Scientific Methods and Clinical Applications'' at Berlin. In recent years, technological improvements towards a better concentration of heat to the desired target region have been achieved. These include a rather sophisticated integrated software environment for therapy planning and a new hyperthermia applicator. In a next step, a detailed closed loop monitoring of the actual treatment is to be developed. For this purpose the hyperthermia applicator is combined with an MRI system, which will allow to check the positioning of the patients and to measure individual blood perfusion as well as the 3D temperature distribution. The measurements will then be employed for an on-line control of the whole treatment. In this intended setting, new fast feedback control algorithms will come into play.

Description: In this paper for the $M(n)/M(n)/s+GI$ system, i.e.\ for a $s$-server queueing system where the calls in the queue may leave the system due to impatience, we present new asymptotic results for the intensities of calls leaving the system due to impatience and a Markovian system approximation where these results are applied. Furthermore, we present a new proof for the formulae of the conditional density of the virtual waiting time distributions, recently given by Movaghar for the less general $M(n)/M/s+GI$ system. Also we obtain new explicit expressions for refined virtual waiting time characteristics as a byproduct.

Description: Several practical instances of network design problems require the network to satisfy multiple constraints. In this paper, we address the \emph{Budget Constrained Connected Median Problem}: We are given an undirected graph $G = (V,E)$ with two different edge-weight functions $c$ (modeling the construction or communication cost) and $d$ (modeling the service distance), and a bound~$B$ on the total service distance. The goal is to find a subtree~$T$ of $G$ with minimum $c$-cost $c(T)$ subject to the constraint that the sum of the service distances of all the remaining nodes $v \in V\setminus T$ to their closest neighbor in~$T$ does not exceed the specified budget~$B$. This problem has applications in optical network design and the efficient maintenance of distributed databases. We formulate this problem as bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem that demonstrate that our performance ratios are close to best possible

Description: Network loading problems occur in the design of telecommunication networks, in many different settings. The polyhedral structure of this problem is important in developing solution methods for the problem. In this paper we investigate the polytope of the problem restricted to one edge of the network (the edge capacity problem). We describe classes of strong valid inequalities for the edge capacity polytope, and we derive conditions under which these constraints define facets. As the edge capacity problem is a relaxation of the network loading problem, their polytopes are intimately related. We, therefore, also give conditions under which the inequalities of the edge capacity polytope define facets of the network loading polytope. Furthermore, some structural properties are derived, such as the relation of the edge capacity polytope to the knapsack polytope. We conclude the theoretical part of this paper with some lifting theorems, where we show that this problem is polynomially solvable for most of our classes of valid inequalities. In a computational study the quality of the constraints is investigated. Here, we show that the valid inequalities of the edge capacity polytope are not only important for solving the edge capacity problem, but also for the network loading problem, showing that the edge capacity problem is an important subproblem.

Description: The improvement of simulations of QCD with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering is studied on $10^4$ and $12^4$ lattices. As an indicator for decorrelation the topological charge is used.

Description: In this paper we describe the results of a computational study towards the (re)optimization of signaling transfer points (STPs) in telecommunication networks. The best performance of an STP is achieved whenever the traffic load is evenly distributed among the internal components. Due to the continuously changing traffic pattern, the load of the components has to be re-optimized on a regular basis. Besides the balancing objective also the number of rearrangements have to be taken into account. In this paper we present two alternative formulations to deal with both requirements. Computational results show that for both formulations (near) optimal solutions can be obtained within reasonable time limits.

Description: The structures and interaction energies of guanine and uracil quartets have been determined by B3LYP hybrid density functional calculations. The total interaction energy $\Delta$E$^{T}$ of the $\it{C}$$_{4h}$-symmetric guanine quartet consisting of Hoogsteen type base pairs with two hydrogen bonds between two neighbour bases is -66.07 kcal/mol at the highest level. The uracil quartet with C6-H6...O4 interactions between the individual bases has only a small interaction energy of -20.92 kcal/mol and the interaction energy of -24.63 kcal/mol for the alternative structure with N3-H3...O4 hydrogen bonds is only slightly more negative. Cooperative effects contribute between 10 and 25 \% to all interaction energies. Complexes of metal ions with G-quartets can be classified into different structure types. The one with Ca$^{2+}$ in the central cavity adopts a $\it{C}$$_{4h}$-symmetric structure with coplanar bases, whereas the energies of the planar and non-planar Na$^{+}$ complexes are almost identical. The small ions Li$^{+}$, Be$^{2+}$, Cu$^{+}$ and Zn$^{2+}$ prefer a non-planar $\it{S}$$_{4}$-symmetric structure. The lack of co-planarity prevents probably a stacking of these base quartets. The central cavity is too small for K$^{+}$ ions and therefore this ion favours in contrast to all other investigated ions a $\it{C}$$_{4}$-symmetric complex, which is 4.73 kcal/mol more stable than the $\it{C}$$_{4h}$-symmetric one. The distance 1.665 {\AA} between K$^{+}$ and the root mean squares plane of the guanine bases is approximately half of the distance between two stacked G-quartets. The total interaction energy of alkaline earth ion complexes exceeds the ones with alkali ions. Within both groups of ions the interaction energy decreases with an increasing row position in the periodic table. The B3LYP and BLYP methods lead to similar structures and energies. Both methods are suitable for hydrogen-bonded biological systems. Compared with the before mentioned methods the HCTH functional leads to longer hydrogen bonds and different relative energies for two U-quartets. Finally we calculated also structures and relative energies with the MMFF94 forcefield. Contrary to all DFT methods, MMFF94 predicts bifurcated C-H...O contacts in the uracil quartet. In the G-quartet the MMFF94 hydrogen bond distances N2-H22...N7 are shorter than the DFT distances, whereas the N1-H1...O6 distances are longer.

Description: Pyridinochelin, a novel catecholate type siderophore, has been designed on the basis of the active analog enterobactin. Growth promotion tests indicate that this synthetic siderophore feeds various pathogenic bacteria effectively with iron even though it lacks one catecholate group compared to enterobactin. The superposition of the siderophore structures suggests that the structure of the skeleton connecting the catecholate groups might be an important factor for the iron transport.

Description: Dynamical process simulation of complex real-life problems often requires the use of modern algorithms, which automatically adapt both the time and space discretization in order to get error-controlled approximations of the solution. In this paper, a combination of linearly implicit time integrators of Rosenbrock type and adaptive multilevel finite elements based on a posteriori error estimates is presented. This approach has proven to work quite satisfactorily for a wide range of challenging practical problems. We show the performance of our adaptive method for two applications that arise in the study of flame balls and brine transport in porous media.

Description: The statistical behavior of deterministic and stochastic dynamical systems may be described using transfer operators, which generalize the notion of Frobenius Perron and Koopman operators. Since numerical techniques to analyze dynamical systems based on eigenvalues problems for the corresponding transfer operator have emerged, bounds on its essential spectral radius became of interest. This article shows that they are also of great theoretical interest. We give an analytical representation of the essential spectral radius in $L^{1}\!(\mu)$, which then is exploited to analyze the asymptotical properties of transfer operators by combining results from functional analysis, Markov operators and Markov chain theory. In particular, it is shown, that an essential spectral radius less than $1$, constrictiveness and some weak form'' of the so--called Doeblin condition are equivalent. Finally, we apply the results to study three main problem classes: deterministic systems, stochastically perturbed deterministic systems and stochastic systems.

Description: We focus on two new types of extremal graphs with respect to perfectness: critically and anticritically perfect graphs that lose their perfectness by simply deleting and adding an arbitrary edge, respectively. We present examples and study properties in order to compare critically and anticritically perfect graphs with minimally imperfect graphs, another type of extremal graphs with respect to perfectness. We discuss two attempts to characterize the classes of all critically and anticritically perfect graphs and give a brief overview on classes of perfect graphs which contain critically or anticritically perfect graphs.

Description: A path following algorithm for linear complementarity problems is presented. Given a point $z$ that approximates a point $z(\tau)$ on the central path with complementarity gap $\tau$, one determines a parameter $\theta\in (0,1)$ so that this point satisfies the hypothesis of the affine invariant Kantorovich Theorem for the equation defining $z((1-\theta)\tau)$. It is shown that $\theta$ is bounded below by a multiple of $n^{-1/2}$, where $n$ is the dimension of the problem. Since the hypothesis of of the Kantorovich Theorem is satisfied the sequence generated by Newton's method, or by the simplified Newton method, will converge to $z((1-\theta)\tau)$. We show that the number of steps required to obtain an acceptable approximation of $z((1-\theta)\tau)$ is bounded above by a number independent of $n$. Therefore the algorithm has $O(\sqrt{n}L)$-iteration complexity. The parameters of the algorithm can be determined in such a way that only one Newton step is needed each time the complementarity gap is decreased.

Description: The polynomial differential system modelling the behavior of a chemical reaction is given by graphtheoretic structures. The concepts from toric geometry are applied to study the steady states and stable steady states. Deformed toric varieties give some insight and enable graph theoretic interpretations. The importance of the circuits in the directed graph are emphazised. The counting of positive solutions of a sparse polynomial system by B.\ Sturmfels is generalized to the counting of stable positive solutions in case of a polynomial differential equation. The generalization is based on a method by sparse resultants to detect whether a system may have a Hopf bifurcation. Special examples from chemistry are used to illustrate the theoretical results.

Description: The increasing demand for distributed solutions in computing technology does not stop when it comes to visualization techniques. However, the capabilities of todays applications to perform remote rendering are limited by historical design legacys. Especially the popular X11 protokoll, which has been proven to be extremely flexible and usefull for remote 2D graphics applications, breaks down for the case of remote 3D rendering. In this white paper, we give a short overview of generic remote rendering technologies available today, and compare their performance to the recently released vizserver by SGI: a network extension to the SGI OpenGL rendering engines.

Description: This book offers a self-contained introduction to the field of semidefinite programming, its applications in combinatorial optimization, and its computational methods. We equip the reader with the basic results from linear algebra on positive semidefinite matrices and the cone spanned by them. Starting from linear programming, we introduce semidefinite programs and discuss the associated duality theory. We then turn to semidefinite relaxations of combinatorial optimization and illustrate their interrelation. In the second half we deal with computational methods for solving semidefinite programs. First, the interior point approach, its iteration complexity, and implementational issues are discussed. Next, we explain in great detail the spectral bundle method, which is particularly suited for large scale semidefinite programming. One of the most successful techniques in integer linear programming is the cutting plane approach which improves an initial relaxation by adding violated inequalities. We explore possibilities to combine the two solution methods with the cutting plane approach in order to strengthen semidefinite relaxations of combinatorial optimization problems.

Description: \texttt{SBmethod}, Version 1.1, is an implementation of the spectral bundle method for eigenvalue optimization problems of the form \begin{displaymath} \min_{y\in \mathbf{R}^m}\;\; a\;\lambda_{\max}(C-\sum_{i=1}^{m} A_i y_i)+b^Ty. \end{displaymath} The design variables $y_i$ may be sign constrained, $C$ and and $A_i$ are given real symmetric matrices, $b\in\mathbf{R}^m$ allows to specify a linear cost term, and $a〉0$ is a constant multiplier for the maximum eigenvalue function $\lambda_{\max}(\cdot)$. The code is intended for large scale problems and allows to exploit structural properties of the matrices such as sparsity and low rank structure. The manual contains instructions for installation and use of the program. It describes in detail input format, options, and output. The meaning of the variables and parameters is made precise by relating them to a mathematical description of the algorithm in pseudocode.

Description: In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets. For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined. The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks.

Description: In this paper we present the {\em SteinLib}, a library of data sets for the Steiner tree problem in graphs. This library extends former libraries on Steiner tree problems by many new interesting and difficult instances, most of them arising from real-world applications. We give a survey on the difficulty of these problem instances by giving references to state-of-the-art software packages that were the first or are currently among the best to solve these instances.

Description: Workstation clusters are often not only used for high-throughput computing in time-sharing mode but also for running complex parallel jobs in space-sharing mode. This poses several difficulties to the resource management system, which must be able to reserve computing resources for exclusive use and also to determine an optimal process mapping for a given system topology. On the basis of our CCS software, we describe the anatomy of a modern resource management system. Like Codine, Condor, and LSF, CCS provides mechanisms for the user-friendly system access and management of clusters. But unlike them, CCS is targeted at the effective support of space-sharing parallel and even metacomputers. Among other features, CCS provides a versatile resource description facility, topology-based process mapping, pluggable schedulers, and hooks to metacomputer management.

Description: Interior point methods for multistage stochastic programs involve KKT systems with a characteristic global block structure induced by dynamic equations on the scenario tree. We generalize the recursive solution algorithm proposed in an earlier paper so that its linear complexity extends to a refined tree-sparse KKT structure. Then we analyze how the block operations can be specialized to take advantage of problem-specific sparse substructures. Savings of memory and operations for a financial engineering application are discussed in detail.

Description: The present paper aims at an extension of {\sc Kohonen's} Self-Organizing Map (SOM) algorithm to be called Self-Organizing Box Map (SOBM) algorithm; it generates box codebooks in lieu of point codebooks. Box codebooks just like point codebooks indirectly define a Voronoi tessellation of the input space, so that each codebook vector represents a unique set of points. Each box codebook vector comprises a multi-dimensional interval that approximates the related partition of the Voronoi tessellation. Upon using the automated cluster identification method that has recently been developed by the authors, the codebook vectors can be grouped in such a way that each group represents a point cluster in the input space. Since the clustering usually depends on the size of the SOM, one cannot be sure, whether the clustering comes out to be optimal. Refinement of part of the identified clusters would often improve the results. This paper presents the concept of an adaptive multilevel cluster algorithm that performs such refinements automatically. Moreover the paper introduces a concept of essential dimensions and suggests a method for their identification based on our herein suggested box codebooks. Applications of the algorithm to molecular dynamics will be described in a forthcoming paper.

Description: This paper addresses the problem of designing a minimum cost network whose capacities are sufficiently large to allow a feasible routing of a given set of multicast commodities. A multicast commodity consists of a set of two or mo re terminals that need to be connected by a so called broadcast tree, which consumes on all of its edges a capacity as large as the demand value associated with that commodity. We model the network design problem with multicast commodities as the problem of packing capacitated Steiner trees in a graph. In the first part of the paper we present three mixed-integer programming formulations for this problem. The first natural formulation uses only one integer capacity variable for each edge and and one binary tree variable for each commodity-edge pair. Applying well-known techniques from the Steiner tree problem, we then develop a stronger directed and a multicommodity flow based mixed-integer programming formulation. In the second part of the paper we study the associated polyhedra and derive valid and even facet defining inequalities for the natural formulation. Finally, we describe separation algorithms for these inequalities and present computational results that demonstrate the strength of our extended formulations.

Description: We present visualizations of recent supercomputer simulations from numerical relativity, exploiting the progress in visualization techniques and numerical methods also from an artistic point of view. The sequences have been compiled into a video tape, showing colliding black holes, orbiting and merging neutron stars as well as collapsing gravitational waves. In this paper we give some background information and provide a glance at the presented sequences.

Description: An algorithm is described to decide if a given polynomial differential expression $\Delta$ of multivariate functions is exact, i.e. whether there exists a first integral $P$ such that $D_xP = \Delta$ for any one of a set of variables $x$ and to provide the integral $P$. A generalization is given to allow integration in the case that the exactness is prohibited by terms which contain only functions of not all the independent variables.

Description: We present a fully second order projection method for the simulation of two-phase incompressible flow with surface tension. The Navier-Stokes equations are solved with a projection method on a fixed Cartesian grid. The free interface between the two fluids is tracked with a level set approach. The conditions at the interface for the pressure, the pressure gradient, and the velocity are explicitly incorporated into the scheme leading to a sharp representation of the pressure discontinuity and the interfacial force. The scheme in the presented form does not introduce additional points in the standard finite difference stencils. Computational results are compared with analytic solutions for a static round bubble, damped surface waves, and Rayleigh-Taylor instabilities.

Description: HyperPlan is a software system for performing 3D-simulations and treatment planning in regional hyperthermia. It allows the user to understand the complex effects of electromagnetic wave propagation and heat transport inside a patient's body. Optimized power amplitudes and phase settings can be calculated for the BSD radiowave applicators Sigma 60 and Sigma 2000 (eye-applicator). HyperPlan is built on top of the modular, object-oriented visualization system Amira. This system already contains powerful algorithms for image processing, geometric modelling and 3D graphics display. HyperPlan provides a number of hyperthermia-specific modules, allowing the user to create 3D tetrahedral patient models suitable for treatment planning. In addition, all numerical simulation modules required for hyperthermia simulation are part of HyperPlan. This guide provides a step-by-step introduction to hyperthermia planning using HyperPlan. It also describes the usage of the underlying visualization system Amira.

Description: In this paper we investigate the effects of the three-dimensional arrangement of antennas and frequency on temperature distributions that can be achieved in regional hyperthermia using an electromagnetic phased array. We compare the results of power-based and temperature-based optimization. Thus we are able to explain the discrepancies between previous studies favouring more antenna rings on the one hand and more antennas per ring on the other hand. We analyze the sensitivity of the results with respect to changes in amplitudes and phases as well as patient position. This analysis can be used for different purposes. First, it provides additional criteria for selecting the optimal frequency. Second, it can be used for specifying the required phase and amplitude accuracy for a real phased array system. Furthermore, it may serve as a basis for technological developments in order to reduce both types of sensitivities described above.

Description: All triangulations of euclidean oriented matroids are of the same PL-homeomorphism type by a result of Anderson. That means all triangulations of euclidean acyclic oriented matroids are PL-homeomorphic to PL-balls and that all triangulations of totally cyclic oriented matroids are PL-homeomorphic to PL-spheres. For non-euclidean oriented matroids this question is wide open. One key point in the proof of Anderson is the following fact: for every triangulation of a euclidean oriented matroid the adjacency graph of the set of all simplices ``intersecting'' a segment $[p_-p_+]$ is a path. We call this graph the $[p_-p_+]$-adjacency graph of the triangulation. While we cannot solve the problem of the topological type of triangulations of general oriented matroids we show in this note that for every circuit admissible triangulation of an arbitrary oriented matroid the $[p_-p_+]$-adjacency graph is a path.

Description: We call an edge $e$ of a perfect graph $G$ critical if $G-e$ is imperfect and say further that $e$ is anticritical with respect to the complementary graph $\overline G$. We ask in which perfect graphs critical and anticritical edges occur and how to find critical and anticritical edges in perfect graphs. Finally, we study whether we can order the edges of certain perfect graphs such that deleting all the edges yields a sequence of perfect graphs ending up with a stable set.

Description: We introduce a new method for reconstructing a triangular surface from an unorganized set of points in space. It is based on placing a probe sphere on the point set and rolling it around, connecting all triples of points with a triangle that the sphere comes to rest on. Therefore, the algorithm interpolates, rather than approximates, the input points. The method needs considerably less running time than previous algorithms and yields good results on point sets that are reasonably well-behaved.

Description: This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are $T$-coloring and list coloring. To model all the subtleties, the techniques of integer programming have proven to be very useful. The ability to produce good frequency plans in practice is essential for the quality of mobile phone networks. The present algorithmic solution methods employ variants of some of the traditional coloring heuristics as well as more sophisticated machinery from mathematical programming. This paper will also address this issue. Finally, this paper discusses several practical frequency assignment problems in detail, states the associated mathematical models, and also points to public electronic libraries of frequency assignment problems from practice. The associated graphs have up to several thousand nodes and range from rather sparse to almost complete.

Description: We present results on light hadron masses from simulations of full QCD and report on experiences in running such simulations on a Hitachi SR8000-F1 supercomputer.

Description: As has been shown recently, the identification of metastable chemical conformations leads to a Perron cluster eigenvalue problem for a reversible Markov operator. Naive discretization of this operator would suffer from combinatorial explosion. As a first remedy, a pre-identification of essential degrees of freedom out of the set of torsion angles had been applied up to now. The present paper suggests a different approach based on neural networks: its idea is to discretize the Markov operator via self-organizing (box) maps. The thus obtained box discretization then serves as a prerequisite for the subsequent Perron cluster analysis. Moreover, this approach also permits exploitation of additional structure within embedded simulations. As it turns out, the new method is fully automatic and efficient also in the treatment of biomolecules. This is exemplified by numerical results.

Description: In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most $C$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation.

Description: An affine invariant convergence analysis for inexact augmented Lagrangian-SQP methods is presented. The theory is used for the construction of an accuracy matching between iteration errors and truncation errors, which arise from the inexact linear system solves. The theoretical investigations are illustrated numerically by an optimal control problem for the Burgers equation.

Description: We establish the relationship between the transparent boundary condition (BPP) of Baskakov and Popov [Wave Motion 14 (1991) 121-128] and Pakpadakis et. al. [J. Acoust. Soc. Am. 92 (1992) 2030-2038] and a second boundary condition (SDY) introduced by Schmidt and Deuflhard [Comp. Math. Appl. 29 (1995) 53-76] and Schmidt and Yevick [J. Compu. Phys. 134 (1997) 96-107], that is explicitly tailored to the form of the underlying numerical propagation scheme. Our analysis demonstrates that if the domain is first discretized in the propagation direction, the SDY expression can be obtained by applying the exact sequence of steps used to derive the BPP procedure. The BPP method is thus an approximate realization of the computationally far simpler and unconditionally stable SDY boundary condition.

Description: We derive exact discrete nonreflecting boundary conditions for time-harmonic scattering problems modeled by the Helmholtz equation. The main idea is to consider the exterior problem as an initial value problem with initial data given on the boundary of the computational domain. The solution of the exterior problem is obtained via Laplace transformation techniques which supply the boundary conditions in terms of discrete Dirichlet-to-Neumann operators.

Description: This paper has been motivated by the need for a fast robust adaptive multigrid method to solve the vectorial Maxwell eigenvalue problem arising from the design of optical chips. Our nonlinear multigrid methods are based on a previous method for the scalar Helmholtz equation, which must be modified to cope with the null space of the Maxwell operator due to the divergence condition. We present two different approaches. First, we present a multigrid algorithm based on an edge element discretization of time-harmonic Maxwell's equations, including the divergence condition. Second, an explicit elimination of longitudinal magnetic components leads to a nodal discretization known to avoid discrete \emph{spurious modes} also and a vectorial eigenvalue problem, for which we present a multigrid solver. Numerical examples show that the edge element discretization clearly outperforms the nodal element approach.