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 - TY - GEN A1 - Kähler, Ralf A1 - Simon, Mark A1 - Hege, Hans-Christian T1 - Fast Volume Rendering of Sparse High-Resolution Datasets Using Adaptive Mesh Refinement Hierarchies N2 - In this paper we present an algorithm that accelerates 3D texture-based volume rendering of large and sparse data sets. A hierarchical data structure (known as AMR tree) consisting of nested uniform grids is employed in order to efficiently encode regions of interest. The hierarchies resulting from this kind of space partitioning yield a good balance between the amount of volume to render and the number of texture bricks -- a prerequisite for fast rendering. Comparing our approach to an octree based algorithm we show that our algorithm increases rendering performance significantly for sparse data. A further advantage is that less parameter tuning is necessary. T3 - ZIB-Report - 01-25 KW - scalar field visualization KW - volume visualization KW - volume rendering KW - 3D texture mapping KW - hierarchical space partitioning KW - AMR tree KW - octree KW - spar Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6516 ER - TY - GEN A1 - Helmberg, Christoph T1 - A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations N2 - The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges to the optimal solution under reasonable assumptions on the separation oracle and the feasible set. We have implemented a practical variant of the cutting plane algorithm for improving semidefinite relaxations of constrained quadratic 0-1 programming problems by odd-cycle inequalities. We also consider separating odd-cycle inequalities with respect to a larger support than given by the cost matrix and present a heuristic for selecting this support. Our preliminary computational results for max-cut instances on toroidal grid graphs and balanced bisection instances indicate that warm start is highly efficient and that enlarging the support may sometimes improve the quality of relaxations considerably. T3 - ZIB-Report - 01-26 KW - bisection KW - equicut KW - max-cut KW - semidefinite programming KW - spectral bundle method KW - subgradient method KW - quadratic 0-1 programming Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6527 ER - TY - GEN A1 - Grötschel, Martin T1 - Telota - was soll das? N2 - Telota ist ein Kunstwort, das für alle Aktivitäten der Berlin-Brandenburgischen Akademie der Wissenschaften steht, die der Förderung von Forschung, Kommunikation und Präsentation durch elektronische Medien dienen. In diesem Artikel werden die Entstehung des Telota-Projektes geschildert und die Ziele diskutiert, die mit diesem Projekt erreicht werden sollen. Es geht darum, moderne Informationstechnik bewusst, geplant und nachhaltig für alle Belange der {\rm BBAW} einzusetzen. Informationstechnische Werkzeuge sollen für die wissenschaftliche Arbeit effizient genutzt werden; die Information nach innen und nach außen soll deutlich verbessert werden; eine bessere Kommunikationsinfrastuktur soll die Zusammenarbeit fördern. T3 - ZIB-Report - 01-27 KW - BBAW KW - Telota-Projekt KW - elektronische Publikation Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6538 ER - TY - GEN A1 - Grötschel, Martin T1 - Empfehlungen des Wissenschaftsrates zur digitalen Informationsversorgung durch Hochschulbibliotheken N2 - Der Wissenschaftsrat hat in seiner Juli-Sitzung 2001 \glqq Empfehlungen zur digitalen Informationsversorgung durch Hochschulbibliotheken \grqq verabschiedet. Einige der Vorschläge des Wissenschaftsrates können, falls sie von den angesprochenen Institutionen aufgenommen werden, zu einer nachhaltigen Veränderung der wissenschaftlichen Informationslandschaft führen. In meinem kurzen Kommentar zu diesem Papier möchte ich auf einige dieser Anregungen hinweisen. T3 - ZIB-Report - 01-28 KW - Wissenschaftsrat KW - digitale Informationsversorgung KW - Hochschulbibliotheken Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6546 ER - TY - GEN A1 - Grötschel, Martin T1 - Mein digitaler Traum N2 - Von welcher "Informationsumwelt" träumt jemand, der für seine wissenschaftliche (und sonstige) Arbeit digitale Informationstechnologie intensiv einsetzt? In diesem Artikel beschreibe ich meinen "digitalen Traum". Er ist ganz einfach zu formulieren:"Ich will alles und zwar sofort, jederzeit, "überall" und kostenlos zur Verfügung haben." Ich schildere, was davon heute schon (fast) realisiert ist und was noch fehlt. Ich skizziere einige zentrale Schwierigkeiten der vollständigen Realisierung und skizziere mögliche Lösungen. T3 - ZIB-Report - 01-29 KW - digitale Informationstechnologie KW - digitale Information KW - BBAW Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6558 ER - TY - GEN A1 - Kähler, Ralf A1 - Hege, Hans-Christian T1 - Interactive Volume Rendering of Adaptive Mesh Refinement Data N2 - Many phenomena in nature and engineering happen simultaneously on rather diverse spatial and temporal scales, i.e.\ exhibit a multi-scale character. Therefore various hierarchical data structures and numerical schemes have been devised to represent quantitatively such phenomena. A special numerical multilevel technique, associated with a particular hierarchical data structure, is so-called Adaptive Mesh Refinement (AMR). This scheme achieves locally very high spatial and temporal resolutions. Due to its popularity, many scientists are in need of interactive visualization tools for AMR data. In this article we present a 3D texture-based volume rendering algorithm for AMR data, that directly utilizes the hierarchical structure. Thereby interactive rendering even for large data sets is achieved. In particular the problems of interpolation artifacts, opacity corrections, and texture memory limitations are addressed. The algorithm's value in practice is demonstrated with simulation and image data. T3 - ZIB-Report - 01-30 KW - Scalar field visualization KW - multiresolution volume rendering KW - AMR hierarchies KW - 3D texture mapping Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6561 ER - TY - GEN A1 - Kober, Cornelia A1 - Sader, Robert A1 - Zeilhofer, Hans-Florian A1 - Prohaska, Steffen A1 - Zachow, Stefan A1 - Deuflhard, Peter T1 - Anisotrope Materialmodellierung für den menschlichen Unterkiefer N2 - Im Rahmen der biomechanischen Simulation knöcherner Organe ist die Frage nach einer befriedigenden Materialbeschreibung nach wie vor ungelöst. Computertomographische Datensätze liefern eine räumliche Verteilung der (Röntgen-)Dichte und ermöglichen damit eine gute Darstellung der individuellen Geometrie. Weiter können die verschiedenen Materialbestandteile des Knochens, Spongiosa und Kortikalis, voneinander getrennt werden. Aber die richtungsabängige Information der Materialanisotropie ist verloren. In dieser Arbeit wird ein Ansatz für eine anisotrope Materialbeschreibung vorgestellt, die es ermöglicht, den Einfluss der individuellen knöchernen Struktur auf das makroskopische Materialverhalten abzuschätzen. T3 - ZIB-Report - 01-31 KW - menschlicher Unterkiefer KW - Simulation mit der Methode der finiten Elemente KW - innerer Aufbau des Knochens KW - anisotrope Elastizität Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6574 ER - TY - GEN A1 - Zöckler, Malte A1 - Rein, Karlheinz A1 - Brandt, Robert A1 - Stalling, Detlev A1 - Hege, Hans-Christian T1 - Creating Virtual Insect Brains with Amira N2 - By combining techniques of preparation, histology, confocal microscopy, data visualization and data processing, we have created and recently published a standard brain model for drosophila and honey bee brains. This report describes the algorithms and implementation of the corresponding software modules. At the same time it serves as a user's guide for scientist who want to reproduce the results for differerent species or mutants. T3 - ZIB-Report - 01-32 KW - visualization KW - anatomical atlas Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6589 ER - TY - GEN A1 - Ilgenfritz, Ernst-Michael A1 - Kerler, Werner A1 - Müller-Preussker, Michael A1 - Stüben, Hinnerk T1 - Parallel tempering in full QCD with Wilson fermions N2 - We study the performance of QCD simulations with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering on $10^4$ and $12^4$ lattices. In order to compare tempered with standard simulations, covariance matrices between sub-ensembles have to be formulated and evaluated using the general properties of autocorrelations of the parallel tempering algorithm. We find that rendering the hopping parameter $\kappa$ dynamical does not lead to an essential improvement. We point out possible reasons for this observation and discuss more suitable ways of applying parallel tempering to QCD. T3 - ZIB-Report - 01-33 KW - QCD KW - parallel tempering KW - correlation analysis Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6593 ER - TY - GEN A1 - Sokolov, Vladimir V. A1 - Wolf, Thomas T1 - Classification of integrable polynomial vector evolution equations N2 - Several classes of systems of evolution equations with one or two vector unknowns are considered. We investigate also systems with one vector and one scalar unknown. For these classes all equations having the simplest higher symmetry are listed. T3 - ZIB-Report - 01-34 Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6601 ER - TY - GEN A1 - Hohage, Thorsten A1 - Schmidt, Frank T1 - On the Numerical Solution of Nonlinear Schrödinger type equations in fiber optics N2 - 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. T3 - ZIB-Report - 02-04 KW - nonlinear Schroedinger equation KW - split step methods KW - extrapolation KW - collocation methods Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6715 ER - TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Probieren geht über Studieren? Entscheidungshilfen für kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik N2 - Die Automatisierung von innerbetrieblicher Logistik erfordert -- über die physikalische Steuerung von Geräten hinaus -- auch eine effiziente Organisation der Transporte: ein Aufgabenfeld der kombinatorischen Optimierung. Dieser Artikel illustriert anhand von konkreten Aufgabenstellungen die Online-Problematik (unvollständiges Wissen) sowie die Echtzeit-Problematik (beschränkte Rechenzeit), auf die man in der innerbetrieblichen Logistik trifft. Der Text gibt einen Überblick über allgemeine Konstruktionsprinzipien für Online-Algorithmen und Bewertungsmethoden, die bei der Entscheidung helfen, welche Algorithmen für eine vorliegende Problemstellung geeignet sind. T3 - ZIB-Report - 02-05 KW - Logistik KW - Hochregallagerbediengeräte KW - Kommissioniermobile KW - Aufzüge KW - Online-Optimierung KW - Echtzeit-Optimierung KW - Simulation KW - kompetitive Analyse Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6723 ER - TY - GEN A1 - Reinefeld, Alexander A1 - Stüben, Hinnerk A1 - Schintke, Florian A1 - Din, George T1 - GuiGen: A Toolset for Creating Customized Interfaces for Grid User Communities N2 - \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. T3 - ZIB-Report - 02-06 KW - Grid computing KW - customized user interfaces KW - grid user communities KW - web portals KW - XML Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6737 ER - TY - GEN A1 - Wagler, Annegret T1 - Antiwebs are Rank-Perfect N2 - \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. T3 - ZIB-Report - 02-07 KW - relaxations of perfect graphs KW - antiwebs KW - stable set polytope Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6742 ER - TY - GEN A1 - Wolf, Thomas T1 - The integration of systems of linear PDEs using conservation laws of syzygies N2 - 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. T3 - ZIB-Report - 02-08 KW - PDE KW - syzygies KW - conservation laws Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6751 ER - TY - GEN A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Koster, Arie M.C.A. T1 - Frequenzplanung im Mobilfunk N2 - Telekommunikation ist seit Jahren \glqq in\grqq. Zunächst gab es einen enormen Aufschwung; neue Technologien und Dienste haben eine überwältigende, nicht vorhersehbare Akzeptanz gefunden. Derzeit ist -- ausgelöst durch die UMTS-Lizenzversteigerungen, Rezessions- und Sättigungstendenzen -- eine Krise zu verzeichnen. Viele (auch wir) sind davon überzeugt, dass technischer Fortschritt und nützliche Dienste demnächst die Stimmung wieder ändern werden. Wenigen ist allerdings bewusst, welche Rolle Mathematik bei der Entwicklung und dem effizienten Einsatz vieler der neuen Kommunikationstechnologien spielt. In diesem Artikel soll kein Überblick über diesen umfangreichen Themenkreis gegeben werden. Wir zeigen lediglich an einem konkreten Beispiel aus dem Mobilfunk, der Frequenzplanung in GSM-Funknetzen, was man durch geeignete Modellierung der praktischen Fragestellung und den Einsatz problemadäquater Algorithmen erreichen kann. T3 - ZIB-Report - 02-09 KW - Telekommunikation KW - Frequenzplanung KW - Mobilfunk KW - GSM-Funknetze Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6762 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Weider, Steffen T1 - Integrierte Umlauf- und Dienstplanung im Öffentlichen Nahverkehr N2 - Wir beschreiben einen Ansatz zur integrierten Umlauf- und Dienstplanung im öffentlichen Nahverkehr. Der Ansatz zielt auf die Verbesserung des Gesamtwirkungsgrades dieser beiden Planungsschritte und auf die besondere Planungsproblematik im Regionalverkehr. Wir entwickeln dazu mathematische Optimierungstechniken für den Einsatz in den Planungssystemen MICROBUS II und DIVA. T3 - ZIB-Report - 02-10 KW - Integrierte Umlauf- und Dienstplanung KW - Umlaufplanung KW - Dienstplanung KW - Optimierung KW - Regionalverkehr Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6773 ER - TY - GEN A1 - Hougardy, Stefan A1 - Wagler, Annegret T1 - Perfectness is an Elusive Graph Property N2 - 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. T3 - ZIB-Report - 02-11 KW - perfect graph KW - elusive graph property Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6787 ER - TY - GEN A1 - Weber, Marcus A1 - Galliat, Tobias T1 - Characterization of Transition States in Conformational Dynamics using Fuzzy Sets N2 - 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. T3 - ZIB-Report - 02-12 KW - biochemical conformations KW - conformational dynamics KW - molecular dynamics KW - cluster analysis KW - transition states KW - fuzzy sets Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6791 ER - TY - GEN T1 - Jahresbericht 1993 T3 - Jahresbericht - 1993 KW - Annual Report Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9668 SN - 0934-5892 ER - TY - GEN T1 - Jahresbericht 1992 T3 - Jahresbericht - 1992 KW - Annual Report Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9686 SN - 0934-5892 ER - TY - GEN T1 - Jahresbericht 1994 T3 - Jahresbericht - 1994 KW - Annual Report Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9699 SN - 0934-5892 ER - TY - GEN T1 - Jahresbericht 1995 T3 - Jahresbericht - 1995 KW - Annual Report Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9704 SN - 0934-5892 ER - TY - GEN T1 - Jahresbericht 2006 T3 - Jahresbericht - 2006 KW - Annual Report Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9812 SN - 0934-5892 ER - TY - GEN T1 - Jahresbericht 1991 T3 - Jahresbericht - 1991 KW - Annual Report Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9825 SN - 0934-5892 ER - TY - GEN T1 - Jahresbericht 1990 T3 - Jahresbericht - 1990 KW - Annual Report Y1 - 1991 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9831 SN - 0934-5892 ER - TY - GEN T1 - Jahresbericht 1989 T3 - Jahresbericht - 1989 KW - Annual Report Y1 - 1990 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9847 SN - 0934-5892 ER - TY - GEN T1 - Jahresbericht 1988 T3 - Jahresbericht - 1988 KW - Annual Report Y1 - 1989 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9858 SN - 0934-5892 ER - TY - GEN T1 - Jahresbericht 1987 T3 - Jahresbericht - 1987 KW - Annual Report Y1 - 1988 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9860 SN - 0933-7903 ER - TY - GEN T1 - Tätigkeitsbericht 1986 T3 - Jahresbericht - 1986 KW - Annual Report KW - Jahresbericht Y1 - 1987 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9871 ER - TY - GEN T1 - Tätigkeitsbericht 1985 T3 - Jahresbericht - 1985 KW - Annual Report KW - Jahresbericht Y1 - 1986 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9885 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schelten, Uwe A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - A Column Generation Approach to Airline Crew Scheduling N2 - The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel rapid branching'' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH. T3 - ZIB-Report - 05-37 KW - Integer Programming KW - Airline Crew Scheduling KW - Branch and Generate Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8713 ER - TY - GEN A1 - Novikov, Yakov A1 - Brinkmann, Raik T1 - Foundations of Hierarchical SAT-Solving N2 - The theory of hierarchical Boolean satisfiability (SAT) solving proposed in this paper is based on a strict axiomatic system and introduces a new important notion of implicativity. The theory makes evident that increasing implicativity is the core of SAT-solving. We provide a theoretical basis for increasing the implicativity of a given SAT instance and for organizing SAT-solving in a hierarchical way. The theory opens a new domain of research: SAT-model construction. Now quite different mathematical models can be used within practical SAT-solvers. The theory covers many advanced techniques such as circuit-oriented SAT-solving, mixed BDD/CNF SAT-solving, merging gates, using pseudo-Boolean constraints, using state machines for representation of Boolean functions, arithmetic reasoning, and managing don t cares. We believe that hierarchical SAT-solving is a cardinal direction of research in practical SAT-solving. T3 - ZIB-Report - 05-38 KW - SAT KW - implicativity KW - verification KW - Boolean vector function KW - satisfiability KW - Bounded-Model-Checking KW - BMC KW - model KW - block KW - hierarchy Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8728 ER - TY - GEN A1 - Pham, The Anh T1 - Einbettung neuer Verwaltungsmethoden in die hierarchische Dateisystemsicht N2 - Die hierarchische Organisation von Dateien beherrscht Computersysteme seit vielen Jahren und wird sich vermutlich auch in Zukunft weiterhin durchsetzen. Dennoch stößt diese Verwaltungsmethode in einem klassischen hierarchischen Dateisystem bei dem jährlichen rasanten Zuwachs an neuen Daten an ihre Grenzen, auch wenn Nutzer eine ausgefeilte Verzeichnisstruktur mit einer disziplinierten Namensgebung konsequent auf- und ausbauen. Um den Überblick über die Dateien zu behalten, werden in dieser Arbeit neue Verwaltungsmethoden vorgestellt und in die hierarchische Dateisystemsicht eingebettet. Auf der Basis des hierarchischen Dateisystems bietet ein metadatenbasiertes Dateisystem neben dem hierarchischen Zugriff noch einen flexiblen, assoziativen Zugriff auf Dateien über virtuelle Objekte, indem Suchmethoden in Form einer Anfrage auf in einer Datenbank gespeicherte Index- und Metadaten angewendet werden. Das Ergebnis dieser Abfrage wird mit Hilfe von virtuellen Verzeichnissen und virtuellen Dateien in einer übersichtlichen Form dargestellt, so dass eine Nutzung der hierarchischen Sicht weiterhin intuitiv fortgesetzt wird. Das Datenmanagementsystem ZIBDMS, welches einen verteilten Metadatenkatalog und einen Dateireplikationskatalog beinhaltet, ermöglicht es, die oben genannten Verwaltungsmethoden für die NFS-Schnittstelle, CORBA-Middleware und Web Services transparent zu implementieren. Zudem stellt ZIBDMS weitere neue Dateiverwaltungsmethoden zur Verfügung, die sich in die hierarchische Dateisystemsicht integrieren lassen. Metadaten in Form von Attribut-Wert-Paaren lassen sich als virtuelle Datei darstellen und editieren. Eine Collection bietet die Möglichkeit, Dateien in einem logischen virtuellen Ordner zu organisieren. Mit einem Dependency-Graph lassen sich Dateien zueinander in Relation stellen, so dass eine Linkstruktur zwischen Dateien ausgedrückt werden kann. Das Verweiskonzept eines klassischen hierarchischen Dateisystems wird im ZIBDMS um eine neue Verweisart Weak-Link erweitert, um einen aktualisierbaren, konsistenten und zyklenfreien symbolischen Link anzubieten. In einer hierarchischen Sicht lässt sich durch Verweise ein Baum bilden, in dem eine Navigation und Verweisauflistung möglich sind, was außer ZIBDMS noch kein anderes System bietet. N2 - The hierarchical organization of files has dominated computer systems for many years and this will probably not change in the near future. However, with the rapid annual growth of new data this classical hierarchical file system management method reaches its limitations, even when the user consistently sets up and continually expands an elaborated directory structure with well-disciplined naming. This paper introduces new management methods to maintain an overview of all files which can be embedded in the hierarchical file system. A metadata-based file system, which is based on the hierarchical file system, offers, in addition to hierarchical access, a more flexible and associative access to files via virtual objects by providing query capabilities of index- and metadata which are stored in a database. The query results are presented in a clearly-arranged form of virtual directories and virtual files so that the intuitive hierarchical view continues to be maintained. The data management system ZIBDMS, which contains a distributed metadata catalog and a file replication catalog, permits a transparent implementation of these management methods for the NFS interface, CORBA-middleware or web services. Furthermore, ZIBDMS provides other new file management methods that can be integrated into the hierarchical file system view. Metadata in form of attribute-value-pairs can be presented and edited with a virtual file. A Collection makes it possible to organize files in logical virtual folders. Using a Dependency graph, files can be related to each other and expressed through a link structure between these files. In the ZIBDMS the reference concept of a classical hierarchal file system is extended with a new kind of reference called Weak Link in order to provide up-to-date, consistent and cycle-free symbolic links. With the references a tree can be established in a hierarchical view in which navigation and listing of references are possible; this capability is only possible in the ZIBDMS system. T3 - ZIB-Report - 05-41 KW - ZIBDMS KW - Datenmanagementsystem KW - semantisch KW - Indizierung KW - metadatenbasiert KW - hierarchisch KW - Dateisystem KW - semantic file system KW - XMLFS KW - Context Fil Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8747 ER - TY - GEN A1 - Achterberg, Tobias A1 - Berthold, Timo T1 - Improving the Feasibility Pump N2 - The Feasibility Pump of Fischetti, Glover, Lodi, and Bertacco has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, tends to be poor. This paper proposes a slight modification of the algorithm in order to find better solutions. Extensive computational results show the success of this variant: in 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original Feasibility Pump. T3 - ZIB-Report - 05-42 KW - mixed integer programming KW - primal heuristics KW - feasibility pump Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8754 ER - TY - GEN A1 - Kube, Susanna A1 - Weber, Marcus T1 - Conformation Kinetics as a Reduced Model for Transition Pathways N2 - The complexity of molecular kinetics can be reduced significantly by a restriction to metastable conformations which are almost invariant sets of molecular dynamical systems. With the Robust Perron Cl uster Analysis PCCA+, developed by Weber and Deuflhard, we have a tool available which can be used to identify these conformations from a transition probability matrix. This method can also be applied to the corresponding transition rate matrix which provides important information concerning transition pathways of single molecules. In the present paper, we explain the relationship between these tw o concepts and the extraction of conformation kinetics from transition rates. Moreover, we show how transition rates can be approximated and conclude with numerical examples. T3 - ZIB-Report - 05-43 KW - conformation kinetics KW - transition rates KW - Robust Perron Cluster Analysis Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8763 ER - TY - GEN A1 - Griesse, Roland A1 - Weiser, Martin T1 - On the Interplay Between Interior Point Approximation and Parametric Sensitivities in Optimal Control N2 - This paper is concerned with the sensitivities of function space oriented interior point approximations in parameter dependent problems. For an abstract setting that covers control constrained optimal control problems, the convergence of interior point sensitivities to the sensitivities of the optimal solution is shown. Error bounds for $L_q$ norms are derived and illustrated with numerical examples. T3 - ZIB-Report - 05-44 KW - interior point methods KW - parametric sensitivity KW - optimal control Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8773 ER - TY - GEN A1 - Pfetsch, Marc T1 - A Branch-And-Cut for the Maximum Feasible Subsystem Problem N2 - We present a branch-and-cut algorithm for the NP-hard maximum feasible subsystem problem: For a given infeasible linear inequality system, determine a feasible subsystem containing as many inequalities as possible. The complementary problem, where one has to remove as few inequalities as possible in order to render the system feasible, can be formulated as a set covering problem. The rows of this formulation correspond to irreducible infeasible subsystems, which can be exponentially many. The main issue of a branch-and-cut algorithm for MaxFS is to efficiently find such infeasible subsystems. We present three heuristics for the corresponding NP-hard separation problem and discuss further cutting planes. This paper contains an extensive computational study of our implementation on a variety of instances arising in a number of applications. T3 - ZIB-Report - 05-46 KW - infeasible linear inequality system KW - irreducible infeasible subsystem KW - (IIS) maximum feasible subsystem problem KW - minimum IIS-cover KW - branch-and-cut Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8797 ER - TY - GEN A1 - Deuflhard, Peter A1 - Hege, Hans-Christian T1 - Die Vision einer individuellen quantitativen Medizin N2 - Die Autoren schreiben dieses Papier aus der eingeschränkten Sicht der Mathematik und der Informationstechnik. Um den speziellen Beitrag dieser Disziplinen überhaupt diskutieren zu können, sehen wir uns jedoch gezwungen, einen Rahmen abzustecken, den wir für das Jahr 2020 vorhersehen -- nach Wahrscheinlichkeit und aus unserem engeren fachlichen Blickwinkel. Vorab bitten wir schon einmal bei den medizinischen Fachleuten um Nachsicht, wenn wir uns in ihrem Revier allzu dillettantisch bewegen. Vielleicht fördert aber auch unser eingeschränkter Blickwinkel ansonsten unbedachte Aspekte zutage -- das hoffen wir zumindest. T3 - ZIB-Report - 05-47 Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8805 ER - TY - GEN A1 - Harks, Tobias A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Competitive Online Multicommodity Routing N2 - We study online multicommodity minimum cost routing problems in networks, where commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining the routing weights. We discuss an online algorithm that routes each commodity by minimizing a convex cost function that depends on the demands that are previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is $4K/2+K$-competitive, where $K$ is the number of commodities. For the parallel arc case this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably. T3 - ZIB-Report - 06-27 KW - Online Optimization KW - Routing KW - Telecommunications Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9212 ER - TY - GEN A1 - Kaibel, Volker A1 - Koch, Thorsten T1 - Mathematik für den Volkssport N2 - "`Volkssport Sudoku"' titelt der Stern in seiner Ausgabe vom 24. Mai2006. In der Tat traut sich derzeit kaum noch eine Zeitung, ohne Sudoku zu erscheinen. Die Begeisterung am Lösen dieser Zahlenrätsel offenbart eine unvermutete Freude am algorithmischen Arbeiten. Mathematisch kann man Sudokus als lineare diophantische Gleichungssysteme mit Nichtnegativitätsbedingungen formulieren. Solche ganzzahligen linearen Programme sind die wichtigsten Modellierungswerkzeuge in zahlreichen Anwendungsgebieten wie z.B. der Optimierung von Telekommunikations- und Verkehrsnetzen. Moderne Verfahren zur Lösung dieser Optimierungsprobleme sind durch Sudokus allerdings deutlich weniger zu beeindrucken als Zeitungsleser. T3 - ZIB-Report - 06-28 KW - Sudoku KW - Integer Programming KW - General Public Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9225 ER - TY - GEN A1 - Abboud, Nadine A1 - Grötschel, Martin A1 - Koch, Thorsten T1 - Mathematical Methods for Physical Layout of Printed Circuit Boards: An Overview N2 - This article surveys mathematical models and methods used for physical PCB layout, i.e., component placement and wire routing. The main concepts are briefly described together with relevant references. T3 - ZIB-Report - 06-29 KW - PCB Design KW - placement KW - routing Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9231 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Wagler, Annegret T1 - The extreme points of QSTAB(G) and its implications N2 - Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs $G$ where the stable set polytope STAB$(G)$ coincides with the clique constraint stable set polytope QSTAB$(G)$. For all imperfect graphs STAB$(G) \subset$ QSTAB$(G)$ holds and, therefore, it is natural to measure imperfection in terms of the difference between STAB$(G)$ and QSTAB$(G)$. Several concepts have been developed in this direction, for instance the dilation ratio of STAB$(G)$ and QSTAB$(G)$ which is equivalent to the imperfection ratio imp$(G)$ of $G$. To determine imp$(G)$, both knowledge on the facets of STAB$(G)$ and the extreme points of QSTAB$(G)$ is required. The anti-blocking theory of polyhedra yields all {\em dominating} extreme points of QSTAB$(G)$, provided a complete description of the facets of STAB$(\overline G)$ is known. As this is typically not the case, we extend the result on anti-blocking polyhedra to a {\em complete} characterization of the extreme points of QSTAB$(G)$ by establishing a 1-1 correspondence to the facet-defining subgraphs of $\overline G$. We discuss several consequences, in particular, we give alternative proofs of several famous results. T3 - ZIB-Report - 06-30 KW - perfect graphs KW - imperfection ratio KW - stable set polytope Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9249 ER - TY - GEN A1 - Meyer, Holger A1 - Moll, Sebastian A1 - Cordes, Frank A1 - Weber, Marcus T1 - ConFlow? A new space-based Application for complete Conformational Analysis of Molecules N2 - Biochemical interactions are determined by the 3D-structure of the involved components - thus the identification of conformations is a key for many applications in rational drug design. {\sf ConFlow} is a new multilevel approach to conformational analysis with main focus on completeness in investigation of conformational space. In contrast to known conformational analysis, the starting point for design is a space-based description of conformational areas. A tight integration of sampling and analysis leads to an identification of conformational areas simultaneously during sampling. An incremental decomposition of high-dimensional conformational space is used to guide the analysis. A new concept for the description of conformations and their path connected components based on convex hulls and {\em Hypercubes}is developed. The first results of the {\sf ConFlow} application constitute a 'proof of concept' and are further more highly encouraging. In comparison to conventional industrial applications, {\sf ConFlow} achieves higher accuracy and a specified degree of completeness with comparable effort. T3 - ZIB-Report - 06-31 KW - conformational-analysis in-silico-screening drug-design Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9258 ER - TY - GEN A1 - Bodlaender, Hans L. A1 - Fomin, Fedor V. A1 - Koster, Arie M.C.A. A1 - Kratsch, Dieter A1 - Thilikos, Dimitrios M. T1 - On exact algorithms for treewidth N2 - We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time $O^\ast(2^n)$. This algorithm is based on the old dynamic programming method introduced by Held and Karp for the {\sc Tra veling Salesman} problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. However, our experiments show that the space use d by the algorithm is an important factor to what input sizes the algorithm is effective. For this purpose, we settle the problem of computing treewidth under the restriction that the space used is only polynomial. In this direction we give a simple $O^\ast(4^n)$ al gorithm that requires {\em polynomial} space. We also show that with a more complicated algorithm, using balanced separators, {\sc Treewidth} can be computed in $O^\ast(2.9512^n)$ time and polynomial space. T3 - ZIB-Report - 06-32 KW - treewidth KW - exponential algorithms Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9265 ER - TY - THES A1 - Böhner, Dörte T1 - Chancen und Risiken Digitaler Rechtebeschreibung für wissenschaftliche Bibliotheken in Deutschland - Möglichkeiten und Perspektiven von Digital Rights Management T1 - Chances and risks of Digital Rights Description for academic libraries in Germany - Possibilities and perspectives of Digital Rights Management N2 - Wissenschaftliche Bibliotheken sind Vermittler von digitalen Medieninhalten. Sie müssen ihren Nutzern einen Zugang zu ihnen ermöglichen. Digitales Rechte Management (DRM), eingesetzt von den Verlagen, soll Nutzung und Zugang kontrollieren. Bibliotheken stehen DRM daher misstrauisch gegenüber, da dieses als Gefahr für die Wissenschaft und ihre (digitalen) Bibliotheken gesehen wird. Nur eine effektive Auseinandersetzung der wissenschaftlichen Bibliotheken mit der jeweiligen Politik der Verlage und den Verfahrensweisen bei DRM ermöglicht es ihnen, ihre Rolle als Vermittler und 'Gedächtnis der Menschheit' auch weiterhin erfolgreich wahrnehmen zu können. Unbestritten ist, dass DRM in seiner restriktiven Form die tägliche Arbeit der Bibliotheken erschwert. Deshalb müssen sie sich aktiv an der Standardisierung, der Entwicklung von Nutzungskonzepten und der Gestaltung der Rahmenbedingungen beteiligen. N2 - Academic libraries are mediators of digital content. They have to ensure access for their patrons. Digital Rights Management (DRM), used by publishers, should control access and usage. Libraries mistrust DRM, because it is seen as a danger to scholarship, sciences and their (digital) libraries. Libraries only can persist as the 'archive of all human knowledge' if they start an effective controversy about the publishers' policies and if they know how DRM works. It is uncontentious that the restrictive form of DRM will complicate the everyday work of libraries. Therefore they have to engage in the prozess of standardization, in the development of concepts of usage and in the definition of general conditions of DRM. KW - Digital Rights Management KW - Urheberrecht KW - Lizenzvertrag KW - Rechtebeschreibung KW - Rechtebeschreibungssprache KW - Digital Rights Management KW - Licence Agreement KW - German Copyright Law KW - Rights Description KW - Rights Description Language Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9271 ER - TY - GEN A1 - Imhof, Andres T1 - RSWK/SWD und Faceted Browsing: neue Möglichkeiten einer inhaltlich-intuitiven Navigation N2 - Das deutschsprachige Bibliothekswesen verfügt mit den \glqq Regeln für den Schlagwortkatalog \grqq (RSWK) unter Verwendung der \glqq Schlagwortnormdatei \grqq (SWD) über ein Instrumentarium, welches zusammen mit einem \glqq Faceted Browsing \grqq das bisher bestehende Angebot für ein Information Retrieval optimal ergänzen kann. Die Verbindung zwischen Standardvokabular (SWD) und Kettenbildung (RSWK) einerseits und eine nach Facetten-Eigenschaften gegliederte Navigation andererseits unterstützt bestmöglich eine inhaltlich bezogene Recherche. Die Stärken und Schwächen der RSWK/SWD werden erörtert und auch Klassifikationen (DDC und RVK) als mögliche Facetten diskutiert. T3 - ZIB-Report - 06-34 KW - RSWK KW - SWD KW - Faceted Browsing KW - Facetten KW - facettierte Navigation KW - Information Retrieval Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9289 ER - TY - GEN A1 - Kube, Susanna A1 - Weber, Marcus T1 - Coarse Grained Molecular Kinetics N2 - The dynamic behavior of molecules can often be described by Markov processes. From computational molecular simulations one can derive transition rates or transition probabilities between subsets of the discretized conformational space. On the basis of this dynamic information, the spatial subsets are combined into a small number of so-called metastable molecular conformations. This is done by clustering methods like the Robust Perron Cluster Analysis (PCCA+). Up to now it is an open question how this coarse graining in space can be transformed to a coarse graining of the Markov chain while preserving the essential dynamic information. In the following article we aim at a consistent coarse graining of transition probabilities or rates on the basis of metastable conformations such that important physical and mathematical relations are preserved. This approach is new because PCCA+ computes molecular conformations as linear combinations of the dominant eigenvectors of the transition matrix which does not hold for other clustering methods. T3 - ZIB-Report - 06-35 Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9299 ER - TY - GEN A1 - Daubechies, Ingrid A1 - Teschke, Gerd A1 - Vese, Luminita T1 - Iteratively Solving Linear Inverse Problems under General Convex Contraints N2 - We consider linear inverse problems where the solution is assumed to fulfill some general homogeneous convex constraint. We develop an algorithm that amounts to a projected Landweber iteration and that provides and iterative approach to the solution of this inverse problem. For relatively moderate assumptions on the constraint we can always prove weak convergence of the iterative scheme. In certain cases, i.e. for special families of convex constraints, weak convergence implies norm convergence. The presented approach covers a wide range of problems, e.g. Besov- or BV-restoration for which we present also numerical experiments in the context of image processing. T3 - ZIB-Report - 06-36 KW - Linear Inverse Problems KW - Landweber Iteration KW - Besov- and BV Image Restoration Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9304 ER -