@misc{Kanaeva2005, author = {Kanaeva, Zara}, title = {Ranking: Google und CiteSeer}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8315}, number = {04-55}, year = {2005}, abstract = {Im Rahmen des klassischen Information Retrieval wurden verschiedene Verfahren f{\"u}r das Ranking sowie die Suche in einer homogenen strukturlosen Dokumentenmenge entwickelt. Die Erfolge der Suchmas chine Google haben gezeigt, dass die Suche in einer zwar inhomogenen aber zusammenh{\"a}ngenden Dokumentenmenge wie dem Internet unter Ber{\"u}cksichtigung der Dokumentenverbindungen (Links) sehr ef fektiv sein kann. Unter den von der Suchmaschine Google realisierten Konzepten ist ein Verfahren zum Ranking von Suchergebnissen (PageRank), das in diesem Artikel kurz erkl{\"a}rt wird. \% Dar{\"u}ber hinaus wird auf die Konzepte eines Systems namens CiteSeer eingegangen, welches automatisch bibliographische Angaben indexiert (engl. \glqq Autonomous Citation Indexing\grqq, ACI). Letzteres erzeugt aus einer Menge von nicht-vernetzten wissenschaftlichen Dokumenten eine zusammenh{\"a}ngende Dokumentenmenge und erm{\"o}glicht den Einsatz von Ranking-Verfahren, die auf den von Google genutzten Verfahren basieren.}, language = {de} } @misc{Kanaeva2005, author = {Kanaeva, Zara}, title = {Verteilter Dokumenten Speicher: Erfahrungen mit der Suchmaschine Fast}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8326}, number = {04-56}, year = {2005}, abstract = {In diesem Bericht wurden Erfahrungen mit der Suchmaschine FAST im Rahmen des Projektes Verteilter Contentspeicher sowie die Suchmaschine FAST beschrieben. Das Ziel des Projektes Verteilter Contentspeicher war die Speicherung, Erschließung und das Angebot der digitalen Best{\"a}nde der Journale und Dokumente der KOBV-Bibliotheken zu erm{\"o}glichen. Die Eignung der Suchmaschine FAST f{\"u}r das Projektvorhaben wurde systematisch und gr{\"u}ndlich getestet, indem verschiedene Dokumentmengen mit FAST indexiert wurden.}, language = {de} } @misc{Busch2005, author = {Busch, Hubert}, title = {Abschlußbericht des DFN-Projekts "Virtueller Supercomputer Berlin - Hannover"}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8337}, number = {04-57}, year = {2005}, abstract = {Mit der Installation des neuen Hochleistungsrechners f{\"u}r die norddeutschen L{\"a}nder (HLRN) steht den Wissenschaftlern ein außergew{\"o}hnlich leistungsf{\"a}higes System zur Verf{\"u}gung. Durch die Verteilung der Rechenelemente auf zwei verschiedene Standorte in Berlin (ZIB) und Hannover (RRZN) entstehen jedoch auch neue Herausforderungen f{\"u}r den Betrieb und die effiziente Nutzung des Rechners. Inhalt dieses Projektes ist die Erforschung und L{\"o}sung der durch die Verteilung des Systems hervorgerufenen Probleme (z.B. Scheduling, Kommunikation, I/O). Es werden effiziente L{\"o}sungen zur Bereitstellung eines virtuellen, hoch-performanten und transparenten Systems entwickelt, die auf vergleichbare Installationen {\"u}bertragbar sind.}, language = {de} } @phdthesis{Koch2005, author = {Koch, Thorsten}, title = {Rapid Mathematical Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8346}, number = {04-58}, year = {2005}, abstract = {The thesis deals with the implementation and application of out-of-the-box tools in linear and mixed integer programming. It documents the lessons learned and conclusions drawn from five years of implementing, maintaining, extending, and using several computer codes to solve real-life industrial problems. By means of several examples it is demonstrated how to apply algebraic modeling languages to rapidly devise mathematical models of real-world problems. It is shown that today's MIP solvers are capable of solving the resulting mixed integer programs, leading to an approach that delivers results very quickly. Even though, problems are tackled that not long ago required the implementation of specialized branch-and-cut algorithms. In the first part of the thesis the modeling language Zimpl is introduced. Chapter 2 contains a complete description of the language. In the subsequent chapter details of the implementation are described. Both theoretical and practical considerations are discussed. Aspects of software engineering, error prevention, and detection are addressed. In the second part several real-world projects are examined that employed the methodology and the tools developed in the first part. Chapter 4 presents three projects from the telecommunication industry dealing with facility location problems. Chapter 5 characterizes questions that arise in UMTS planning. Problems, models, and solutions are discussed. Special emphasis is put on the dependency of the precision of the input data and the results. Possible reasons for unexpected and undesirable solutions are explained. Finally, the Steiner tree packing problem in graphs, a well-known hard combinatorial problem, is revisited. A formerly known, but not yet used model is applied to combine switchbox wire routing and via minimization. All instances known from the literature are solved by this approach, as are some newly generated bigger problem instances.}, language = {en} } @misc{Steidinger2004, author = {Steidinger, Alexander}, title = {Data Management for Processing Molecules}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8358}, number = {05-01}, year = {2004}, abstract = {Molecular dynamics simulations of possible ligands for proteins yield large amounts of data in the form of trajectories which are further processed in order to find metastable conformations. These conformations can then be used for docking between ligand and protein. Around this core computation procedure lots of other data have to be managed. It should also be possible for external users not involved in program development to perform computations. As a paradigm for other fields where a similar constitution of program usage and data processing is found we present a software architecture for data generation, access and management. Requirements for this system include: Ease of use, graphical user interface, persistent storage of data concerning molecules, users, programs, program parameters, metadata, and results. A mere storage in the file system would render a quick overview of data more or less impossible. On the other hand, storing large amounts of binary data in a database doesn't yield any advantage concerning speed of access. Therefore, a hybrid approach combining file system and database is appropriate. The system should be easily extensible by inserting new applications which can be controlled and whose results can be collected and stored. The software system described here consists of different components, the presentation layer (graphical user interface), the business logic, the persistence layer (relational database plus file system), and an interface to the compute cluster (batch system for parallel processing). We will discuss the alternatives and take a closer look at the components.}, language = {en} } @misc{SchmidtEhrenbergHege2004, author = {Schmidt-Ehrenberg, Johannes and Hege, Hans-Christian}, title = {Visual Analysis of Molecular Conformations by Means of a Dynamic Density Mixture Model}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8361}, number = {05-02}, year = {2004}, abstract = {We propose an approach for transforming the sampling of a molecular conformation distribution into an analytical model based on Hidden Markov Models. The model describes the sampled shape density as a mixture of multivariate unimodal densities. Thus, it delivers an interpretation of the sampled density as a set of typical shapes that appear with different probabilities and are characterized by their geometry, their variability and transition probabilities between the shapes. The gained model is used to identify atom groups of constant shape that are connected by metastable torsion angles. Based on this description an alignment for the original sampling is computed. As it takes into account the different shapes contained in the sampled set, this alignment allows to compute reasonable average shapes and meaningful shape density plots. Furthermore, it enables us to visualize typical conformations.}, language = {en} } @misc{FrieseRambau2005, author = {Friese, Philipp and Rambau, J{\"o}rg}, title = {Online-Optimization of Multi-Elevator Transport Systems with Reoptimization Algorithms based on Set-Partitioning Models}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8373}, number = {05-03}, year = {2005}, abstract = {We develop and experimentally compare policies for the control of a system of \$k\$ elevators with capacity one in a transport environment with \$\ell\$ floors, an idealized version of a pallet elevator system in a large distribution center of the Herlitz PBS AG in Falkensee. Each elevator in the idealized system has an individual waiting queue of infinite capacity. On each floor, requests arrive over time in global waiting queues of infinite capacity. The goal is to find a policy that, without any knowledge about future requests, assigns an elevator to each req uest and a schedule to each elevator so that certain expected cost functions (e.g., the average or the maximal flow times) are minimized. We show that a reoptimization policy for minimizing average sq uared waiting times can be implemented to run in real-time (\$1\,s\$) using dynamic column generation. Moreover, in discrete event simulations with Poisson input it outperforms other commonly used polic ies like multi-server variants of greedy and nearest neighbor.}, language = {en} } @misc{Bley2005, author = {Bley, Andreas}, title = {Inapproximability Results for the Inverse Shortest Paths Problem with Integer Length and Unique Shortest Paths}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8388}, number = {05-04}, year = {2005}, abstract = {We study the complexity of two Inverse Shortest Paths (ISP) problems with integer arc lengths and the requirement for uniquely determined shortest paths. Given a collection of paths in a directed graph, the task is to find positive integer arc lengths such that the given paths are uniquely determined shortest paths between their respective terminals. The first problem seeks for arc lengths that minimize the length of the longest of the prescribed paths. In the second problem, the length of the longest arc is to be minimized. We show that it is \$np-hard\$ to approximate the minimal longest path length within a factor less than \$8/7\$ or the minimal longest arc length within a factor less than \$9/8\$. This answers the (previously) open question whether these problems are \$np-hard\$ or not. We also present a simple algorithm that achieves an \$\mathcal{O}(|V|)\$-approximation guarantee for both variants. Both ISP problems arise in the planning of telecommunication networks with shortest path routing protocols. Our results imply that it is \$\mathcal{NP}\$-hard to decide whether a given path set can be realized with a real shortest path routing protocol such as OSPF, IS-IS, or RIP.}, language = {en} } @misc{TsuchidaWolf2005, author = {Tsuchida, Takayuki and Wolf, Thomas}, title = {Classification of polynomial integrable systems of mixed scalar and vector evolution equations. I}, arxiv = {http://arxiv.org/abs/nlin.SI/0412003}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8391}, number = {05-05}, year = {2005}, abstract = {We perform a classification of integrable systems of mixed scalar and vector evolution equations with respect to higher symmetries. We consider polynomial systems that are homogeneous under a suitable weighting of variables. This paper deals with the KdV weighting, the Burgers (or potential KdV or modified KdV) weighting, the Ibragimov--Shabat weighting and two unfamiliar weightings. The case of other weightings will be studied in a subsequent paper. Making an ansatz for undetermined coefficients and using a computer package for solving bilinear algebraic systems, we give the complete lists of \$2^{\mbox{\scriptsize nd }}\$order systems with a \$3^{\mbox{\scriptsize rd }}\$order or a \$4^{\mbox{\scriptsize th }}\$order symmetry and \$3^{\mbox{\scriptsize rd }}\$order systems with a \$5^{\mbox{\scriptsize th }}\$order symmetry. For all but a few systems in the lists, we show that the system (or, at least a subsystem of it) admits either a Lax representation or a linearizing transformation. A thorough comparison with recent work of Foursov and Olver is made.}, language = {en} } @misc{Wolf2005, author = {Wolf, Thomas}, title = {Partial and complete linearization of PDEs based on conservation laws}, arxiv = {http://arxiv.org/abs/nlin.SI/0501034}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8409}, number = {05-06}, year = {2005}, abstract = {A method based on infinite parameter conservation laws is described to factor linear differential operators out of nonlinear partial differential equations (PDEs) or out of differential consequences of nonlinear PDEs. This includes a complete linearization to an equivalent linear PDE (-system) if that is possible. Infinite parameter conservation laws can be computed, for example, with the computer algebra package {\sc ConLaw}.}, language = {en} } @misc{Wolf2005, author = {Wolf, Thomas}, title = {Integrable quadratic Hamiltonians with a linear Lie-Poisson bracket}, doi = {10.1007/s10714-006-0293-2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8414}, number = {05-07}, year = {2005}, abstract = {Quadratic Hamiltonians with a linear Lie-Poisson bracket have a number of applications in mechanics. For example, the Lie-Poisson bracket \$e(3)\$ includes the Euler-Poinsot model describing motion of a rigid body around a fixed point under gravity and the Kirchhoff model describes the motion of a rigid body in ideal fluid. Advances in computer algebra algorithms, in implementations and hardware, together allow the computation of Hamiltonians with higher degree first integrals providing new results in the search for integrable models. A computer algebra module enabling related computations in a 3-dimensional vector formalism is described.}, language = {en} } @misc{AncoWolf2005, author = {Anco, Stephen and Wolf, Thomas}, title = {Some classifications of hyperbolic vector evolution equations}, arxiv = {http://arxiv.org/abs/nlin.SI/0412015}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8429}, number = {05-08}, year = {2005}, abstract = {Motivated by recent work on integrable flows of curves and 1+1 dimensional sigma models, several \$O(N)\$-invariant classes of hyperbolic equations \$Utx=f(U,Ut,Ux)\$ for an \$N\$-component vector \$U(t,x)\$ are considered. In each class we find all scaling-homogeneous equations admitting a higher symmetry of least possible scaling weight. Sigma model interpretations of these equations are presented.}, language = {en} } @misc{SchaedleLopezFernandezLubich2005, author = {Sch{\"a}dle, Achim and Lopez-Fernandez, Maria and Lubich, Christian}, title = {Fast and oblivious convolution quadrature}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8437}, number = {05-09}, year = {2005}, abstract = {We give an algorithm to compute \$N\$ steps of a convolution quadrature approximation to a continuous temporal convolution using only \$O(N\, \log N)\$ multiplications and \$O(\log N)\$ active memory. The method does not require evaluations of the convolution kernel, but instead \$O(\log N)\$ evaluations of its Laplace transform, which is assumed sectorial. The algorithm can be used for the stable numerical solution with quasi-optimal complexity of linear and nonlinear integral and integro-differential equations of convolution type. In a numerical example we apply it to solve a subdiffusion equation with transparent boundary conditions.}, language = {en} } @misc{LopezFernandezLubichPalenciaetal.2005, author = {Lopez-Fernandez, Maria and Lubich, Christian and Palencia, Cesar and Sch{\"a}dle, Achim}, title = {Fast Runge-Kutta approximation of inhomogeneous parabolic equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8443}, number = {05-10}, year = {2005}, abstract = {The result after \$N\$ steps of an implicit Runge-Kutta time discretization of an inhomogeneous linear parabolic differential equation is computed, up to accuracy \$\varepsilon\$, by solving only \$\$O\Big(\log N\, \log \frac1\varepsilon \Big) \$\$ linear systems of equations. We derive, analyse, and numerically illustrate this fast algorithm.}, language = {en} } @misc{HelmbergRoehl2005, author = {Helmberg, Christoph and R{\"o}hl, Stefan}, title = {A Case Study of Joint Online Truck Scheduling and Inventory Management for Multiple Warehouses}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8454}, number = {05-11}, year = {2005}, abstract = {For a real world problem --- transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand --- we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost function that is based on minimizing the expected number of pallets that still need transportation. For speed, the convex relaxation is solved approximately by a bundle approach yielding an online schedule in 5 to 12 minutes for up to 3 warehouses and 40000 articles; in contrast, computation times of state of the art LP-solvers are prohibitive for online application. In extensive numerical experiments on a real world data stream, the approximate solutions exhibit negligible loss in quality; in long term simulations the proposed method reduces the average number of pallets needing transportation due to short term demand to less than half the number observed in the data stream.}, language = {en} } @misc{AndrzejakHermannSahai2005, author = {Andrzejak, Artur and Hermann, Ulf and Sahai, Akhil}, title = {FeedbackFlow - An Adaptive Workflow Generator for System Management}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8467}, number = {05-12}, year = {2005}, abstract = {We describe a prototypical framework that further automates system management by composing complex management tasks from elementary actions, and executing composite tasks with feedback-awareness. {\sl FEEDBACKFLOW} implements a general closed control loop of \emph{planning - execution - result validation - replanning}, and generates workflows of system management actions in an adaptive manner. System-dependent behaviour of the loop is specified by declarative description of the domain (essentially descriptions of available actions), and statement of the goal. We evaluate the design of this framework on examples taken from resource construction in Utility Computing environments, and discuss the challenges we have encountered. Our implementation utilizes external components such as \emph{MBP}, a \emph{PDDL}-conform planner, and \emph{Triana}, a workflow specification and execution framework. An alternative approach involving \emph{BPEL4WS} is discussed.}, language = {en} } @misc{Koster2005, author = {Koster, Arie M.C.A.}, title = {Wavelength Assignment in Multi-Fiber WDM Networks by Generalized Edge Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8478}, number = {05-13}, year = {2005}, abstract = {In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results for stars are also of interest for general meshed topologies. We show that wavelength assignment with at most two links per lightpath can be modeled as a generalized edge coloring problem. By this relation, we show that for a network with an even number of fibers at all links and at most two links per lightpath, all lightpaths can be assigned a wavelength without conversion. Moreover, we derive a lower bound on the number of lightpaths to be converted for networks with arbitrary numbers of fibers at the links. A comparison with linear programming lower bounds reveals that the bounds coincide for problems with at most two links per lightpath. For meshed topologies, the cumulative lower bound over all star subnetworks equals the best known solution value for all realistic wavelength assignment instances available, by this proving optimality.}, language = {en} } @misc{GaertnerKaibel2005, author = {G{\"a}rtner, Bernd and Kaibel, Volker}, title = {Two New Bounds for the Random-Edge Simplex Algorithm}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8483}, number = {05-14}, year = {2005}, abstract = {We prove that the Random-Edge simplex algorithm requires an expected number of at most \$13n/sqrt(d)\$ pivot steps on any simple d-polytope with n vertices. This is the first nontrivial upper bound for general polytopes. We also describe a refined analysis that potentially yields much better bounds for specific classes of polytopes. As one application, we show that for combinatorial d-cubes, the trivial upper bound of \$2^d\$ on the performance of Random-Edge can asymptotically be improved by any desired polynomial factor in d.}, language = {en} } @misc{SchielaWeiser2005, author = {Schiela, Anton and Weiser, Martin}, title = {Superlinear Convergence of the Control Reduced Interior Point Method for PDE Constrained Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8490}, number = {05-15}, year = {2005}, abstract = {A thorough convergence analysis of the Control Reduced Interior Point Method in function space is performed. This recently proposed method is a primal interior point pathfollowing scheme with the special feature, that the control variable is eliminated from the optimality system. Apart from global linear convergence we show, that this method converges locally almost quadratically, if the optimal solution satisfies a function space analogue to a non-degeneracy condition. In numerical experiments we observe, that a prototype implementation of our method behaves in compliance with our theoretical results.}, language = {en} } @misc{LangePolthier2005, author = {Lange, Carsten and Polthier, Konrad}, title = {Anisotropic Smoothing of Point Sets}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8508}, number = {05-16}, year = {2005}, abstract = {The use of point sets instead of meshes became more popular during the last years. We present a new method for anisotropic fairing of a point sampled surface using an anisotropic geometric mean curvature flow. The main advantage of our approach is that the evolution removes noise from a point set while it detects and enhances geometric features of the surface such as edges and corners. We derive a shape operator, principal curvature properties of a point set, and an anisotropic Laplacian of the surface. This anisotropic Laplacian reflects curvature properties which can be understood as the point set analogue of Taubin's curvature-tensor for polyhedral surfaces. We combine these discrete tools with techniques from geometric diffusion and image processing. Several applications demonstrate the efficiency and accuracy of our method.}, language = {en} } @misc{Wagler2004, author = {Wagler, Annegret}, title = {The Normal Graph Conjecture is true for Circulants}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7813}, number = {04-06}, year = {2004}, abstract = {Normal graphs are defined in terms of cross-intersecting set families: a graph is normal if it admits a clique cover \$\cal Q\$ and a stable set cover \$\cal S\$ s.t.~every clique in \$\cal Q\$ intersects every stable set in \$\cal S\$. Normal graphs can be considered as closure of perfect graphs by means of co-normal products (K{\"o}rner 1973) and graph entropy (Czisz\'ar et al. 1990). Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs (Strong Perfect Graph Theorem, Chudnovsky et al. 2002). K{\"o}rner and de Simone observed that \$C_5\$, \$C_7\$, and \$\overline C_7\$ are minimal not normal and conjectured, as generalization of the Strong Perfect Graph Theorem, that every \$C_5\$, \$C_7\$, \$\overline C_7\$- free graph is normal (Normal Graph Conjecture, K{\"o}rner and de Simone 1999). We prove this conjecture for a first class of graphs that generalize both odd holes and odd antiholes, the circulants, by characterizing all the normal circulants.}, language = {en} } @misc{EisenblaetterGeerdesKochetal.2004, author = {Eisenbl{\"a}tter, Andreas and Geerdes, Hans-Florian and Koch, Thorsten and T{\"u}rke, Ulrich}, title = {MOMENTUM Data Scenarios for Radio Network Planning and Simulation (Extended Abstract)}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7829}, number = {04-07}, year = {2004}, abstract = {We present publicly available data sets related to research on wireless networks. The scenarios contain a wide range of data and are detailed in all aspects. To our knowledge, this is the most realistic, comprehensive, and detailed \emph{public} data collection on mobile networking. We indicate example uses of this data collection in applications related tu UMTS.}, language = {en} }