KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 10 Dec 2014 14:11:41 +0100Wed, 10 Dec 2014 14:11:41 +0100Transit Dependent Evacuation Planning for Kathmandu Valley: A Case Study
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3944
Due to the increasing number of natural or man-made disasters, the application of operations research methods in evacuation planning has seen a rising interest in the research community. From the beginning, evacuation planning has been highly focused on car-based evacuation. Recently, also the evacuation of transit depended evacuees with the help of buses has been considered.
In this case study, we apply two such models and solution algorithms to evacuate a core part of the metropolitan capital city Kathmandu of Nepal as a hypothetical endangered region, where a large part of population is transit dependent. We discuss the computational results for evacuation time under a broad range of possible scenarios, and derive planning suggestions for practitioners.Urmila Pyakurel; Marc Goerigk; Tanka Dhamala; Horst W. Hamacherreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3944Wed, 10 Dec 2014 14:11:41 +0100An online approach to detecting changes in nonlinear autoregressive models
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2772
In this paper we develop monitoring schemes for detecting structural changes
in nonlinear autoregressive models. We approximate the regression function by a
single layer feedforward neural network. We show that CUSUM-type tests based
on cumulative sums of estimated residuals, that have been intensively studied
for linear regression in both an offline as well as online setting, can be extended
to this model. The proposed monitoring schemes reject (asymptotically) the null
hypothesis only with a given probability but will detect a large class of alternatives
with probability one. In order to construct these sequential size tests the limit
distribution under the null hypothesis is obtained.Claudia Kirch; Joseph Tadjuidje Kamgaingreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2772Mon, 24 Oct 2011 10:46:14 +0000Mathematical aspects of stress field simulations in deep geothermal reservoirs
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2671
This report gives an insight into basics of stress field simulations for geothermal reservoirs.
The quasistatic equations of poroelasticity are deduced from constitutive equations, balance
of mass and balance of momentum. Existence and uniqueness of a weak solution is shown.
In order of to find an approximate solution numerically, usage of the so–called method of
fundamental solutions is a promising way. The idea of this method as well as a sketch of
how convergence may be proven are given.Matthias Augustinreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2671Fri, 08 Jul 2011 07:18:26 +0200The Multi Terminal q-FlowLoc Problem: A Heuristic
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2290
In this paper the multi terminal q-FlowLoc problem (q-MT-FlowLoc) is introduced. FlowLoc problems combine two well-known modeling tools: (dynamic) network flows and locational analysis. Since the q-MT-FlowLoc problem is NP-hard we give a mixed integer programming formulation and propose a heuristic which obtains a feasible solution by calculating a maximum flow in a special graph H. If this flow is also a minimum cost flow, various versions of the heuristic can be obtained by the use of different cost functions. The quality of this solutions is compared.Stephanie Heller; Horst W. Hamacherreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2290Wed, 02 Mar 2011 16:46:24 +0100Reliable and Restricted Quickest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288
In a dynamic network, the quickest path problem asks for a path minimizing the time needed to send a given amount of flow from source to sink along this path. In practical settings, for example in evacuation or transportation planning, the reliability of network arcs depends on the specific scenario of interest. In this circumstance, the question of finding a quickest path among all those having at least a desired path reliability arises. In this article, this reliable quickest path problem is solved by transforming it to the restricted quickest path problem. In the latter, each arc is associated a nonnegative cost value and the goal is to find a quickest path among those not exceeding a predefined budget with respect to the overall (additive) cost value. For both, the restricted and reliable quickest path problem, pseudopolynomial exact algorithms and fully polynomial-time approximation schemes are proposed.Stefan Ruzika; Markus Thiemannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288Wed, 02 Mar 2011 16:45:38 +0100Efficient Computation of Equilibria in Bottleneck Games via Game Transformation
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2283
Thomas L. Werth; Heike Sperber; Sven O. Krumkereporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2283Thu, 10 Feb 2011 10:37:35 +0100Locally Supported Wavelets for the Separation of Spherical Vector Fields with Respect to their Sources
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2284
We provide a space domain oriented separation of magnetic fields into parts generated by sources in the exterior and sources in the interior of a given sphere. The separation itself is well-known in geomagnetic modeling, usually in terms of a spherical harmonic analysis or a wavelet analysis that is spherical harmonic based. However, it can also be regarded as a modification of the Helmholtz decomposition for which we derive integral representations with explicitly known convolution kernels. Regularizing these singular kernels allows a multiscale representation of the magnetic field with locally supported wavelets. This representation is applied to a set of CHAMP data for crustal field modeling.Christian Gerhardsreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2284Tue, 08 Feb 2011 12:16:54 +0100Train Marshalling Problem - Algorithms and Bounds -
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2263
The Train Marshalling Problem consists of rearranging an incoming train in a marshalling yard in such a way that cars with the same destinations appear consecutively in the final train and the number of needed sorting tracks is minimized. Besides an initial roll-in operation, just one pull-out operation is allowed. This problem was introduced by Dahlhaus et al. who also showed that the problem is NP-complete. In this paper, we provide a new lower bound on the optimal objective value by partitioning an appropriate interval graph. Furthermore, we consider the corresponding online problem, for which we provide upper and lower bounds on the competitiveness and a corresponding optimal deterministic online algorithm. We provide an experimental evaluation of our lower bound and algorithm which shows the practical tightness of the results.Katharina Beygang; Sven O. Krumke; Florian Dahmsreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2263Mon, 10 Jan 2011 10:26:59 +0100Min-Max Quickest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2249
In a dynamic network, the quickest path problem asks for a path such that a given amount of flow can be sent from source to sink via this path in minimal time. In practical settings, for example in evacuation or transportation planning, the problem parameters might not be known exactly a-priori. It is therefore of interest to consider robust versions of these problems in which travel times and/or capacities of arcs depend on a certain scenario. In this article, min-max versions of robust quickest path problems are investigated and, depending on their complexity status, exact algorithms or fully polynomial-time approximation schemes are proposed.Stefan Ruzika; Markus Thiemannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2249Fri, 19 Nov 2010 09:57:06 +0100Dynamic Multi-Period Routing With Two Classes
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2228
In the Dynamic Multi-Period Routing Problem, one is given a new set of requests at the beginning of each time period. The aim is to assign requests to dates such that all requests are fulfilled by their deadline and such that the total cost for fulling the requests is minimized. We consider a generalization of the problem which allows two classes of requests: The 1st class requests can only be fulfilled by the 1st class server, whereas the 2nd class requests can be fulfilled by either the 1st or 2nd class server. For each tour, the 1st class server incurs a cost that is alpha times the cost of the 2nd class server, and in each period, only one server can be used. At the beginning of each period, the new requests need to be assigned to service dates. The aim is to make these assignments such that the sum of the costs for all tours over the planning horizon is minimized. We study the problem with requests located on the nonnegative real line and prove that there cannot be a deterministic online algorithm with a competitive ratio better than alpha. However, if we require the difference between release and deadline date to be equal for all requests, we can show that there is a min{2*alpha, 2 + 2/alpha}-competitive algorithm.Sven O. Krumke; Christiane Zeckreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2228Mon, 16 Aug 2010 15:41:41 +0200Online Delay Management
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2197
We present extensions to the Online Delay Management Problem on a Single Train Line. While a train travels along the line, it learns at each station how many of the passengers wanting to board the train have a delay of delta. If the train does not wait for them, they get delayed even more since they have to wait for the next train. Otherwise, the train waits and those passengers who were on time are delayed by delta. The problem consists in deciding when to wait in order to minimize the total delay of all passengers on the train line. We provide an improved lower bound on the competitive ratio of any deterministic online algorithm solving the problem using game tree evaluation. For the extension of the original model to two possible passenger delays delta_1 and delta_2, we present a 3-competitive deterministic online algorithm. Moreover, we study an objective function modeling the refund system of the German national railway company, which pays passengers with a delay of at least Delta a part of their ticket price back. In this setting, the aim is to maximize the profit. We show that there cannot be a deterministic competitive online algorithm for this problem and present a 2-competitive randomized algorithm.Sven O. Krumke; Clemens Thielen; Christiane Zeckreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2197Thu, 08 Jul 2010 08:52:34 +0200Generalized Max Flow in Series-Parallel Graphs
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2179
In the generalized max flow problem, the aim is to find a maximum flow in a generalized network, i.e., a network with multipliers on the arcs that specify which portion of the flow entering an arc at its tail node reaches its head node. We consider this problem for the class of series-parallel graphs. First, we study the continuous case of the problem and prove that it can be solved using a greedy approach. Based on this result, we present a combinatorial algorithm that runs in O(m*m) time and a dynamic programming algorithm with running time O(m*log(m)) that only computes the maximum flow value but not the flow itself. For the integral version of the problem, which is known to be NP-complete, we present a pseudo-polynomial algorithm.Katharina Beygang; Sven O. Krumke; Christiane Zeckreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2179Tue, 09 Mar 2010 07:57:55 +0100Selfish Bin Coloring
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2145
We introduce a new game, the so-called bin coloring game, in which selfish players control colored items and each player aims at packing its item into a bin with as few different colors as possible. We establish the existence of Nash and strong as well as weakly and strictly Pareto optimal equilibria in these games in the cases of capacitated and uncapacitated bins. For both kinds of games we determine the prices of anarchy and stability concerning those four equilibrium concepts. Furthermore, we show that extreme Nash equilibria, those with minimal or maximal number of colors in a bin, can be found in time polynomial in the number of items for the uncapcitated case.Leah Epstein; Sven O. Krumke; Asaf Levin; Heike Sperberreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2145Fri, 16 Oct 2009 08:55:08 +0200Earliest Arrival Flows in Series-Parallel Graphs
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2137
We present an exact algorithm for computing an earliest arrival flow in a discrete time setting on series-parallel graphs. In contrast to previous results for the earliest arrival flow problem this algorithm runs in polynomial time.Stefan Ruzika; Heike Sperber; Mechthild Steinerreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2137Tue, 06 Oct 2009 15:31:20 +0200Wärmetransportmodellierung in tiefen geothermischen Systemen
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2129
Gegenstand dieser Arbeit ist die Entwicklung eines Wärmetransportmodells für tiefe geothermische (hydrothermale) Reservoire. Existenz- und Eindeutigkeitsaussagen bezüglich einer schwachen Lösung des vorgestellten Modells werden getätigt. Weiterhin wird ein Verfahren zur Approximation dieser Lösung basierend auf einem linearen Galerkin-Schema dargelegt, wobei sowohl die Konvergenz nachgewiesen als auch eine Konvergenzrate erarbeitet werden.Isabel Ostermannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2129Sat, 19 Sep 2009 16:50:42 +0200Interdisziplinäres Seminar: „Fachdidaktik Chemie und Mathematik“ - Ausarbeitungen und Unterrichtsentwürfe
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2079
Im Sommersemester 2008 führte die AG Optimierung, FB Mathematik zusammen mit dem FB Chemie und dem FB Pädagogik ein interdisziplinäres Seminar zur „Fachdidaktik Chemie und Mathematik“ durch. Durch dieses integrative Lehrveranstaltungskonzept sollte die Nachhaltigkeit der Ausbildung gestärkt und die Verknüpfung von Allgemeiner Didaktik mit der Fachdidaktik sowie zwischen verschiedenen Fachbereichen gefördert werden. In dieser speziellen Veranstaltung erarbeiteten sich die Teilnehmer Inhalte in der Schnittmenge von Chemie und Mathematik, nämlich Kristallgeometrie, Analysis und Titration sowie Graphentheorie und Trennverfahren. Ihre Erkenntnisse wurden im Rahmen von Seminarvorträgen präsentiert und ausgearbeitet. Im folgenden Report befinden sich die Ausarbeitungen, welche Lernziele und Kompetenzen, Sach-, Methodische und Didaktische Analysen sowie Unterrichtsentwürfe umfassen.Florentine Bunke; Horst W. Hamacher; Anne M. Schwahnreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2079Wed, 08 Apr 2009 15:18:45 +0200Truthful Mechanisms for Selfish Routing and Two-Parameter Agents
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2055
We prove a general monotonicity result about Nash flows in directed networks and use it for the design of truthful mechanisms in the setting where each edge of the network is controlled by a different selfish agent, who incurs costs when her edge is used. The costs for each edge are assumed to be linear in the load on the edge. To compensate for these costs, the agents impose tolls for the usage of edges. When nonatomic selfish network users choose their paths through the network independently and each user tries to minimize a weighted sum of her latency and the toll she has to pay to the edges, a Nash flow is obtained. Our monotonicity result implies that the load on an edge in this setting can not increase when the toll on the edge is increased, so the assignment of load to the edges by a Nash flow yields a monotone algorithm. By a well-known result, the monotonicity of the algorithm then allows us to design truthful mechanisms based on the load assignment by Nash flows. Moreover, we consider a mechanism design setting with two-parameter agents, which is a generalization of the case of one-parameter agents considered in a seminal paper of Archer and Tardos. While the private data of an agent in the one-parameter case consists of a single nonnegative real number specifying the agent's cost per unit of load assigned to her, the private data of a two-parameter agent consists of a pair of nonnegative real numbers, where the first one specifies the cost of the agent per unit load as in the one-parameter case, and the second one specifies a fixed cost, which the agent incurs independently of the load assignment. We give a complete characterization of the set of output functions that can be turned into truthful mechanisms for two-parameter agents. Namely, we prove that an output function for the two-parameter setting can be turned into a truthful mechanism if and only if the load assigned to every agent is nonincreasing in the agent's bid for her per unit cost and, for almost all fixed bids for the agent's per unit cost, the load assigned to her is independent of the agent's bid for her fixed cost. When the load assigned to an agent is continuous in the agent's bid for her per unit cost, it must be completely independent of the agent's bid for her fixed cost. These results motivate our choice of linear cost functions without fixed costs for the edges in the selfish routing setting, but the results also seem to be interesting in the context of algorithmic mechanism design themselves.Clemens Thielenreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2055Thu, 15 Jan 2009 15:21:50 +0100Minimum Cut Tree Games
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2049
In this paper we introduce a cooperative game based on the minimum cut tree problem which is also known as multi-terminal maximum flow problem. Minimum cut tree games are shown to be totally balanced and a solution in their core can be obtained in polynomial time. This special core allocation is closely related to the solution of the original graph theoretical problem. We give an example showing that the game is not supermodular in general, however, it is for special cases and for some of those we give an explicit formula for the calculation of the Shapley value.Anne M. Schwahnreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2049Fri, 19 Dec 2008 12:48:05 +0100Klassische Erdschwerefeldbestimmung aus der Sicht moderner Geomathematik
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2040
Gegenstand dieser Arbeit ist die kanonische Verbindung klassischer globaler Schwerefeldmodellierung in der Konzeption von Stokes (1849) und Neumann (1887) und moderner lokaler Multiskalenberechnung mittels lokalkompakter adaptiver Wavelets. Besonderes Anliegen ist die "Zoom-in"-Ermittlung von Geoidhöhen aus lokal gegebenen Schwereanomalien bzw. Schwerestörungen.Willi Freeden; Kerstin Wolfreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2040Tue, 18 Nov 2008 13:50:49 +0100How to find Nash equilibria with extreme total latency in network congestion games?
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2034
We study the complexity of finding extreme pure Nash equilibria in symmetric network congestion games and analyse how it depends on the graph topology and the number of users. In our context best and worst equilibria are those with minimum respectively maximum total latency. We establish that both problems can be solved by a Greedy algorithm with a suitable tie breaking rule on parallel links. On series-parallel graphs finding a worst Nash equilibrium is NP-hard for two or more users while finding a best one is solvable in polynomial time for two users and NP-hard for three or more. Additionally we establish NP-hardness in the strong sense for the problem of finding a worst Nash equilibrium on a general acyclic graph.Heike Sperberreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2034Wed, 29 Oct 2008 15:50:44 +0100Classical Globally Reflected Gravity Field Determination in Modern Locally Oriented Multiscale Framework
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2031
The purpose of this paper is the canonical connection of classical global gravity field determination following the concept of Stokes (1849), Bruns (1878), and Neumann (1887) on the one hand and modern locally oriented multiscale computation by use of adaptive locally supported wavelets on the other hand. Essential tools are regularization methods of the Green, Neumann, and Stokes integral representations. The multiscale approximation is guaranteed simply as linear difference scheme by use of Green, Neumann, and Stokes wavelets, respectively. As an application, gravity anomalies caused by plumes are investigated for the Hawaiian and Iceland areas.W. Freeden; T. Fehlinger; M. Klug; D. Mathar; K. Wolfreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2031Tue, 14 Oct 2008 12:34:09 +0200A piecewise analytical solution for Jiangs model of elastoplasticity
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1898
In this article, we present an analytic solution for Jiang's constitutive model of elastoplasticity. It is considered in its stress controlled form for proportional stress loading under the assumptions that the one-to-one coupling of the yield surface radius and the memory surface radius is switched off, that the transient hardening is neglected and that the ratchetting exponents are constant.Holger Lang; Klaus Dressler; Rene Pinnaureporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1898Tue, 02 Oct 2007 12:27:59 +0200A condition that a continuously deformed, simply connected body does not penetrate itself
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1874
In this article we give a sufficient condition that a simply connected flexible body does not penetrate itself, if it is subjected to a continuous deformation. It is shown that the deformation map is automatically injective, if it is just locally injective and injective on the boundary of the body. Thereby, it is very remarkable that no higher regularity assumption than continuity for the deformation map is required. The proof exclusively relies on homotopy methods and the Jordan-Brouwer separation theorem.Holger Langreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1874Sat, 23 Jun 2007 13:31:37 +0200Local Modelling of Sea Surface Topography from (Geostrophic) Ocean Flow
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1836
This paper deals with the problem of determining the sea surface topography from geostrophic flow of ocean currents on local domains of the spherical Earth. In mathematical context the problem amounts to the solution of a spherical differential equation relating the surface curl gradient of a scalar field (sea surface topography) to a surface divergence-free vector field(geostrophic ocean flow). At first, a continuous solution theory is presented in the framework of an integral formula involving Green’s function of the spherical Beltrami operator. Different criteria derived from spherical vector analysis are given to investigate uniqueness. Second, for practical applications Green’s function is replaced by a regularized counterpart. The solution is obtained by a convolution of the flow field with a scaled version of the regularized Green function. Calculating locally without boundary correction would lead to errors near the boundary. To avoid these Gibbs phenomenona we additionally consider the boundary integral of the corresponding region on the sphere which occurs in the integral formula of the solution. For reasons of simplicity we discuss a spherical cap first, that means we consider a continuously differentiable (regular) boundary curve. In a second step we concentrate on a more complicated domain with a non continuously differentiable boundary curve, namely a rectangular region. It will turn out that the boundary integral provides a major part for stabilizing and reconstructing the approximation of the solution in our multiscale procedure.Thomas Fehlinger; Willi Freeden; Simone Gramsch; Carsten Mayer; Dominik Michel; Michael Schreinerreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1836Sun, 11 Feb 2007 15:03:15 +0100Notes at the embeddedness of the minimal surface of Costa, Hoffman and Meeks
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1777
The existence of a complete, embedded minimal surface of genus one, with three ends and whose total Gaussian curvature satisfies equality in the estimate of Jorge and Meeks, was a sensation in the middle eighties. From this moment on, the surface of Costa, Hoffman and Meeks has become famous all around the world, not only in the community of mathematicians. With this article, we want to fill a gap in the injectivity proof of Hoffman and Meeks, where there is a lack of a strict mathematical justification. We exclusively argue topologically and do not use additional properties like differentiability or even holomorphy.Holger Langreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1777Sat, 23 Sep 2006 13:08:22 +0200