@misc{BodlaenderFominKosteretal.2006, author = {Bodlaender, Hans L. and Fomin, Fedor V. and Koster, Arie M.C.A. and Kratsch, Dieter and Thilikos, Dimitrios M.}, title = {On exact algorithms for treewidth}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9265}, number = {06-32}, year = {2006}, abstract = {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.}, language = {en} } @misc{Boehner2008, type = {Master Thesis}, author = {B{\"o}hner, D{\"o}rte}, title = {Chancen und Risiken Digitaler Rechtebeschreibung f{\"u}r wissenschaftliche Bibliotheken in Deutschland - M{\"o}glichkeiten und Perspektiven von Digital Rights Management}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9271}, school = {Zuse Institute Berlin (ZIB)}, year = {2008}, abstract = {Wissenschaftliche Bibliotheken sind Vermittler von digitalen Medieninhalten. Sie m{\"u}ssen ihren Nutzern einen Zugang zu ihnen erm{\"o}glichen. Digitales Rechte Management (DRM), eingesetzt von den Verlagen, soll Nutzung und Zugang kontrollieren. Bibliotheken stehen DRM daher misstrauisch gegen{\"u}ber, da dieses als Gefahr f{\"u}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{\"o}glicht es ihnen, ihre Rolle als Vermittler und 'Ged{\"a}chtnis der Menschheit' auch weiterhin erfolgreich wahrnehmen zu k{\"o}nnen. Unbestritten ist, dass DRM in seiner restriktiven Form die t{\"a}gliche Arbeit der Bibliotheken erschwert. Deshalb m{\"u}ssen sie sich aktiv an der Standardisierung, der Entwicklung von Nutzungskonzepten und der Gestaltung der Rahmenbedingungen beteiligen.}, language = {de} } @misc{Imhof2006, author = {Imhof, Andres}, title = {RSWK/SWD und Faceted Browsing: neue M{\"o}glichkeiten einer inhaltlich-intuitiven Navigation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9289}, number = {06-34}, year = {2006}, abstract = {Das deutschsprachige Bibliothekswesen verf{\"u}gt mit den \glqq Regeln f{\"u}r den Schlagwortkatalog \grqq (RSWK) unter Verwendung der \glqq Schlagwortnormdatei \grqq (SWD) {\"u}ber ein Instrumentarium, welches zusammen mit einem \glqq Faceted Browsing \grqq das bisher bestehende Angebot f{\"u}r ein Information Retrieval optimal erg{\"a}nzen kann. Die Verbindung zwischen Standardvokabular (SWD) und Kettenbildung (RSWK) einerseits und eine nach Facetten-Eigenschaften gegliederte Navigation andererseits unterst{\"u}tzt bestm{\"o}glich eine inhaltlich bezogene Recherche. Die St{\"a}rken und Schw{\"a}chen der RSWK/SWD werden er{\"o}rtert und auch Klassifikationen (DDC und RVK) als m{\"o}gliche Facetten diskutiert.}, language = {de} } @misc{KubeWeber2006, author = {Kube, Susanna and Weber, Marcus}, title = {Coarse Grained Molecular Kinetics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9299}, number = {06-35}, year = {2006}, abstract = {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.}, language = {en} } @misc{DaubechiesTeschkeVese2006, author = {Daubechies, Ingrid and Teschke, Gerd and Vese, Luminita}, title = {Iteratively Solving Linear Inverse Problems under General Convex Contraints}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9304}, number = {06-36}, year = {2006}, abstract = {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.}, language = {en} } @misc{RaackKosterWessaely2007, author = {Raack, Christian and Koster, Arie M.C.A. and Wess{\"a}ly, Roland}, title = {On the strength of cut-based inequalities for capacitated network design polyhedra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9512}, number = {07-08}, year = {2007}, abstract = {In this paper we study capacitated network design problems, differentiating directed, bidirected and undirected link capacity models. We complement existing polyhedral results for the three variants by new classes of facet-defining valid inequalities and unified lifting results. For this, we study the restriction of the problems to a cut of the network. First, we show that facets of the resulting cutset polyhedra translate into facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Second, we provide an analysis of the facial structure of cutset polyhedra, elaborating the differences caused by the three different types of capacity constraints. We present flow-cutset inequalities for all three models and show under which conditions these are facet-defining. We also state a new class of facets for the bidirected and undirected case and it is shown how to handle multiple capacity modules by Mixed Integer Rounding (MIR).}, language = {en} } @misc{DeuflhardNowakLutzWestphal2007, author = {Deuflhard, Peter and Nowak, Ulrich and Lutz-Westphal, Brigitte}, title = {Bessel'scher Irrgarten}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9525}, number = {07-09}, year = {2007}, abstract = {Dieser Artikel berichtet {\"u}ber eine erfolgreiche Sch{\"u}leraktivit{\"a}t, die seit Jahren am Zuse-Institut Berlin (ZIB) bei Besuchen von Sch{\"u}lergruppen erprobt und verfeinert worden ist. Das hier zusammengestellte Material ist gedacht als Basis f{\"u}r eine Unterrichtseinheit in Leistungskursen Mathematik an Gymnasien. Inhaltlich wird von einem zwar f{\"u}r Sch{\"u}ler (wie auch Lehrer) neuen, aber leicht fasslichen Gegenstand ausgegangen: der Drei-Term-Rekursion f{\"u}r Besselfunktionen. Die Struktur wird erkl{\"a}rt und in ein kleines Programm umgesetzt. Dazu teilen sich die Sch{\"u}ler selbstorganisierend in Gruppen ein, die mit unterschiedlichen Taschenrechnern "um die Wette" rechnen. Die Sch{\"u}ler und Sch{\"u}lerinnen erfahren unmittelbar die katastrophale Wirkung von an sich kleinen'' Rundungsfehlern, sie landen -- ebenso wie der Supercomputer des ZIB -- im Bessel'schen Irrgarten''. Die auftretenden Ph{\"a}nomene werden mathematisch elementar erkl{\"a}rt, wobei lediglich auf das Konzept der linearen Unabh{\"a}ngigkeit zur{\"u}ckgegriffen wird. Das dabei gewonnene vertiefte Verst{\"a}ndnis fließt ein in die Konstruktion eines klassischen Algorithmus sowie eines wesentlich verbesserten Horner-artigen Algorithmus.}, language = {de} } @misc{KosterZymolkaKutschka2007, author = {Koster, Arie M.C.A. and Zymolka, Adrian and Kutschka, Manuel}, title = {Algorithms to Separate {0,1/2}-Chvatal-Gomory Cuts}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9531}, number = {07-10}, year = {2007}, abstract = {Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or \$\frac{1}{2}\$, such cuts are known as \$\{0,\frac{1}{2}\}\$-cuts. It has been proven by Caprara and Fischetti (1996) that separation of \$\{0,\frac{1}{2}\}\$-cuts is NP-hard. In this paper, we study ways to separate \$\{0,\frac{1}{2}\}\$-cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated \$\{0,\frac{1}{2}\}\$-cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the algorithmic framework. Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers.}, language = {en} } @misc{GeerdesEisenblaetter2007, author = {Geerdes, Hans-Florian and Eisenbl{\"a}tter, Andreas}, title = {Reconciling Theory and Practice: A Revised Pole Equation for W-CDMA Cell Powers}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9543}, number = {07-11}, year = {2007}, abstract = {The performance evaluation of W-CDMA networks is intricate as cells are strongly coupled through interference. Pole equations have been developed as a simple tool to analyze cell capacity. Numerous scientific contributions have been made on their basis. In the established forms, the pole equations rely on strong assumptions such as homogeneous traffic, uniform users, and constant downlink orthogonality factor. These assumptions are not met in realistic scenarios. Hence, the pole equations are typically used during initial network dimensioning only. Actual network (fine-) planning requires a more faithful analysis of each individual cell's capacity. Complex analytical analysis or Monte-Carlo simulations are used for this purposes. In this paper, we generalize the pole equations to include inhomogeneous data. We show how the equations can be parametrized in a cell-specific way provided the transmit powers are known. This allows to carry over prior results to realistic settings. This is illustrated with an example: Based on the pole equation, we investigate the accuracy of average snapshot'' approximations for downlink transmit powers used in state-of-the-art network optimization schemes. We confirm that the analytical insights apply to practice-relevant settings on the basis of results from detailed Monte-Carlo simulation on realistic datasets.}, language = {en} } @misc{RuprechtSchaedleSchmidtetal.2007, author = {Ruprecht, Daniel and Sch{\"a}dle, Achim and Schmidt, Frank and Zschiedrich, Lin}, title = {Transparent boundary conditons for time-dependent problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9558}, number = {07-12}, year = {2007}, abstract = {A new approach to derive transparent boundary conditions (TBCs) for wave, Schr{\"o}dinger, heat and drift-diffusion equations is presented. It relies on the pole condition and distinguishes between physical reasonable and unreasonable solutions by the location of the singularities of the spatial Laplace transform of the exterior solution. To obtain a numerical algorithm, a M{\"o}bius transform is applied to map the Laplace transform onto the unit disc. In the transformed coordinate the solution is expanded into a power series. Finally, equations for the coefficients of the power series are derived. These are coupled to the equation in the interior, and yield transparent boundary conditions. Numerical results are presented in the last section, showing that the error introduced by the new approximate TBCs decays exponentially in the number of coefficients.}, language = {en} } @misc{VaterKlein2007, author = {Vater, Stefan and Klein, Rupert}, title = {Stability of a Cartesian Grid Projection Method for Zero Froude Number Shallow Water Flows}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9562}, number = {07-13}, year = {2007}, abstract = {In this paper a Godunov-type projection method for computing approximate solutions of the zero Froude number (incompressible) shallow water equations is presented. It is second-order accurate and locally conserves height (mass) and momentum. To enforce the underlying divergence constraint on the velocity field, the predicted numerical fluxes, computed with a standard second order method for hyperbolic conservation laws, are corrected in two steps. First, a MAC-type projection adjusts the advective velocity divergence. In a second projection step, additional momentum flux corrections are computed to obtain new time level cell-centered velocities, which satisfy another discrete version of the divergence constraint. The scheme features an exact and stable second projection. It is obtained by a Petrov-Galerkin finite element ansatz with piecewise bilinear trial functions for the unknown incompressible height and piecewise constant test functions. The stability of the projection is proved using the theory of generalized mixed finite elements, which goes back to Nicola{\"i}des (1982). In order to do so, the validity of three different inf-sup conditions has to be shown. Since the zero Froude number shallow water equations have the same mathematical structure as the incompressible Euler equations of isentropic gas dynamics, the method can be easily transfered to the computation of incompressible variable density flow problems.}, language = {en} } @misc{RaackKosterOrlowskietal.2007, author = {Raack, Christian and Koster, Arie M.C.A. and Orlowski, Sebastian and Wess{\"a}ly, Roland}, title = {Capacitated network design using general flow-cutset inequalities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9576}, number = {07-14}, year = {2007}, abstract = {This paper deals with directed, bidirected, and undirected capacitated network design problems. Using mixed integer rounding (MIR), we generalize flow-cutset inequalities to these three link types and to an arbitrary modular link capacity structure, and propose a generic separation algorithm. In an extensive computational study on 54 instances from the Survivable Network Design Library (SNDlib), we show that the performance of cplex can significantly be enhanced by this class of cutting planes. The computations reveal the particular importance of the subclass of cutset-inequalities.}, language = {en} }