TY - GEN A1 - Hochmuth, Reinhard T1 - Homogenization for a Nonlocal Coupling Model N2 - In [7,8,12] homogenization techniques are applied to derive an anisotropic variant of the bio-heat transfer equation as asymptotic result of boundary value problems providing a microscopic description for microvascular tissue. In view of a future application on treatment planning in hyperthermia, we investigate here the homogenization limit for a coupling model, which takes additionally into account the influence of convective heat transfer in medium size blood vessels. This leads to second order elliptic boundary value problems with nonlocal boundary conditions on parts of the boundary. Moreover, we present asymptotic estimates for first order correctors. T3 - ZIB-Report - 04-50 KW - Homogenization KW - nonlocal boundary conditions KW - Robin boundary conditions KW - correctos KW - heat transfer KW - bio-heat equation KW - hyperthermia Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8251 ER - TY - GEN A1 - Baumeister, Timm A1 - Cordes, Frank T1 - A new Model for the Free Energy of Solvation and its Application in Protein Ligand Scoring N2 - A new and time efficient model to evaluate the free energy of solvation has been developed. The solvation free energy is separated into an electrostatic term, a hydrogen bond term, and a rest-term, combining both entropic and van der Waals effects. The electrostatic contribution is evaluated with a simplified boundary element method using the partial charges of the MMFF94 force field. The number of hydrogen bonds and the solvent excluded surface area over the surface atoms are used in a linear model to estimate the non-electrostatic contribution. This model is applied to a set of 213 small and mostly organic molecules, yielding an rmsd of 0.87kcal/mol and a correlation with experimental data of r=0.951. The model is applied as a supplementary component of the free energy of binding to estimate binding constants of protein ligand complexes. The intermolecular interaction energy is evaluated by using the MMFF94 force field. T3 - ZIB-Report - 04-51 KW - scoring KW - solvation KW - free energy Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8265 ER - TY - GEN A1 - Baum, Daniel T1 - Multiple Semi-flexible 3D Superposition of Drug-sized Molecules N2 - In this paper we describe a new algorithm for multiple semi-flexible superpositioning of drug-sized molecules. The algorithm identifies structural similarities of two or more molecules. When comparing a set of molecules on the basis of their three-dimensional structures, one is faced with two main problems. (1) Molecular structures are not fixed but flexible, i.e., a molecule adopts different forms. To address this problem, we consider a set of conformers per molecule. As conformers we use representatives of conformational ensembles, generated by the program ZIBMol. (2) The degree of similarity may vary considerably among the molecules. This problem is addressed by searching for similar substructures present in arbitrary subsets of the given set of molecules. The algorithm requires to preselect a reference molecule. All molecules are compared to this reference molecule. For this pairwise comparison we use a two-step approach. Clique detection on the correspondence graph of the molecular structures is used to generate start transformations, which are then iteratively improved to compute large common substructures. The results of the pairwise comparisons are efficiently merged using binary matching trees. All common substructures that were found, whether they are common to all or only a few molecules, are ranked according to different criteria, such as number of molecules containing the substructure, size of substructure, and geometric fit. For evaluating the geometric fit, we extend a known scoring function by introducing weights which allow to favor potential pharmacophore points. Despite considering the full atomic information for identifying multiple structural similarities, our algorithm is quite fast. Thus it is well suited as an interactive tool for the exploration of structural similarities of drug-sized molecules. T3 - ZIB-Report - 04-52 KW - pharmaceutical drug design KW - multiple superposition KW - semi-flexible alignment KW - clique detection KW - iterative closest point KW - matching tree Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8278 ER - TY - GEN A1 - Bosse, Hartwig A1 - Grötschel, Martin A1 - Henk, Martin T1 - Polynomial Inequalities Representing Polyhedra N2 - Our main result is that every $n$-dimensional polytope can be described by at most $2n-1$ polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an $n$-dimensional pointed polyhedral cone we prove the bound $2n-2$ and for arbitrary polyhedra we get a constructible representation by $2n$ polynomial inequalities. T3 - ZIB-Report - 04-53 KW - polyhedra and polytopes KW - semi-algebraic sets KW - polyhedral combinatorics KW - polynomial inequalities KW - stability index Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8284 ER - TY - GEN A1 - Hodoroaba, Lavinia A1 - Imhof, Andres A1 - Malo, Markus T1 - Das Profil des KOBV-Portals N2 - Zahlreiche lokale, nationale und internationale Informationsportale existieren mit zum Teil gleichen Angeboten und Dienstleistungen nebeneinander. Da der Aufbau und Betrieb von Portalen kostspielig ist, sollten die einzelnen Dienstleistungen abgestimmt und sinnvoll untereinander vernetzt werden. Für eine solch anzustrebende Kooperation unter Portalen ist es notwendig, ein jeweils eigenes Portalprofil zu definieren, um bei einer Gegenüberstellung der Profile die Abgrenzungen und Verknüpfungspunkte deutlich werden zu lassen. Die KOBV-Zentrale möchte mit der Profilbeschreibung des KOBV-Portals beginnen und so die eigenen Angebote des regionalen Portals mit denen anderer auf sinnvolle Weise verknüpfen. Für diese Positionsbestimmung werden die Dienstleistungen, die Zielgruppe, die Kriterien für die Ressourcenauswahl sowie die Abgrenzung zu anderen Portalen dargelegt. T3 - ZIB-Report - 04-54 KW - Informationsportal KW - Portal KW - Verbundportal KW - Digibib KW - Profilbeschreibung KW - Sammelprofil KW - KOBV-Suchmaschine KW - Digitale Bibliothek Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8292 ER - TY - GEN A1 - Erdmann, Bodo A1 - Lang, Jens A1 - Matera, Sebastian A1 - Wilmanski, Krzysztof T1 - Adaptive Linearly Implicit Methods for Linear Poroelastic Equations N2 - Adaptive numerical methods in time and space are introduced and studied for linear poroelastic models in two and three space dimensions. We present equivalent models for linear poroelasticity and choose both the {\em displacement--pressure} and the {\em stress--pressure} formulation for our computations. Their discretizations are provided by means of linearly implicit schemes in time and linear finite elements in space. Our concept of adaptivity opens a way to a fast and reliable simulation of different loading cases defined by corresponding boundary conditions. We present some examples using our code {\sf Kardos} and show that the method works efficiently. In particular, it could be used in the simulation of some bone healing models. T3 - ZIB-Report - 06-37 KW - Poroelasticity KW - Biot's model KW - bone healing KW - adaptive finite elements KW - adaptive time integration KW - Rosenbrock methods Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9312 ER - TY - GEN A1 - Stephan, Rüdiger T1 - Facets of the (s,t)-p-path polytope N2 - \noindent We give a partial description of the $(s,t)-p$-path polytope of a directed graph $D$ which is the convex hull of the incidence vectors of simple directed $(s,t)$-paths in $D$ of length $p$. First, we point out how the $(s,t)-p$-path polytope is located in the family of path and cycle polyhedra. Next, we give some classes of valid inequalities which are very similar to inequalities which are valid for the $p$-cycle polytope, that is, the convex hull of the incidence vectors of simple cycles of length $p$ in $D$. We give necessary and sufficient conditions for these inequalities to be facet defining. Furthermore, we consider a class of inequalities that has been identifie d to be valid for $(s,t)$-paths of cardinality at most $p$. Finally, we transfer the results to related polytopes, in particular, the undirected counterpart of the $(s,t)-p$-path polytope. T3 - ZIB-Report - 06-38 Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9328 ER - TY - GEN A1 - Weber, Marcus A1 - Walter, Lionel A1 - Kube, Susanna A1 - Deuflhard, Peter T1 - Stable computation of probability densities for metastable dynamical systems N2 - Whenever the invariant stationary density of metastable dynamical systems decomposes into almost invariant partial densities, its computation as eigenvector of some transition probability matrix is an ill-conditioned problem. In order to avoid this computational difficulty, we suggest to apply an aggregation/disaggregation method which only addresses wellconditioned sub-problems and thus results in a stable algorithm. In contrast to existing methods, the aggregation step is done via a sampling algorithm which covers only small patches of the sampling space. Finally, the theoretical analysis is illustrated by two biomolecular examples. T3 - ZIB-Report - 06-39 KW - dynamical systems KW - metastability KW - molecular conformations KW - cluster analysis KW - sampling KW - aggregation/disaggregation KW - domain decomposition Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9331 ER - TY - GEN A1 - Lügger, Joachim T1 - Neustart für Bibliotheken ins Informationszeitalter N2 - Wir erleben zu Beginn des aufkommenden Informationszeitalters mit dem Siegeszug von Google und anderen Internet-Technologien einen Wandel im Verhalten von Wissenschaftlern und Studenten, der mit dem Einsatz von {\sl Google Scholar} und {\sl Google Book Search} einen Paradigmenwechsel für Bibliotheken und Informationsversorger gleichkommt. Der Artikel untersucht die technischen Hintergründe für den Erfolg dieser besonderen Art des Information Retrievals: Fulltext Indexing und Citation Ranking als besondere Form des Information Minig. Er diskutiert Stärken und auch Schwächen des Google-Ansatzes. Der Autor stellt sich auch der Frage, unter welchen Bedingungen es möglich ist, ein zu {\sl Google Scholar} und der {\sl Google Book Search} konkurrenzfähiges Retrieval in der Landschaft der Bibliotheken und Bibliotheksverbünde zu entrichten. Die These ist, dass dieses unter Einsatz des {\sl Open Source} Indexierers {\sl Lucene} und des Web-Robots {\sl Nutch} möglich ist. Bibliotheken können durch gezielten Einsatz solcher Internet-Technologien dem Nutzer die Leistungen, welche Google uns mit seinen Tools im {\sl Visible Web} und mit Referenzen auf {\sl Citations} in der Welt der Literatur zur Verfügung stellt, in vergleichbarer Art auch für ihre eigenen durch Lizenzen geschützten digitalen Journale und ihre speziellen lokal verfügbaren Ressourcen, auf die Internet-Suchmaschinen keine Zugriff haben, anbieten. Es besteht die Hoffnung, dass Nutzer dann nicht - wie in einer kürzlichen Studie des OCLC konstatiert - überwiegend im Internet verbleiben, sondern bei ihrer Suche auch den Weg zu den Angeboten der örtlichen Bibliothek attraktiv finden. T3 - ZIB-Report - 06-40 KW - Information Retrieval KW - Volltextindizierung KW - Citation-Ranking KW - Suchmaschinen Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9347 ER - TY - GEN A1 - Schiela, Anton T1 - A continuity result for Nemyckii Operators and some applications in PDE constrained optimal control N2 - This work explores two applications of a classical result on the continuity of Nemyckii operators to optimal control with PDEs. First, we present an alternative approach to the analysis of Newton's method for function space problems involving semi-smooth Nemyckii operators. A concise proof for superlinear convergence is presented, and sharpened bounds on the rate of convergence are derived. Second, we derive second order sufficient conditions for problems, where the underlying PDE has poor regularity properties. We point out that the analytical structure in both topics is essentially the same. T3 - ZIB-Report - 06-41 KW - continuity of Nemyckii Operators KW - Newton methods in function space KW - optimal control KW - second order sufficient conditions Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9354 ER - TY - GEN A1 - Deuflhard, Peter A1 - Krause, Rolf A1 - Ertel, Susanne T1 - A Contact-Stabilized Newmark Method for Dynamical Contact Problems N2 - The numerical integration of dynamical contact problems often leads to instabilities at contact boundaries caused by the non-penetration condition between bodies in contact. Even a recent energy dissipative modification due to Kane et al. (1999), which discretizes the non-penetration constraints implicitly, is not able to circumvent artificial oscillations. For this reason, the present paper suggests a contact stabilization which avoids artificial oscillations at contact interfaces and is also energy dissipative. The key idea of this contact stabilization is an additional $L^2$-projection at contact interfaces, which can easily be added to any existing time integration scheme. In case of a lumped mass matrix, this projection can be carried out completely locally, thus creating only negligible additional numerical cost. For the new scheme, an elementary analysis is given, which is confirmed by numerical findings in an illustrative test example (Hertzian two body contact). T3 - ZIB-Report - 06-42 KW - Numerical problems in dynamical systems KW - nonlinear stabilities Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9361 ER - TY - GEN A1 - Harks, Tobias T1 - Nash Equilibria in Online Sequential Routing Games N2 - In this paper, we study the efficiency of Nash equilibria for a sequence of nonatomic routing games. We assume that the games are played consecutively in time in an online fashion: by the time of playing game $i$, future games $i+1,\dots,n$ are not known, and, once players of game $i$ are in equilibrium, their corresponding strategies and costs remain fixed. Given a sequence of games, the cost for the sequence of Nash equilibria is defined as the sum of the cost of each game. We analyze the efficiency of a sequence of Nash equilibria in terms of competitive analysis arising in the online optimization field. Our main result states that the online algorithm $\sl {SeqNash}$ consisting of the sequence of Nash equilibria is $\frac{4n}{2+n}$-competitive for affine linear latency functions. For $n=1$, this result contains the bound on the price of anarchy of $\frac{4}{3}$ for affine linear latency functions of Roughgarden and Tardos [2002] as a special case. Furthermore, we analyze a problem variant with a modified cost function that reflects the total congestion cost, when all games have been played. In this case, we prove an upper bound of $\frac{4n}{2+n}$ on the competitive ratio of $\sl {SeqNash}$. We further prove a lower bound of $\frac{3n-2}{n}$ of $\sl {SeqNash}$ showing that for $n=2$ our upper bound is tight. T3 - ZIB-Report - 06-43 KW - Congestion Game KW - Online Optimization KW - Nash equilibria Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9376 ER - TY - GEN A1 - Lopez-Fernandez, Maria A1 - Lubich, Christian A1 - Schädle, Achim T1 - Adaptive, Fast and Oblivious Convolution in Evolution Equations with Memory N2 - To approximate convolutions which occur in evolution equations with memory terms, a variable-stepsize algorithm is presented for which advancing $N$ steps requires only $O(N\log N)$ operations and $O(\log N)$ active memory, in place of $O(N^2)$ operations and $O(N)$ memory for a direct implementation. A basic feature of the fast algorithm is the reduction, via contour integral representations, to differential equations which are solved numerically with adaptive step sizes. Rather than the kernel itself, its Laplace transform is used in the algorithm. The algorithm is illustrated on three examples: a blow-up example originating from a Schrödinger equation with concentrated nonlinearity, chemical reactions with inhibited diffusion, and viscoelasticity with a fractional order constitutive law. T3 - ZIB-Report - 06-45 KW - convolution quadrature KW - adaptivity KW - Volterra integral equations KW - numerical inverse Laplace transform KW - anomalous diffusion KW - fractional order visco Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9399 ER - TY - GEN A1 - Brandt, Andreas A1 - Brandt, Manfred T1 - Waiting times for M/M systems under generalized processor sharing N2 - We consider a system where the arrivals form a Poisson process and the required service times of the requests are exponentially distributed. According to the generalized processor sharing discipline, each request in the system receives a fraction of the capacity of one processor which depends on the actual number of requests in the system. We derive systems of ordinary differential equations for the LST and for the moments of the conditional waiting time of a request with given required service time as well as a stable and fast recursive algorithm for the LST of the second moment of the conditional waiting time, which in particular yields the second moment of the unconditional waiting time. Moreover, asymptotically tight upper bounds for the moments of the conditional waiting time are given. The presented numerical results for the first two moments of the sojourn times in the $M/M/m-PS$ system show that the proposed algorithms work well. T3 - ZIB-Report - 06-46 KW - Poisson arrivals KW - exponential service times KW - generalized processor sharing KW - many-server KW - permanent customers KW - M/M/m-PS KW - waiting time KW - sojourn t Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9404 ER - TY - GEN A1 - Kröller, Alexander A1 - Wessäly, Roland T1 - Integrated Optimization of Hardware Configuration and Capacity. Dimensioning in SDH and opaque WDM networks N2 - We suggest a new model for the design of telecommunication networks which integrates decisions about the topology, configuration of the switching hardware, link dimensioning, and protected routing of communication demands. Applying the branch-and-cut-algorithm implemented in our network planning and optimization tool DISCNET, we demonstrate that real-world based network planning instances of such an enhanced model can be solved. T3 - ZIB-Report - 03-49 KW - Survivable Network Design KW - Integer Programming KW - Hardware Configuration KW - Routing KW - Network Models KW - Network Planning KW - Resource Allocation KW - Surviva Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7714 ER - TY - GEN A1 - Koch, Thorsten T1 - Verteilter Dokumenten-Speicher, Erfahrungen mit den Kluwer-Daten des Friedrich-Althoff-Konsortiums N2 - Dieser Bericht beschreibt die Erfahrungen und Schlussfolgerungen,die im Rahmen der VDS-Vorstudie bei der Speicherung der vom Friedrich-Althoff-Konsortium lizenzierten Zeitschriften des Kluwer-Verlages gewonnen wurden. T3 - ZIB-Report - 03-50 KW - Dokumentenspeicherung KW - Metadaten Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7726 ER - TY - GEN A1 - Lügger, Joachim T1 - Vorhaben: Offene Navigation und Suchmaschinen in Verbünden, Konsortien und den Wissenschaften; Schlussbericht zumTeilprojekt des BMBF-Vorhabens: Kompetenznetzwerk NeueDienste, Standardisierung, Metadaten. N2 - Die harmonische Integration der Navigation und Suche in lizenzierten Journalen und gleichzeitig in freien digitalen Dokumenten unter einer einheitlichen konsistenten Nutzeroberflache ist eines der ungelösten F&E-Probleme der Fachinformation. Hierfür sollen Elemente des Invisible Web und des Visible Web unter Berücksichtigung offener Standards nahtlos #I miteinander verbunden werden. Dem Projekt liegt ein Modell mit Internet-Index, Metasuche und Open Linking über verteilten heterogenen Speichern #I zu Grunde: Verschiedenste Server, digitale Referenzen in Artikeln und Dokumenten, Links in Datenbanken und auf Bestelldienste sollen unter Berücksichtigung von Standort-, Studien- und Lernbedingungen kooperativ miteinander vernetzt werden. Die Leistungsfähigkeit des Modells soll in Pilotimplementierungen getestet und für eine breite Anwendung vorbereitet werden. Auf dieser Basis soll das Vorhaben Verteilter Zeitschriftenserver der AG der Verbundsysteme in eigenen Teilprojekten kooperativ initiiert werden, das jetzt in das Vorhaben Verteilter Dokumentenserver von vascoda integriert ist. T3 - ZIB-Report - 03-51 KW - Metasuchmaschine KW - Internet-Suchmaschinen KW - kontextsensitives Linking KW - OpenURL KW - Verteilter Zeitschriftenserver KW - Verteilter Dokumentenserver KW - Virtu Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7737 ER - TY - GEN A1 - Nowak, Ulrich A1 - Grah, Aleksander A1 - Schreier, Manfred T1 - Parameter Estimation and Accuracy Matching Strategies for 2-D Reactor Models N2 - The mathematical modeling of a special modular catalytic reactor kit leads to a system of partial differential equation in two space dimensions. As customary, this model contains unconfident physical parameters, which may be adapted to fit experimental data. To solve this nonlinear least squares problem we apply a damped Gauss-Newton method. A method of lines approach is used to evaluate the associated model equations. By an a priori spatial discretization a large DAE system is derived and integrated with an adaptive, linearly-implicit extrapolation method. For sensitivity evaluation we apply an internal numerical differentiation technique, which reuses linear algebra information from the model integration. In order not to interfere the control of the Gauss-Newton iteration these computations are done usually very accurately and, therefore, very costly. To overcome this difficulty, we discuss several accuracy adaptation strategies, e.g., a master-slave mode. Finally, we present some numerical experiments. T3 - ZIB-Report - 03-52 KW - parameter estimation KW - accuracy matching KW - method of lines KW - differential-algebraic systems KW - extrapolation methods KW - catalytic reactor models Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7749 ER - TY - GEN A1 - Baum, Daniel T1 - Finding All Maximal Cliques of a Family of Induced Subgraphs N2 - Many real world problems can be mapped onto graphs and solved with well-established efficient algorithms studied in graph theory. One such problem is to find large sets of points satisfying some mutual relationship. This problem can be transformed to the problem of finding all cliques of an undirected graph by mapping each point onto a vertex of the graph and connecting any two vertices by an edge whose corresponding points satisfy our desired relationship. Clique detection has been widely studied and there exist efficient algorithms. In this paper we study a related problem, where all points have a set of binary attributes, each of which is either 0 or 1. This is only a small limitation, since all discrete properties can be mapped onto binary attributes. In our case, we want to find large sets of points not only satisfying some mutual relationship; but, in addition, all points of a set also need to have at least one common attribute with value 1. The problem we described can be mapped onto a set of induced subgraphs, where each subgraph represents a single attribute. For attribute $i$, its associated subgraph contains those vertices corresponding to the points with attribute $i$ set to 1. We introduce the notion of a maximal clique of a family, $\mathcal{G}$, of induced subgraphs of an undirected graph, and show that determining all maximal cliques of $\mathcal{G}$ solves our problem. Furthermore, we present an efficient algorithm to compute all maximal cliques of $\mathcal{G}$. The algorithm we propose is an extension of the widely used Bron-Kerbosch algorithm. T3 - ZIB-Report - 03-53 KW - Bron-Kerbosch algorithm KW - maximal cliques KW - vertex properties KW - family of induced subgraphs KW - backtracking algorithm KW - branch and bound technique KW - re Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7758 ER - TY - GEN A1 - Deuflhard, Peter A1 - (Chairs), Hyung Yong Ra T1 - Korean-German Bilateral Symposium on Scientific Computing N2 - Collection of abstracts of the Korean-German Bilateral Symposium on Scientific Computing, Berlin January 15/16, 2004 T3 - ZIB-Report - 04-02 KW - Abstracts Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7778 ER - TY - GEN A1 - Weber, Marcus T1 - Clustering by using a simplex structure N2 - In this paper we interpret clustering as a mapping of data into a simplex. If the data itself has simplicial struture this mapping becomes linear. Spectral analysis is an often used tool for clustering data. We will show that corresponding singular vectors or eigenvectors comprise simplicial structure. Therefore they lead to a cluster algorithm, which consists of a simple linear mapping. An example for this kind of algorithms is the Perron cluster analysis (PCCA). We have applied it in practice to identify metastable sets of molecular dynamical systems. In contrast to other algorithms, this kind of approach provides an a priori criterion to determine the number of clusters. In this paper we extend the ideas to more general problems like clustering of bipartite graphs. T3 - ZIB-Report - 04-03 KW - cluster algorithms KW - Perron cluster analysis KW - stochastic matrices KW - bipartite graphs Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7782 ER - TY - GEN A1 - Bley, Andreas A1 - Koch, Thorsten A1 - Wessäly, Roland T1 - Large-scale hierarchical networks: How to compute an optimal architecture? N2 - In this article, we present a mathematical model and an algorithm to support one of the central strategic planning decisions of network operators: How to organize a large number of locations into a hierarchical network? We propose a solution approach that is based on mixed-integer programming and Lagrangian relaxation techniques. As major advantage, our approach provides not only solutions but also worst-case quality guarantees. Real-world scenarios with more than 750 locations have been solved within 30 minutes to less than 1\% off optimality. T3 - ZIB-Report - 04-04 KW - Hierarchical Networks KW - Mixed-Integer Programming KW - Lagrangian Relaxation Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7799 ER - TY - GEN A1 - Helmes, Kurt A1 - Röhl, Stefan T1 - A Geometrical Characterization of the Multidimensional Hausdorff and Dale Polytopes with Applications to Exit Time Problems N2 - We present formulae for the corner points of the multidimensional Hausdorff and Dale Polytopes and show how these results can be used to improve linear programming models for computing e.\,g.\ moments of exit distribution of diffusion processes. Specifically, we compute the mean exit time of twodimensional Brownian motion from the unit square and the unit triangle, as well as higher moments of the exit time of time space Brownian motion from a triangle. T3 - ZIB-Report - 04-05 KW - linear programming KW - special polytopes KW - moment problems KW - Brownian motion on a triangle KW - numerical methods for exit time problems Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7807 ER - TY - GEN A1 - Lutz-Westphal, Brigitte T1 - Die Mathematik der kürzesten Wege. Inhalte und Methoden für den Unterricht N2 - Wie findet man den optimalen Weg im U-Bahnnetz? Das Problem wird als Graph modelliert und dann eine Breitensuche durchgeführt. Will man Weglängen oder Fahrzeiten mitberücksichtigen, so braucht man den Algorithmus von Dijkstra für gewichtige Graphen. Beim Nachdenken über diese Algorithmen werden auch Fragestellungen der Graphentheorie berührt. In einem zweiten Abschnitt werden methodische Hinweise für den Unterricht in der Sekundarstufe I und II gegeben, insbesondere, wie man Lernende dazu bringen kann, ihre Ideen für Algorithmen präzise zu analysieren und zu Papier zu bringen. T3 - ZIB-Report - 04-36 KW - Schule KW - Unterricht KW - Graphenalgorithmen KW - Graphen KW - Unterrichtsmethoden Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8116 ER - TY - GEN A1 - Joswig, Michael A1 - Pfetsch, Marc T1 - Computing Optimal Morse Matchings N2 - Morse matchings capture the essential structural information of discrete Morse functions. We show that computing optimal Morse matchings is NP-hard and give an integer programming formulation for the problem. Then we present polyhedral results for the corresponding polytope and report on computational results. T3 - ZIB-Report - 04-37 KW - discrete Morse function KW - Morse matching Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8120 ER - TY - GEN A1 - Weber, Marcus A1 - Rungsarityotin, Wasinee A1 - Schliep, Alexander T1 - Perron Cluster Analysis and Its Connection to Graph Partitioning for Noisy Data N2 - The problem of clustering data can be formulated as a graph partitioning problem. Spectral methods for obtaining optimal solutions have reveceived a lot of attention recently. We describe Perron Cluster Cluster Analysis (PCCA) and, for the first time, establish a connection to spectral graph partitioning. We show that in our approach a clustering can be efficiently computed using a simple linear map of the eigenvector data. To deal with the prevalent problem of noisy and possibly overlapping data we introduce the min Chi indicator which helps in selecting the number of clusters and confirming the existence of a partition of the data. This gives a non-probabilistic alternative to statistical mixture-models. We close with showing favorable results on the analysis of gene expressi on data for two different cancer types. T3 - ZIB-Report - 04-39 KW - Perron cluster analysis KW - spectral graph theory KW - clustering KW - gene expression Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8140 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Provably Good Solutions for Wavelength Assignment in Optical Networks N2 - In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formula tion by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation approach. Computational experiments show that the value of the linear relaxation states a good lower bound and can often prove optimality of the best solution generated heuristically. T3 - ZIB-Report - 04-40 KW - wavelength assignment KW - integer programming KW - column generation Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8155 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks N2 - In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of the most promising formulation. In many cases, a non-zero lower bound on the number of required converters is generated this way. For several instances, we in fact prove optimality since the lower bound equals the best known solution value. T3 - ZIB-Report - 04-41 KW - optical networks KW - wavelength assignment KW - integer programming Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8160 ER - TY - GEN A1 - Koch, Thorsten A1 - Wessäly, Roland T1 - Hierarchical Infrastructure Planning in Networks N2 - In this article, strategical infrastructure planning problems in the design of large-scale telecommunication networks are discussed based on experiences from three projects with industrial partners: The access network planning of the German Gigabit-Wissenschaftsnetz (G-WiN) for DFN (Verein zur Förderung eines Deutschen Forschungsnetzes e.V.), the mobile network switching center location planning project for E-Plus Mobilfunk, and the fixed network switching center location planning project for TELEKOM AUSTRIA. We introduce a mathematical model for a hierarchical multi-commodity capacitated facility location problem, present adaptions of this basic model to the specific requirements within the different projects and discuss the individual peculiarities and model decisions made. Eventually, we present and discuss computational results of three associated case studies, illustrating '"how we did the job`` with mathematical methods. T3 - ZIB-Report - 04-42 KW - Facility Location KW - Telecommunication KW - Mixed Integer Programming Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8174 ER - TY - GEN A1 - Wolle, Thomas A1 - Koster, Arie M.C.A. A1 - Bodlaender, Hans L. T1 - A Note on Contraction Degeneracy N2 - The parameter contraction degeneracy -- the maximum minimum degree over all minors of a graph -- is a treewidth lower bound and was first defined in (Bodlaender, Koster, Wolle, 2004). In experiments it was shown that this lower bound improves upon other treewidth lower bounds. In this note, we examine some relationships between the contraction degeneracy and connected components of a graph, block s of a graph and the genus of a graph. We also look at chordal graphs, and we study an upper bound on the contraction degeneracy and another lower bound for treewidth. A data structure that can be used for algorithms computing the degeneracy and similar parameters, is also described. T3 - ZIB-Report - 04-43 KW - contraction degeneracy KW - genus of a graph KW - treewidth lower bounds Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8180 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Wolle, Thomas A1 - Bodlaender, Hans L. T1 - Degree-Based Treewidth Lower Bounds N2 - Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving treewidth lower bounds. In this paper, we investigate a total of nine graph parameters, providing lower bounds for treewidth. The parameters have in common that they all are the vertex-degree of some vertex in a subgra ph or minor of the input graph. We show relations between these graph parameters and study their computational complexity. To allow a practical comparison of the bounds, we developed heuristic algorithms for those parameters that are NP-hard to compute. Computational experiments show that combining the treewidth lower bounds with minors can considerably improve the lower bounds. T3 - ZIB-Report - 04-44 KW - contraction degeneracy KW - Ramachandramurthi parameter KW - treewidth lower bounds Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8193 ER - TY - GEN A1 - Bodlaender, Hans L. A1 - Koster, Arie M.C.A. T1 - On the Maximum Cardinality Search Lower Bound for Treewidth N2 - The Maximum Cardinality Search algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbors becomes visited. An MCS-ordering of a graph is an ordering of the vertices that can be generated by the Maximum Cardinality Search algorithm. The visited degree of a vertex $v$ in an MCS-ordering is the number of neighbors of $v$ that are before $v$ in the ordering. The visited degree of an MCS-ordering $\psi$ of $G$ is the maximum visited degree over all vertices $v$ in $\psi$. The maximum visited degree over all MCS-orderings of graph $G$ is called its {\em maximum visited degree}. Lucena (2003) showed that the treewidth of a graph $G$ is at least its maximum visited degree. We show that the maximum visited degree is of size $O(\log n)$ for planar graphs, and give examples of planar graphs $G$ with maximum visited degree $k$ with $O(k!)$ vertices, for all $k\in \Bbb{N}$. Given a graph $G$, it is NP-complete to determine if its maximum visited degree is at least $k$, for any fixed $k\geq 7$. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete. We also propose and experimentally analyses some heuristics for the problem. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications. T3 - ZIB-Report - 04-45 KW - maximum cardinality search KW - treewidth KW - lower bounds KW - planar graphs KW - graph algorithms Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8201 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Koster, Arie M.C.A. A1 - Raack, Christian A1 - Wessäly, Roland T1 - Two-layer Network Design by Branch-and-Cut featuring MIP-based Heuristics N2 - This paper deals with MIP-based primal heuristics to be used within a branch-and-cut approach for solving multi-layer telecommunication network design problems. Based on a mixed-integer programming formulation for two network layers, we present three heuristics for solving important subproblems, two of which solve a sub-MIP. On multi-layer planning instances with many parallel logical links, we show the effectiveness of our heuristics in finding good solutions early in the branch-and-cut search tree. T3 - ZIB-Report - 06-47 KW - multi-layer network design KW - integer programming KW - branch-and-cut KW - heuristics Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9412 ER - TY - GEN A1 - Kaibel, Volker A1 - Peinhardt, Matthias A1 - Pfetsch, Marc T1 - Orbitopal Fixing N2 - The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the permutation of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up the branch-and-cut tree. We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving this kind of symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the branch-and-cut tree, removes redundant parts of the tree produced by the above mentioned permutations. The method relies on certain polyhedra, called orbitopes, which have been investigated in (Kaibel and Pfetsch (2006)). However, it does not add inequalities to the model, and thus, it does not increase the difficulty of solving the linear programming relaxations. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem motivated from frequency planning in mobile telecommunication networks. T3 - ZIB-Report - 06-48 KW - symmetry breaking KW - variable fixing KW - orbitopes Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9422 ER - TY - GEN A1 - Deuflhard, Peter A1 - Erdmann, Bodo A1 - Roitzsch, Rainer A1 - Lines, Glenn Terje T1 - Adaptive Finite Element Simulation of Ventricular Fibrillation Dynamics N2 - The dynamics of ventricular fibrillation caused by irregular excitation is simulated in the frame of the monodomain model with an action potential model due to Aliev-Panfilov for a human 3D geometry. The numerical solution of this multiscale reaction-diffusion problem is attacked by algorithms which are fully adaptive in both space and time (code library {\sc Kardos}). The obtained results clearly demonstrate an accurate resolution of the cardiac potential during the excitation and the plateau phases (in the regular cycle) as well as after a reentrant excitation (in the irregular cycle). T3 - ZIB-Report - 06-49 KW - reaction-diffusion equations KW - Aliev-Panfilov model KW - electrocardiology KW - adaptive finite elements KW - adaptive time integration KW - adaptive Rothe method Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9431 ER - TY - GEN A1 - Weber, Marcus A1 - Kube, Susanna A1 - Riemer, Alexander A1 - Bujotzek, Alexander T1 - Efficient Sampling of the Stationary Distribution of Metastable Dynamical Systems N2 - In this article we aim at an efficient sampling of the stationary distribution of dynamical systems in the presence of metastabilities. In the past decade many sophisticated algorithms have been inven ted in this field. We do not want to simply add a further one. We address the problem that one has applied a sampling algorithm for a dynamical system many times. This leads to different samplings which more or less represent the stationary distribution partially very well, but which are still far away from ergodicity or from the global stationary distribution. We will show how these samplings can be joined together in order to get one global sampling of the stationary distribution. T3 - ZIB-Report - 07-03 KW - dynamical systems KW - stationary distribution KW - rare events KW - metastability KW - cluster analysis Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9467 ER - TY - GEN A1 - Deuflhard, Peter A1 - Huisinga, Wilhelm A1 - Jahnke, Tobias A1 - Wulkow, Michael T1 - Adaptive Discrete Galerkin Methods Applied to the Chemical Master Equation N2 - \begin{abstract} In systems biology, the stochastic description of biochemical reaction kinetics is increasingly being employed to model gene regulatory networks and signalling pathways. Mathematically speaking, such models require the numerical solution of the underlying evolution equat ion, also known as the chemical master equation (CME). Up to now, the CME has almost exclusively been treated by Monte-Carlo techniques, the most prominent of which is the simulation algorithm suggest ed by Gillespie in 1976. Since this algorithm requires an update for each single reaction event, realizations can be computationally very costly. As an alternative, we here propose a novel approach, which focuses on the discrete partial differential equation (PDE) structure of the CME and thus allows to adopt ideas from adaptive discrete Galerkin methods (as designed by two of the present authors in 1989), which have proven to be highly efficient in the mathematical modelling of polyreaction kinetics. Among the two different options of discretizing the CME as a discrete PDE, the method of lines approach (first space, then time) and the Rothe method (first time, then space), we select the latter one for clear theoretical and algorithmic reasons. First numeric al experiments at a challenging model problem illustrate the promising features of the proposed method and, at the same time, indicate lines of necessary further research. \end{abstract} T3 - ZIB-Report - 07-04 KW - adaptive discrete Galerkin methods KW - adaptive Rothe method KW - discrete Chebyshev polynomials KW - stochastic reactions kinetics KW - chemical master equation Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9471 ER - TY - GEN A1 - Jokar, Sadegh A1 - Pfetsch, Marc T1 - Exact and Approximate Sparse Solutions of Underdetermined Linear Equations N2 - In this paper, we empirically investigate the NP-hard problem of finding sparse solutions to linear equation systems, i.e., solutions with as few nonzeros as possible. This problem has received considerable interest in the sparse approximation and signal processing literature, recently. We use a branch-and-cut approach via the maximum feasible subsystem problem to compute optimal solutions for small instances and investigate the uniqueness of the optimal solutions. We furthermore discuss five (modifications of) heuristics for this problem that appear in different parts of the literature. For small instances, the exact optimal solutions allow us to evaluate the quality of the heuristics, while for larger instances we compare their relative performance. One outcome is that the basis pursuit heuristic performs worse, compared to the other methods. Among the best heuristics are a method due to Mangasarian and a bilinear approach. T3 - ZIB-Report - 07-05 KW - sparse representations KW - basis pursuit KW - orthogonal matching pursuit KW - maximum feasible subsystem problem Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9488 ER - TY - GEN A1 - Imhof, Andres T1 - Zweieinhalb Jahre Open-Linking im KOBV-Portal: Ein Erfahrungsbericht N2 - Die Zentrale des Kooperativen Bibliotheksverbunds Berlin-Brandenburg (KOBV) betreibt seit Januar 2004 das KOBV-Portal, in dem u.a. vielfältige Open-Linking-Dienste eingebunden sind. Dieser Beitrag erläutert Open-Linking allgemein und stellt die KOBV spezifischen Dienste im Detail vor. Dabei wird auch die Zugriffsentwicklung auf die KOBV-Open-Linking-Dienste evaluiert. Ein Ergebnis ist, dass signifikante Steigerungen der Nutzung erst dann bewirkt werden, wenn Maßnahmen durchgeführt werden, die erstens die Open-Linking-Dienste stärker ins Bewusstsein der NutzerInnen rücken und zweitens den Weg dorthin im KOBV-Portal verkürzen. Vor allem muss ein schneller Weg zu den Open-Linking-Diensten gewährleistet sein, um die Nutzung deutlich zu steigern. Um zusätzlich den Bekanntheitsgrad der Open-Linking-Dienste bundesweit zu erhöhen, regt die KOBV-Zentrale andere Bibliotheken und Verbünde dazu an, analoge Open-Linking-Dienste einzurichten. Auf diese Weise wird die Handhabung von Open-Linking selbstverständlicher. T3 - ZIB-Report - 07-06 KW - Open-Linking KW - Reference-Linking KW - kontextsensitives Linking KW - KOBV-Portal KW - KOBV-Dienste Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9499 ER - TY - GEN A1 - Lutz, Frank H. T1 - Enumeration and Random Realization of Triangulated Surfaces N2 - We discuss different approaches for the enumeration of triangulated surfaces. In particular, we enumerate all triangulated surfaces with 9 and 10 vertices. We also show how geometric realizations of orientable surfaces with few vertices can be obtained by choosing coordinates randomly. T3 - ZIB-Report - 06-07 KW - triangulated surfaces KW - polyhedral manifolds Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9012 ER - TY - GEN A1 - Lutz, Frank H. T1 - Triangulated Manifolds with Few Vertices: Combinatorial Manifolds N2 - In this survey on combinatorial properties of triangulated manifolds we discuss various lower bounds on the number of vertices of simplicial and combinatorial manifolds. Moreover, we give a list of all known examples of vertex-minimal triangulations. T3 - ZIB-Report - 06-08 KW - triangulated manifolds KW - combinatorial properties KW - minimal triangulations Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9028 ER - TY - GEN A1 - Köhler, Ekkehard G. A1 - Lutz, Frank H. T1 - Triangulated Manifolds with Few Vertices: Vertex-Transitive Triangulations I N2 - We describe an algorithm for the enumeration of (candidates of) vertex-transitive combinatorial $d$-manifolds. With an implementation of our algorithm, we determine, up to combinatorial equivalence, all combinatorial manifolds with a vertex-transitive automorphism group on $n\leq 13$ vertices. With the exception of actions of groups of small order, the enumeration is extended to 14 and 15 vertices. T3 - ZIB-Report - 06-09 KW - triangulated manifolds KW - vertex-transitive triangulations Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9031 ER - TY - GEN A1 - Csorba, Peter A1 - Lutz, Frank H. T1 - Graph Coloring Manifolds N2 - We introduce a new and rich class of graph coloring manifolds via the Hom complex construction of Lov\´{a}sz. The class comprises examples of Stiefel manifolds, series of spheres and products of spheres, cubical surfaces, as well as examples of Seifert manifolds. Asymptotically, graph coloring manifolds provide examples of highly connected, highly symmetric manifolds. T3 - ZIB-Report - 06-11 KW - graph coloring complexes KW - Hom complexes KW - flag complexes KW - graph coloring manifolds Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9043 ER - TY - GEN A1 - Hougardy, Stefan A1 - Lutz, Frank H. A1 - Zelke, Mariano T1 - Polyhedra of Genus 2 with 10 Vertices and Minimal Coordinates N2 - We give coordinate-minimal geometric realizations in general position of all 865 vertex-minimal triangulations of the orientable surface of genus 2 in the 4x4x4-cube. T3 - ZIB-Report - 06-12 KW - triangulated surfaces KW - minimal triangulations KW - polyhedral realizations Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9054 ER - TY - GEN A1 - Hougardy, Stefan A1 - Lutz, Frank H. A1 - Zelke, Mariano T1 - Polyhedra of Genus 3 with 10 Vertices and Minimal Coordinates N2 - We give coordinate-minimal geometric realizations in general position for 17 of the 20 vertex-minimal triangulations of the orientable surface of genus 3 in the 5x5x5-cube. T3 - ZIB-Report - 06-13 KW - triangulated surfaces KW - minimal triangulations KW - polyhedral realizations Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9064 ER - TY - GEN A1 - Lutz, Frank H. T1 - Combinatorial 3-Manifolds with 10 Vertices N2 - We give a complete enumeration of combinatorial 3-manifolds with 10 vertices: There are precisely 247882 triangulated 3-spheres with 10 vertices as well as 518 vertex-minimal triangulations of the sphere product $S^2 x S^1$ and 615 triangulations of the twisted sphere product $S^2 \underline{x} S^1$. An analysis of the 3-spheres with up to 10 vertices shows that all these spheres are shellable, but that there are 29 vertex-minimal non-shellable 3-balls with 9 vertices. T3 - ZIB-Report - 06-14 KW - triangulated manifolds KW - enumeration KW - minimal triangulations KW - shellability Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9071 ER - TY - GEN A1 - Hülsermann, Ralf A1 - Jäger, Monika A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland A1 - Zymolka, Adrian T1 - Availability and Cost Based Evaluation of Demand-wise Shared Protection N2 - In this paper, we investigate the connection availabilities for the new protection scheme Demand-wise Shared Protection (DSP) and describe an appropriate approach for their computation. The exemplary case study on two realistic network scenarios shows that in most cases the availabilities for DSP are comparable with that for 1+1 path protection and better than in case of shared path protection. T3 - ZIB-Report - 06-15 KW - demand-wise shared protection KW - network availability KW - network optimization Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9080 ER - TY - GEN A1 - Schiela, Anton T1 - Convergence of the Control Reduced Interior Point Method for PDE Constrained Optimal Control with State Constraints N2 - We propose a variant of the control reduced interior point method for the solution of state constrained problems. We show convergence of the corresponding interior point pathfollowing algorithm in function space. Morever, we provide error bounds for the iterates. T3 - ZIB-Report - 06-16 KW - interior point methods in function space KW - optimal control KW - state constraints Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9099 ER - TY - GEN A1 - Kaibel, Volker A1 - Pfetsch, Marc T1 - Packing and Partitioning Orbitopes N2 - We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain insight into ways of breaking certain symmetries in integer programs by adding constraints, e.g., for a well-known formulation of the graph coloring problem. We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining inequalities. For the cyclic group case, the descriptions turn out to be totally unimodular, while for the symmetric group case, both the description and the proof are more involved. The associated separation problems can be solved in linear time. T3 - ZIB-Report - 06-17 KW - integer programming KW - symmetry breaking KW - lexicographic representatives Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9104 ER - TY - GEN A1 - Grötschel, Martin T1 - Das Problem mit der Komplexität: P = NP? N2 - Was Komplexität ist, weiß niemand so richtig. In vielen Wissenschaftsgebieten wird der Begriff Komplexität verwendet, überall mit etwas anderer Bedeutung. Mathematik und Informatik hab en eine eigene Theorie hierzu entwickelt: die Komplexitätstheorie. Sie stellt zwar grundlegende Begriffe bereit, aber leider sind die meisten wichtigen Fragestellungen noch ungelöst. Diese kurze Einführung konzentriert sich auf einen speziellen, aber bedeutenden Aspekt der Theorie: Lösbarkeit von Problemen in deterministischer und nichtdeterministischer polynomialer Zeit. Hinter der für Uneingeweihte etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexitätstheorie. Anhand dieser Fragestellung werden einige Aspekte der Theorie erläutert und formell erklärt, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grundsätzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es für viele Probleme unseres Alltags keine effizienten Lösungsmethoden gibt? T3 - ZIB-Report - 05-58 KW - Komplexität KW - Komplexitätstheorie Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8916 ER -