TY - GEN
A1 - Grötschel, Martin
T1 - Frequency Assignment in Mobile Phone Systems
N2 - Wireless communication networks employ radio frequencies to establish communication links. The available radio spectrum is very limited. To meet today's radio communication demand, this resource has to be administered and reused carefully in order to control mutual interference. The reuse can be organized via separation in space, time, or frequency, for example. The problem, therefore, arises to distribute frequencies to links in a ``reasonable manner''. This is the basic form of the frequency assignment problem. What ``reasonable'' means, how to quantify this measure of quality, which technical side constraints to consider cannot be answered in general. The exact specification of this task and its mathematical model depend heavily on the particular application considered. In this paper we discuss this issue with respect to the GSM standard for mobile communication.
T3 - ZIB-Report - 00-58
KW - frequency assignment
KW - telecommunication
KW - mobile phone
KW - integer programming
KW - coloring
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6265
ER -
TY - GEN
A1 - Hohage, Thorsten
A1 - Schmidt, Frank
A1 - Zschiedrich, Lin
T1 - Solving time-harmonic scattering problems based on the condition: Theory
N2 - The pole condition is a general concept for the theoretical analysis and the numerical solution of a variety of wave propagation problems. It says that the Laplace transform of the physical solution in radial direction has no poles in the lower complex half-plane. In the present paper we show that for the Helmholtz equation with a radially symmetric potential the pole condition is equivalent to Sommerfeld's radiation condition. Moreover, a new representation formula based on the pole condition is derived and used to prove existence, uniqueness and asymptotic properties of solutions. This lays the foundations of a promising new algorithm to solve time-harmonic scattering problems numerically and provides a new approach for analyzing existing algorithms such as the Perfectly Matched Layer (PML) method and the Bayliss-Gunzburger-Turkel (BGT) algorithm.
T3 - ZIB-Report - 01-01
KW - transparent boundary conditions
KW - Laplace transform
KW - Sommerfeld radiation condition
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6279
ER -
TY - GEN
A1 - Borndörfer, Ralf
A1 - Grötschel, Martin
A1 - Löbel, Andreas
T1 - Duty Scheduling in Public Transit
N2 - This article is about \emph{adaptive column generation techniques} for the solution of duty scheduling problems in public transit. The current optimization status is exploited in an adaptive approach to guide the subroutines for duty generation, LP resolution, and schedule construction toward relevant parts of a large problem. Computational results for three European scenarios are reported.
T3 - ZIB-Report - 01-02
KW - Duty Scheduling
KW - Constraint Shortest Paths Problem
KW - Column Generation
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6286
ER -
TY - GEN
A1 - Fischer, Alexander
A1 - Schütte, Christof
A1 - Deuflhard, Peter
A1 - Cordes, Frank
T1 - Hierarchical Uncoupling-Coupling of Metastable Conformations
N2 - Uncoupling-coupling Monte Carlo (UCMC) combines uncoupling techniques for finite Markov chains with Markov chain Monte Carlo methodology. UCMC aims at avoiding the typical metastable or trapping behavior of Monte Carlo techniques. From the viewpoint of Monte Carlo, a slowly converging long-time Markov chain is replaced by a limited number of rapidly mixing short-time ones. Therefore, the state space of the chain has to be hierarchically decomposed into its metastable conformations. This is done by means of combining the technique of conformation analysis as recently introduced by the authors, and appropriate annealing strategies. We present a detailed examination of the uncoupling-coupling procedure which uncovers its theoretical background, and illustrates the hierarchical algorithmic approach. Furthermore, application of the UCMC algorithm to the $n$-pentane molecule allows us to discuss the effect of its crucial steps in a typical molecular scenario.
T3 - ZIB-Report - 01-03
KW - almost invariant sets
KW - bridge sampling
KW - metastability
KW - hierarchical annealing
KW - hybrid Monte Carlo
KW - $n$-pentane molecule
KW - ratio of normalizing co
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6296
ER -
TY - GEN
A1 - Henrion, Rene
A1 - Li, Pu
A1 - Möller, Andris
A1 - Steinbach, Marc
A1 - Wendt, Moritz
A1 - Wozny, Günter
T1 - Stochastic Optimization for Operating Chemical Processes Under Uncertainty
N2 - Mathematical optimization techniques are on their way to becoming a standard tool in chemical process engineering. While such approaches are usually based on deterministic models, uncertainties such as external disturbances play a significant role in many real-life applications. The present article gives an introduction to practical issues of process operation and to basic mathematical concepts required for the explicit treatment of uncertainties by stochastic optimization.
T3 - ZIB-Report - 01-04
KW - Uncertainty
KW - Chemical Processes
KW - Multistage Stochastic Programs
KW - Probabilistic Constraints
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6304
ER -
TY - GEN
A1 - Ehrig, Rainald
A1 - Ofenloch, Oliver
A1 - Schaber, Karlheinz
A1 - Deuflhard, Peter
T1 - Modelling and Simulation of Aerosol Formation by Heterogeneous Nucleation in Gas-Liquid Contact Devices
N2 - This paper describes a new simulation tool for the prediction of aerosol formation and behavior in gas--liquid contact devices such as absorbers, scrubbers, quench coolers, and condensers as well as multistage gas cleaning processes, respectively. Aerosol formation can impact severely the separation efficiency of gas cleaning processes. Aerosol or fog formation can arise by spontaneous condensation or desublimation in supersaturated gas phases. The rigorous description of the mass and energy transfer between the gas phase, the liquid phase, and the growing aerosol droplets leads to a system of partial differential and algebraic equations. For the solution of these systems we have developed the plant simulation tool AerCoDe. This program bases upon the linearly--implicit Euler discretisation, which in combination with extrapolation permits an adaptive step size and order control. Typical simulation results of a multistage industrial flue gas scrubbing process are presented. It is shown, that experimental data can be confirmed if the number concentration of condensation nuclei as an input parameter is roughly known.
T3 - ZIB-Report - 01-15
KW - aerosols
KW - heterogeneous nucleation
KW - two-phase flow
KW - balance equations
KW - extrapolation methods
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6416
ER -
TY - GEN
A1 - Grötschel, Martin
A1 - Krumke, Sven
A1 - Rambau, Jörg
A1 - Winter, Thomas
A1 - Zimmermann, Uwe
T1 - Combinatorial Online Optimization in Real Time
N2 - Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when decisions have to be made before all data of the problem are known. And we speak of a real-time online problem when online decisions have to be computed within very tight time bounds. This paper surveys the are of combinatorial online and real-time optimization, it discusses, in particular, the concepts with which online and real-time algorithms can be analyzed.
T3 - ZIB-Report - 01-16
KW - Online Optimization
KW - Realtime Optimization
KW - Competitive Analysis
KW - Heuristics
KW - Survey
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6424
ER -
TY - GEN
A1 - Grötschel, Martin
A1 - Krumke, Sven
A1 - Rambau, Jörg
T1 - Online Optimization of Complex Transportation Systems
N2 - This paper discusses online optimization of real-world transportation systems. We concentrate on transportation problems arising in production and manufacturing processes, in particular in company internal logistics. We describe basic techniques to design online optimization algorithms for such systems, but our main focus is decision support for the planner: which online algorithm is the most appropriate one in a particular setting? We show by means of several examples that traditional methods for the evaluation of online algorithms often do not suffice to judge the strengths and weaknesses of online algorithms. We present modifications of well-known evaluation techniques and some new methods, and we argue that the selection of an online algorithm to be employed in practice should be based on a sound combination of several theoretical and practical evaluation criteria, including simulation.
T3 - ZIB-Report - 01-17
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6438
ER -
TY - GEN
A1 - Wagler, Annegret
T1 - Rank-Perfect and Weakly Rank-Perfect Graphs
N2 - An edge of a perfect graph $G$ is critical if $G-e$ is imperfect. We would like to decide whether $G - e$ is still {\sl almost perfect} or already {\sl very imperfect}. Via relaxations of the stable set polytope of a graph, we define two superclasses of perfect graphs: rank-perfect and weakly rank-perfect graphs. Membership in those two classes indicates how far an imperfect graph is away from being perfect. We study the cases, when a critical edge is removed from the line graph of a bipartite graph or from the complement of such a graph.
T3 - ZIB-Report - 01-18
KW - perfect graphs
KW - rank-perfect graphs
KW - weakly rank-perfect graphs
KW - stable set polytope
KW - critical edges
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6448
ER -
TY - GEN
A1 - Jeltsch, Rolf
A1 - Strang, Gilbert
A1 - Deuflhard, Peter
T1 - First SIAM-EMS Conference "Applied Mathematics in our Changing World" Berlin 2001 - Collection of Abstracts
N2 - Collection of abstracts of the first SIAM-EMS conference Applied Mathematics in our Changing World'' in Berlin, September 2-6, 2001.
T3 - ZIB-Report - 01-19
KW - Abstracts
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6452
ER -
TY - GEN
A1 - Koch, Thorsten
T1 - ZIMPL User Guide
N2 - {\sc Zimpl} is a little language to translate the mathematical model of a problem into a linear or (mixed-)integer mathematical program expressed in {\tt lp} or {\tt mps} file format which can be read by a LP or MIP solver.
T3 - ZIB-Report - 01-20
KW - LP
KW - IP
KW - Modelling Language
KW - Integer Programming
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6466
ER -
TY - GEN
A1 - Otto, Dagmar
T1 - Informationsportale und Digitale Bibliotheken
N2 - Im ersten Teil des folgenden Aufsatzes werden allgemeine Überlegungen zur Entwicklung von Bibliotheken hin zu Informationsvermittlungsstellen für sowohl elektronische wie auch gedruckte Medien angestellt. Basierend auf den Ergebnissen der Evaluation digitaler Bibliotheken und Informationsportale in Deutschland wird ein erster Kriterienkatalog für ein Verbund-Informationsportal für den Kooperativen Bibliotheksverbund Berlin-Brandenburg entwickelt. Im Anhang befindet sich der Statusbericht über Informationsportale und digitale Bibliotheken in Deutschland. Dazu wurden sieben digitale Bibliotheken auf Verbundebene und 21 Bibliotheken nach Bundesländern evaluiert.
T3 - ZIB-Report - 01-21
KW - KOBV
KW - Kooperativer Bibliotheksverbund Berlin-Brandenburg
KW - Bibliotheksverbund
KW - Informationsportal
KW - Portal
KW - Digitale Bibliothek
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6479
ER -
TY - GEN
A1 - Krumke, Sven
A1 - Rambau, Jörg
A1 - Torres, Luis Miguel
T1 - Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows
N2 - Given a set of service requests (events), a set of guided servers (units), and a set of unguided service contractors (conts), the vehicle dispatching problem {\sl vdp} is the task to find an assignment of events to units and conts as well as tours for all units starting at their current positions and ending at their home positions (dispatch) such that the total cost of the dispatch is minimized. The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit costs consist of driving costs, service costs and overtime costs; cont costs consist of a fixed cost per service; event costs consist of late costs linear in the late time, which occur whenever the service of the event starts later than its deadline. The program \textsf{ZIBDIP} based on dynamic column generation and set partitioning yields solutions on heavy-load real-world instances (215 events, 95 units) in less than a minute that are no worse than 1\% from optimum on state-of-the-art personal computers.
T3 - ZIB-Report - 01-22
KW - vehicle dispatching
KW - soft time windows
KW - real-time
KW - column generation
KW - pricing
KW - branch and bound
KW - real world data
KW - ADAC
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6484
ER -
TY - GEN
A1 - Hohage, Thorsten
A1 - Schmidt, Frank
A1 - Zschiedrich, Lin
T1 - Solving time-harmonic scattering problems based on the pole condition: Convergence of the PML method
N2 - In this paper we study the PML method for Helmholtz-type scattering problems with radially symmetric potential. The PML method consists in surrounding the computational domain by a \textbf{P}erfectly \textbf{M}atched sponge \textbf{L}ayer. We prove that the approximate solution obtained by the PML method converges exponentially fast to the true solution in the computational domain as the thickness of the sponge layer tends to infinity. This is a generalization of results by Lassas and Somersalo based on boundary integral eqaution techniques. Here we use techniques based on the pole condition instead. This makes it possible to treat problems without an explicitly known fundamental solution.
T3 - ZIB-Report - 01-23
KW - transparent boundary conditions
KW - PML
KW - pole condition
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6494
ER -
TY - GEN
A1 - Steinbach, Marc
T1 - General Information Constraints in Stochastic Programs
N2 - Scenario tree models of stochastic programs arise naturally under standard nonanticipativity assumptions. We demonstrate how tree-sparse programs cover the general case, with \emph{arbitrary} information constraints. Detailed examples and intuitive interpretations illuminate the basic thoughts behind the abstract but elementary construction.
T3 - ZIB-Report - 01-24
KW - information constraints
KW - general nonanticipativity
KW - sigma-fields
KW - filtrations
KW - scenarios
KW - stochastic programs
KW - tree-sparse programs
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6502
ER -
TY - GEN
A1 - Garrido, Izaskun
A1 - Steinbach, Marc
T1 - A Multistage Stochastic Programming Approach in Real-Time Process Control
N2 - Standard model predictive control for real-time operation of industrial production processes may be inefficient in the presence of substantial uncertainties. To avoid overly conservative disturbance corrections while ensuring safe operation, random influences should be taken into account explicitly. We propose a multistage stochastic programming approach within the model predictive control framework and apply it to a distillation process with a feed tank buffering external sources. A preliminary comparison to a probabilistic constraints approach is given and first computational results for the distillation process are presented.
T3 - ZIB-Report - 01-05
KW - Process Control
KW - Real-Time Optimization
KW - Multistage Stochastic Programming
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6317
ER -
TY - GEN
A1 - Byun, Chul-Young
T1 - Lower Bounds for Large-Scale Set Partitioning Problems
N2 - In this work we concentrate on developing methods which determine good lower bounds for set partitioning problems (SPP) in an appropriate amount of time. We found out that it makes sense to use the Lagrangian relaxation method for this task. The Lagrangian relaxed problem of SPP has a simple structure, which leads to algorithms and heuristics, whose total complexity per iteration depends linearly on the number of non-zeros of the problem matrix of SPP. In contrast, other methods like simplex methods or interior point methods have a complexity of higher order. Because the problem matrices of our tested instances are sparse, the linear dependence becomes an advantage for the algorithms and heuristics mentioned above. As a reference for the state-of-the-art we have applied the dual simplex method and the barrier function method, implemented in CPLEX. The methods, which we have developed and compared with those of CPLEX, are SBM, CAM, CCBM, and CBM. SBM is a subgradient bundle method derived from the basic subgradient method, which is a global convergent method for determining the maximum of concave functions. CAM is a coordinate ascent method, where the convex coordinate bundle method CCBM and the coordinate bundle method CBM are derivatives from CAM. We observed that the basic subgradient and the coordinate ascent method are improved if bundling techniques can be used. But the motivation for bundling differs for both approaches. In the former case bundling helps to approximate a minimum norm subgradient, which provides a steepest ascent direction, in order to speed up the performance. In the latter case bundling enables proceeding along directions, which are not restricted on the coordinate directions. By this the performance is accelerated. Among all used techniques stabilization is worth mentioning. Stabilization improves the performance especially at the beginning by avoiding too big steps during the proceeding. This leads to a more stabilized progression. Stabilization was successfully applied to SBM, CAM, CCBM, and CBM. As an overall result we conclude the following: \begin{enumerate} \item CPLEX computes the optimal objective values, whereas SBM and CBM has on average a gap of under $1.5\%$. \item In comparison to CPLEX baropt, SBM, CAM, and CBM the algorithm CCBM has a slow convergence because of the convex combination of ascent coordinate directions. An alternative is to relax the convex combination to a simple sum of the corresponding directions. This idea is realized in CBM. \item If we focus on the running time rather than on optimality then CBM is on average the fastest algorithm. \end{enumerate} Note that methods like SBM or CBM are applied on static SPP instances in order to determine a good lower bound. For solving SPP we need dynamical methods. Due to the complex topic of dynamical methods we will not discuss them, but a certain technique is worth mentioning. It is called column generation. We have indicated that this technique needs good Lagrangian multipliers of the corresponding SPP instances in order to generate further columns (in our case duties), which are added to the current SPP instance. Those multipliers are by-products of methods like our six considered methods. Due to the large number of such generation steps the running time depends on the computation time of these methods. Therefore, CBM fits more to this technique than CPLEX baropt or SBM. To sum it up it can be said that applications such as a duty scheduling can be described as set partitioning problems, whose lower bound can be solved by simplex, interior points, subgradient, or coordinate ascent methods. It turns out that the interior points method CPLEX baropt and the heuristic CBM have good performances. Furthermore, good Lagrangian multipliers, which are by-products of these methods, can be used by techniques like column generation. For this particular technique it also turns out that among our tested algorithms CBM is the most efficient one. In general we can state that real-world applications, which have to solve a large number of Lagrangian relaxed SPP instances can improve their performance by using CBM.
T3 - ZIB-Report - 01-06
KW - Set Partitioning
KW - Lagrangean Relaxation
KW - Dual Ascent
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6321
ER -
TY - GEN
A1 - Krumke, Sven
A1 - Paepe, Willem de
A1 - Rambau, Jörg
A1 - Stougie, Leen
T1 - Online Bin-Coloring
N2 - We introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly enviroment. The bin coloring problem is to pack unit size colored items into bins, such that the maximum number of different colors per bin is minimized. Each bin has size~$B\in\mathbb{N}$. The packing process is subject to the constraint that at any moment in time at most $q\in\mathbb{N}$ bins may be partially filled. Moreover, bins may only be closed if they are filled completely. An online algorithm must pack each item must be packed without knowledge of any future items. We investigate the existence of competitive online algorithms for the online uniform binpacking problem. We show upper bounds for the bin coloring problem. We prove an upper bound of $3q$ - 1 and a lower bound of $2q$ for the competitive ratio of a natural greedy-type algorithm, and show that surprisingly a trivial algorithm which uses only one open bin has a strictly better competitive ratio of $2q$ - 1. Morever, we show that any deterministic algorithm has a competitive ratio $\Omega (q)$ and that randomization does not improve this lower bound even when the adversary is oblivious.
T3 - ZIB-Report - 01-07
KW - Online Optimization
KW - randomized algorithms
KW - lower bounds
KW - competitive analysis
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6338
ER -
TY - GEN
A1 - Steinbach, Marc
T1 - Tree-Sparse Convex Programs
N2 - Dynamic stochastic programs are prototypical for optimization problems with an inherent tree structure inducing characteristic sparsity patterns in the KKT systems of interior methods. We propose an integrated modeling and solution approach for such tree-sparse programs. Three closely related natural formulations are theoretically analyzed from a control-theoretic viewpoint and compared to each other. Associated KKT solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.
T3 - ZIB-Report - 01-08
KW - Convex program
KW - tree
KW - discrete-time optimal control multistage stochastic program
KW - recursive factorization
KW - local projection
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6340
ER -
TY - GEN
A1 - Brandt, Andreas
A1 - Brandt, Manfred
T1 - On the Moments of the Overflow and Freed Carried Traffic for the GI/M/C/0 System
N2 - In circuit switching networks call streams are characterized by their mean and peakedness (two-moment method). The $GI/M/C/0$ system is used to model a single link, where the $GI$-stream is determined by fitting moments appropriately. For the moments of the overflow traffic of a $GI/M/C/0$ system there are efficient numerical algorithms available. However, for the moments of the freed carried traffic, defined as the moments of a virtual link of infinite capacity to which the process of calls accepted by the link (carried arrival process) is virtually directed and where the virtual calls get fresh exponential i.i.d.\ holding times, only complex numerical algorithms are available. This is the reason why the concept of the freed carried traffic is not used rigorously. The main result of this paper is an efficient algorithm for computing the moments of the freed carried traffic, in particular an explicit formula for its peakedness. This result offers a unified handling of both overflow and carried traffics in networks. Furthermore, some refined characteristics for the overflow and freed carried streams are derived.
T3 - ZIB-Report - 01-09
KW - GI/M/C/0 system
KW - overflow traffic
KW - freed carried traffic
KW - carried arrival process
KW - factorial moments
KW - peakedness
KW - two-moment method
KW - difference
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6355
ER -
TY - GEN
A1 - Kuberek, Monika
T1 - KOBV: institutionalisiert
N2 - Der Aufsatz ist die ausgearbeitete Fassung eines Vortrages, gehalten am 05.04.2001 auf dem 91. Deutschen Bibliothekartag in Bielefeld. Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) ist im Rahmen eines wissenschaftlichen Projektes in den Jahren 1997 bis 2000 am Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) aufgebaut worden. Nachdem das Projekt erfolgreich abgeschlossen ist, wird der KOBV 2001 institutionalisiert. In dem Vortrag hat die Verfasserin einen Überblick über das bisher Erreichte, den derzeitigen Stand und die Perspektiven des neuen Verbundes gegeben. Der KOBV stellt eine neue Art von Bibliotheksverbund dar. Sein technisches Konzept und sein organisatorischer Aufbau basieren auf der {\sl Internetphilosophie}. Den informationstechnischen Kern bildet eine Suchmaschine, die die heterogenen lokalen Bibliothekssysteme miteinander verbindet. Die KOBV-Organisation ist dezentral. Sie wird getragen von der Kooperation der Bibliotheken in Berlin und Brandenburg. Eine kleine Verbundzentrale koordiniert dieses Geflecht vernetzter lokaler Einheiten, vertritt den KOBV nach außen und arbeitet - in Form von Projekten - an seiner Weiterentwicklung. Der Entwicklungsaspekt und die Nutzerorientierung sind zwei wesentliche Komponenten in der Verbundarbeit. Berlin und Brandenburg haben auf engem Raum zahlreiche Bibliotheken mit großen, reichhaltigen Medienbeständen. Mittel- bis langfristig sollen Bibliotheken aller Sparten und Größen in den KOBV integriert werden, seien es wissenschaftliche Universalbibliotheken, universitäre Bibliothekssysteme, Spezialbibliotheken, Behörden- und Parlamentsbibliotheken oder öffentliche Bibliotheken. Auch regionale Bibliotheksverbünde können als Subverbünde am KOBV teilnehmen. Mit der KOBV-Suchmaschine ist eine offene Plattform geschaffen worden, auf der weitere Entwicklungen aufsetzen können. Der Aufbau einer virtuellen Regionalbibliothek mit Bestell- und Lieferkomponenten ist eines der Ziele. Darüber hinaus ist es die Vision, in der Region ein virtuelles {\sl Wissensportal} aufzubauen, das dem Nutzer unter einer Adresse den umfassenden Zugang und die umfassende Bereitstellung von Informationen aller Art bietet.
T3 - ZIB-Report - 01-10
KW - Bibliotheksverbund
KW - KOBV
KW - Kooperativer Bibliotheksverbund Berlin-Brandenburg
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6360
ER -
TY - GEN
A1 - Reinefeld, Alexander
A1 - Lindenstruth, Volker
T1 - How to Build a High-Performance Compute Cluster for the Grid
N2 - The success of large-scale multi-national projects like the forthcoming analysis of the LHC particle collision data at CERN relies to a great extent on the ability to efficiently utilize computing a management software (Datagrid, Globus, etc.), while the effective integration of computing nodes has been largely neglected up to now. This is the focus of our work. We present a framework for a high-performance cluster that can be used as a reliable computing node in the Grid. We outline the cluster architecture, the management of distributed data and the seamless intergration of the cluster into the Grid environment.
T3 - ZIB-Report - 01-11
KW - cluster architecture
KW - resource management
KW - Grid computing
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6374
ER -
TY - GEN
A1 - Grötschel, Martin
T1 - Copyright und elektronisches Publizieren: Auf dem Weg zu vernünftigen Regelungen?
N2 - Das \emph{Committee on Electronic Information and Communication} (CEIC) der \emph{International Mathematical Union} (IMU) hat die Aufgabe, sich über die langfristige Informationsversorgung in der Mathematik Gedanken zu machen und Lösungsvorschläge hierfür zu erarbeiten. Das Kernthema ist natürlich "`Elektronisches Publizieren"'. Dazu gehören auch Copyright-Regelungen. % Sie sind -- % neben einer Andeutung der weiteren CEIC-Pläne -- der Fokus dieses % kurzen Artikels. Er schließt mit einem von der IMU verabschiedeten % Aufruf zu vernünftigem Verhalten bei Copyright-Vereinbarungen. Eine % nachhaltige Befolgung dieses Aufrufs -- verbunden mit weiteren % Aktivitäten -- könnte die (derzeit kaum noch bezahlbare und % dadurch gefährdete) Literaturversorgung nachhaltig zum Positiven % verändern. Mit diesem Artikel beginnt eine kleine Serie von Aufsätzen, in denen ich (in meiner Funktion als eines von elf CEIC-Mitgliedern) die Empfehlungen des CEIC erläutern werde. % Das heutige Thema sind die % CEIC-Vorschläge zum Copyright
T3 - ZIB-Report - 01-13
KW - Copyright
KW - elektronisches Publizieren
KW - IMU
KW - CEIC
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6395
ER -
TY - GEN
A1 - Sperber, Wolfram
A1 - Dalitz, Wolfgang
T1 - Portale, Search Engines und Math-Net
N2 - Wie sucht ein Wissenschaftler im Internet die ben"otigten Informationen für seine Arbeit? Welche relevanten Informationen gibt es überhaupt im Web? Sind dafür solche Suchmaschinen wie AltaVista, Google oder HotBot die richtigen Werkzeuge? Die Antwort der Mathematiker heisst Math-Net, ein Informations- und Kommunikationssystem für die Mathematik. Math-Net besteht zunächst aus den Informationen von Personen und Institutionen, die ihre für die Mathematik relevanten Informationen dort bereitstellen wollen. Das soll i.a. auf den Web-Servern der Personen oder Institutionen geschehen. Hierin unterscheidet sich die Situation im Math-Net nicht von der im WWW insgesamt. Im Math-Net sollen aber die Informationen in einheitlicher Weise erschlossen werden. Dazu gibt es sowohl für Server als auch für die Dokumente Empfehlungen für deren Strukturierung. Die lokalen Informationen werden dann im Math-Net durch automatische Verfahren gesammelt, ausgewertet und indexiert. Diese Indexe sind die Basis für die Math-Net Dienste. Das sind Search Engines und Portale, die einen qualifizierten und effizienten Zugang zu den Informationen im Math-Net bieten. Die Math-Net Dienste sind auf die Mathematik spezialisiert. Im Gegensatz zu den oben erwähnten universellen Suchmaschinen decken sie nur einen winzigen Bruchteil des Web ab, aber dafür den für die Mathematik relevanten Teil. Math-Net ist mehr als nur Search Engine oder Portal zu Informationen in der Mathematik. Es ist auch ein Informations- und Kommunikationssystem sowie ein Publikationsmedium für die Mathematik. Die mathematische Community hat sich in der Math-Net Initiative organisiert. Diese Initiative wird von der International Mathematical Union (IMU), der weltweiten Dachorganisation der mathematischen Gesellschaften, koordiniert. Die Entwicklung des Math-Net wird von dem breiten Konsens der Mathematiker getragen, den Zugang zu der für die Mathematik relevanten Information zu erleichtern und zu verbessern.
T3 - ZIB-Report - 00-24
KW - Math-Net
KW - Portals
KW - search engines
KW - information retrieval
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5923
ER -
TY - GEN
A1 - Ilgenfritz, Ernst-Michael
A1 - Kerler, Werner
A1 - Müller-Preussker, Michael
A1 - Stüben, Hinnerk
T1 - Parallel tempering and decorrelation of topological charge in full QCD
N2 - 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.
T3 - ZIB-Report - 00-25
KW - QCD
KW - parallel tempering
KW - topological charge
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5930
ER -
TY - GEN
A1 - Huisinga, Wilhelm
T1 - The Essential Spectral Radius and Asymptotic Properties of Transfer Operators
N2 - 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.
T3 - ZIB-Report - 00-26
KW - constrictive
KW - asymptotically stable
KW - exact
KW - asymptotically periodic
KW - ergodic
KW - aperiodic
KW - Frobenius Perron operator
KW - Koopman operator
KW - Markov o
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5942
ER -
TY - GEN
A1 - Stalling, Detlev
A1 - Seebass, Martin
A1 - Zöckler, Malte
A1 - Hege, Hans-Christian
T1 - Hyperthermia Treatment Planning with HyperPlan - User's Manual
N2 - 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.
T3 - ZIB-Report - 00-27
KW - image segmentation
KW - grid generation
KW - visualization
KW - therapy planning
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5957
ER -
TY - GEN
A1 - Seebass, Martin
A1 - Beck, Rudolf
A1 - Gellermann, Johanna
A1 - Nadobny, Jacek
A1 - Wust, Peter
T1 - Electromagnetic phased arrays for regional hyperthermia -- optimal frequency and antenna arrangement
N2 - 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.
T3 - ZIB-Report - 00-28
KW - Pelvic heating
KW - phased array optimization
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5961
ER -
TY - GEN
A1 - Wagler, Annegret
T1 - The Classes of Critically and Anticritically Perfect Graphs
N2 - 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.
T3 - ZIB-Report - 00-29
KW - perfect graphs
KW - critically perfect graphs
KW - anticritically perfect graphs
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5975
ER -
TY - GEN
A1 - Potra, Florian
T1 - A path-following method for linear complementarity problems based on the affine invariant Kantorovich Theorem
N2 - 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.
T3 - ZIB-Report - 00-30
KW - Linear complementarity problem
KW - interior-point algorithm
KW - path-following
KW - Kantorovich Theorem
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5981
ER -
TY - GEN
A1 - Hege, Hans-Christian
A1 - Merzky, Andre
A1 - Zachow, Stefan
T1 - Distributed Visualization with OpenGL Vizserver: Practical Experiences
N2 - 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.
T3 - ZIB-Report - 00-31
KW - remote visualization
KW - high performance computing
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5992
ER -
TY - GEN
A1 - Gatermann, Karin
T1 - Counting stable solutions of sparse polynomial systems in chemistry
N2 - 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.
T3 - ZIB-Report - 00-32
KW - mass action kinetics
KW - toric variety
KW - stability
KW - circuit
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6007
ER -
TY - GEN
A1 - Grötschel, Martin
A1 - Kuberek, Monika
A1 - Lill, Monika
A1 - Lohrum, Stefan
A1 - Lügger, Joachim
A1 - Rusch, Beate
T1 - Kooperativer Bibliotheksverbund Berlin-Brandenburg (KOBV)
N2 - Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) wurde in den Jahren 1997-2000 im Rahmen eines wissenschaftlichen Projektes eingerichtet. Er stellt eine neuartige Form von Bibliotheksverbund dar. Sein technisches Konzept und sein organisatorischer Aufbau basieren auf der Internetphilosophie. Den informationstechnischen Kern bildet eine Suchmaschine, die die heterogenen lokalen Bibliothekssysteme miteinander verbindet. Die KOBV-Organisation ist dezentral. Sie wird getragen von der Kooperation der Bibliotheken in Berlin und Brandenburg; diese werden von einer kleinen Verbundzentrale unterstützt. Die KOBV-Suchmaschine ist zu erreichen unter: {\begin{rawhtml} http://www.kobv.de/suche/ \end{rawhtml}}
T3 - ZIB-Report - 00-43
KW - Bibliotheksverbund
KW - KOBV
KW - Kooperativer Bibliotheksverbund Berlin-Brandenburg
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6118
ER -
TY - GEN
A1 - Grötschel, Martin
T1 - Mathematik in der Industrie: interessante Branchen und zukünftige Einsatzfelder
N2 - Dieser kurze Artikel hat keine umfassende Übersicht zum Ziel. Basierend auf eigenen Erfahrungen durch Projekte mit Industriefirmen möchte ich einige Branchen erwähnen, bei denen nach meiner Einschätzung Mathematik in Zukunft zunehmend Anwendung finden wird. Ich werde das anhand konkreter Beispiele erläutern. Mathematik ersetzt in der Regel traditionelle Analyse-, Planungs- und Entwurfstechniken. Den (nicht leichten) Schritt zum Einsatz mathematischer Methoden macht ein Praktiker nur, wenn es sich für ihn ``lohnt''. Wann sich dies lohnt, ist schwer abzuschätzen. Man kann aber einige Indikatoren dafür finden, ob eine Branche für den Einsatz von Mathematik ``reif'' ist. Ob es dann dazu kommt, hängt von vielen Faktoren ab, nicht zuletzt von der Psychologie und dem sozialen Umfeld der beteiligten Personen sowie der Bereitschaft, sich auf ein so schwieriges Terrain zu begeben und Kompromisse einzugehen. Gerade letzteres fällt Mathematikern gelegentlich schwer.
T3 - ZIB-Report - 00-44
KW - Mathematics in Industry
KW - Telecommunication
KW - Energy
KW - Transportation
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6125
ER -
TY - GEN
A1 - Rambau, Jörg
T1 - Circuit Admissible Triangulations of Oriented Matroids
N2 - 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.
T3 - ZIB-Report - 00-45
KW - triangulations of oriented matroids
KW - topological type
KW - segment adjacency graph
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6139
ER -
TY - GEN
A1 - Rambau, Jörg
T1 - Triangulierungen von Punktmengen und Polyedern
N2 - Dieser Report wurde im Sommersemester 2000 an der TU Berlin in einer Spezialvorlesung über Triangulierungen von Punktmengen und Polyedern als Skriptum verwendet. Nach einem motivierenden Kapitel werden grundlegende Begriffe und Konstruktionen in der Theorie der Triangulierungen von Punktmengen und Polyedern vorgestellt. Danach werden als weiterführende Themen reguläre Triangulierungen, Sekundärpolytope, bistellare Operationen, höhere Stasheff-Tamari-Halbordnungen und Triangulierungen mit wenigen bzw. gar keinen Flips behandelt. Ein Kapitel über Enumeration und Optimierung beschließt die Zusammenstellung.
T3 - ZIB-Report - 00-46
KW - point configuration
KW - triangulation
KW - polytope
KW - polyhedron
KW - Gale diagram
KW - secondary polytope
KW - cyclic polytope
KW - graph of all triangulations
KW - conn
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6145
ER -
TY - GEN
A1 - Eisenblätter, Andreas
A1 - Grötschel, Martin
A1 - Koster, Arie M.C.A.
T1 - Frequency Planning and Ramifications of Coloring
N2 - 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.
T3 - ZIB-Report - 00-47
KW - frequency assignment
KW - graph coloring
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6152
ER -
TY - GEN
A1 - Bley, Andreas
A1 - Koch, Thorsten
T1 - Optimierung in der Planung und beim Aufbau des G-WiN
N2 - Ende Juni diesen Jahres wurde das Gigabit-Wissenschaftsnetz offiziell gestartet. In der zweijährigen Vorbereitungsphase wurden nicht nur die technischen Möglichkeiten der neuen Übertragungstechniken und Dienste getestet. Es wurden auch verschiedene Fragestellungen zum effizienten Einsatz der verfügbaren Ressourcen für den Betrieb des G-WiN untersucht. In diesem Artikel beschreiben wir, wie das G-WiN zu seiner jetzigen Struktur und Topologie gekommen ist.
T3 - ZIB-Report - 00-48
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6169
ER -
TY - GEN
A1 - Wagler, Annegret
T1 - Critical and Anticritical Edges in Perfect Graphs
N2 - 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.
T3 - ZIB-Report - 00-49
KW - perfect graphs
KW - critical edges
KW - anticritical edges
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6174
ER -
TY - GEN
A1 - Sander, Oliver
A1 - Runge, Daniel
T1 - Fast Surface Reconstruction Using a Probe Sphere
N2 - 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.
T3 - ZIB-Report - 00-50
KW - Surface Reconstruction
KW - Computational Geometry
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6181
ER -
TY - GEN
A1 - Galliat, Tobias
A1 - Deuflhard, Peter
A1 - Roitzsch, Rainer
A1 - Cordes, Frank
T1 - Automatic Identification of Metastable Conformations via Self-Organized Neural Networks
N2 - 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.
T3 - ZIB-Report - 00-51
KW - biochemical conformations
KW - cluster analysis
KW - Molecular Dynamics
KW - Monte-Carlo methods
KW - operator discretization
KW - Perron cluster
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6197
ER -
TY - GEN
A1 - Stüben, Hinnerk
T1 - Hadron masses from dynamical, non-perturbatively O(a) improved Wilson fermions
N2 - 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.
T3 - ZIB-Report - 00-52
KW - QCD
KW - Hadron masses
Y1 - 2000
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6205
ER -
TY - GEN
A1 - Brandt, Andreas
A1 - Brandt, Manfred
T1 - Individual Overflow and Freed Carried Traffics for a Link with Trunk Reservation
N2 - Two traffic streams $\Phi_1$, $\Phi_2$ are offered a link. The calls of $\Phi_i$ require exponential holding times with parameter $\mu$ and are accepted if less than $C_i$ trunks are occupied. Approximating the $\Phi_i$ by appropriate renewal processes meeting their first two moments, defined as the moments of the numbers of calls in virtual links of infinite capacity to which the traffic streams as freed traffics are virtually directed and where the calls get fresh exponential i.i.d.\ holding times with parameter $\mu$, stable recursive algorithms of complexity $O(\max(C_1,C_2))$ are derived for the first two defined as above moments of the individual overflow and freed carried traffics. The results offer a unified handling of both overflow and carried traffics in circuit switching networks with trunk reservation, providing a basis for new two-moment network dimensioning algorithms.
T3 - ZIB-Report - 01-35
KW - trunk reservation
KW - overflow traffic
KW - freed carried traffic
KW - factorial moments
KW - peakedness
KW - two-moment method
KW - circuit switching network
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6615
ER -
TY - GEN
A1 - Kuberek, Monika
T1 - Der KOBV - eine regionale Service-Einrichtung für Nutzer und Bibliothekare
N2 - Dem vorliegenden Aufsatz liegt ein Vortrag zugrunde, den die Verfasserin auf der Ersten Gemeinsamen Fachtagung der DBV-Landesverbände Berlin und Brandenburg "Wir machen den Weg frei : Fusionen - Kooperationen in Berlin und Brandenburg" am 17. Oktober 2001 gehalten hat, in der Vortragsreihe "Möglichkeiten und Grenzen von Ausleih- und bibliographischen Verbünden - VÖB Berlin, VÖB Brandenburg, KOBV". Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) ist angetreten, um auf der Basis neuer Technologien zeitgemäße, nutzerorientierte Dienstleistungen für den Informationsbereich zu entwickeln und die Informationsinfrastruktur in der Region Berlin-Brandenburg neu zu organisieren. Dabei setzt der KOBV insbesondere auf das Internet. Die Verfasserin beschreibt die einzelnen Stufen, in denen die Dienste des KOBV aufgebaut wurden und kontinuierlich weiter ausgebaut werden. Dabei zeigt sie Vorteile auf, die Nutzern und Bibliotheken durch den Verbund entstehen, und lotet gleichzeitig die Grenzen aus, die dem Verbund gesetzt sind.
T3 - ZIB-Report - 01-36
KW - Bibliotheksverbund
KW - KOBV
KW - Kooperativer Bibliotheksverbund Berlin-Brandenburg
KW - Service-Einrichtung
KW - Service-Einrichtung KOBV
KW - Verbund-Dienstleistu
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6620
ER -
TY - GEN
A1 - Helmberg, Christoph
T1 - Numerical Evaluation of SBmethod
N2 - We report numerical results for SBmethod --- a publically available implementation of the spectral bundle method --- applied to the 7$^{th}$ DIMACS challenge test sets that are semidefinite relaxations of combinatorial optimization problems. The performance of the code is heavily influenced by parameters that control bundle update and eigenvalue computation. Unfortunately, no mathematically sound guidelines for setting them are known. Based on our experience with SBmethod, we propose heuristics for dynamically updating the parameters as well as a heuristc for improving the starting point. These are now the default settings of SBmethod Version 1.1. We compare their performance on the DIMACS instances to our previous best choices for Version 1.0. SBmethod Version 1.1 is also part of the independent DIMACS benchmark by H.~Mittelmann. Based on these results we try to analyze strengths and weaknesses of our approach in comparison to other codes for large scale semidefinite programming.
T3 - ZIB-Report - 01-37
KW - semidefinite programming
KW - large scale methods
KW - computational
KW - semidefinite relaxations
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6637
ER -
TY - GEN
A1 - Koster, Arie M.C.A.
A1 - Bodlaender, Hans L.
A1 - Hoesel, Stan P.M. van
T1 - Treewidth: Computational Experiments
N2 - Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed $k$, linear time algorithms exist to solve the decision problem ``treewidth $\leq k$'', their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.
T3 - ZIB-Report - 01-38
KW - treewidth
KW - heuristics
KW - lower bounds
KW - computations
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6644
ER -
TY - GEN
A1 - Bodlaender, Hans L.
A1 - Koster, Arie M.C.A.
A1 - Eijkhof, Frank van den
A1 - Gaag, Linda C. van der
T1 - Pre-processing for Triangulation of Probabilistic Networks
N2 - The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.
T3 - ZIB-Report - 01-39
KW - triangulation
KW - treewidth
KW - probabilistic networks
KW - pre-processing
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6655
ER -
TY - GEN
A1 - Aardal, Karen I.
A1 - Hoesel, Stan P.M. van
A1 - Koster, Arie M.C.A.
A1 - Mannino, Carlo
A1 - Sassano, Antonio
T1 - Models and Solution Techniques for Frequency Assignment Problems
N2 - {\begin{rawhtml} Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0 \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.
T3 - ZIB-Report - 01-40
KW - frequency assignment
Y1 - 2001
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6667
ER -
TY - GEN
A1 - Kuberek, Monika
A1 - Lill, Monika
A1 - Litsche, Stefan
A1 - Lohrum, Stefan
A1 - Lügger, Joachim
A1 - Otto, Dagmar
A1 - Rusch, Beate
T1 - Entwicklungsprojekt "KOBV-Informationsportal" : Teilprojekte der 1. Stufe
N2 - Die KOBV-Suchmaschine hat seit ihrer Inbetriebnahme Ende 1999 entscheidend zur Verbesserung der Informationsinfrastruktur in Berlin und Brandenburg beigetragen. Auf der Basis der offenen Plattform KOBV-Suchmaschine wird die KOBV-Zentrale gemeinsam mit den Bibliotheken in den nächsten Jahren das Dienstleistungsangebot des KOBV und seiner Bibliotheken kontinuierlich erweitern. Dabei sollen die Prinzipien des KOBV - Offenheit, Heterogenität und Dezentralität auf technischer und organisatorischer Ebene - gewahrt bleiben. Die einzelnen KOBV-Bibliotheken werden sich mit ihren Angeboten in unterschiedlicher Weise im Web positionieren. Die Integration auf regionaler Ebene kann und soll die lokalen Angebote nicht künstlich vereinheitlichen. Das kooperative Portal, das in der Region aufgebaut wird, ist als System geplant, in dem zentrales Portal und lokale Portale nicht hierarchisch einander zugeordnet, sondern miteinander vernetzt sind. Das \glqq KOBV-Informationsportal \grqq soll in der KOBV-Zentrale im Rahmen eines wissenschaftlichen Projektes von Mitte 2001 bis Ende 2003 aufgebaut werden. Das vorliegende Papier gibt einen ersten allgemeinen Einblick, welche Funktionen das \glqq KOBV-Informationsporta \grqq umfassen soll und stellt die Teilprojekte der 1. Stufe vor.
T3 - ZIB-Report - 01-41
KW - Bibliotheksverbund
KW - Digitale Bibliothek
KW - KOBV
KW - KOBV-Informationsportal
KW - Kooperativer Bibliotheksverbund Berlin-Brandenburg
KW - Portal
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6678
ER -
TY - GEN
A1 - Hohage, Thorsten
A1 - Schmidt, Frank
A1 - Zschiedrich, Lin
T1 - A new method for the solution of scattering problems
N2 - 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.
T3 - ZIB-Report - 02-01
KW - transparent boundary conditions
KW - inhomogeneous exterior domains
KW - Laplace transform
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6683
ER -
TY - GEN
A1 - Pfeifle, Julian
A1 - Rambau, Jörg
T1 - Computing Triangulations Using Oriented Matroids
N2 - 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.
T3 - ZIB-Report - 02-02
KW - triangulation
KW - oriented matroid
KW - software
KW - chirotope
KW - circuit
KW - cocircuit
KW - symmetry
KW - regular
KW - secondary polytope
KW - hypergeometric function
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6692
ER -
TY - GEN
A1 - Wagler, Annegret
T1 - Relaxing Perfectness: Which Graphs are 'Almost' Perfect?
N2 - 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?
T3 - ZIB-Report - 02-03
KW - perfect graph
KW - stable set polytope
KW - relaxations
Y1 - 2002
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6700
ER -