The Chained Lin-Kernighan algorithm (CLK) is one of the best heuristics to solve Traveling Salesman Problems (TSP). In this paper a distributed algorithm is proposed, were nodes in a network locally optimize TSP instances by using the CLK algorithm. Within an Evolutionary Algorithm (EA) network-based framework the resulting tours are modified and exchanged with neighboring nodes. We show that the distributed variant finds better tours compared to the original CLK given the same amount of computation time. For instance fl3795, the original CLK got stuck in local optima in each of 10 runs, whereas the distributed algorithm found optimal tours in each run requiring less than 10 CPU minutes per node on average in an 8 node setup. For instance sw24978, the distributed algorithm had an average solution quality of 0.050% above the optimum, compared to CLK's average solution of 0.119% above the optimum given the same total CPU time (104 seconds). Considering the best tours of both variants for this instance, the distributed algorithm is 0.033% above the optimum and the CLK algorithm 0.099%.
In my doctoral thesis, I present new information about the developmental expression pattern of the potassium chloride cotransporter KCC2 in the rat auditory brain stem and the morphometrical effects caused by KCC2 gene silencing in mice. The thesis is divided into 3 Chapters. Chapter 1 is a general introduction which gives a brief outline of the primary ascending auditory pathway in mammals. Also, it provides information about the presence of a large number of inhibitory inputs in the auditory system and how these inputs develop; the involvement of inhibition in the acoustic processing is mentioned. In addition, the role of the KCC2 cotransporter in the shift of GABA/glycine transmission, and thus, in maintaining the normal level of inhibition in the mature brain, is described. The focus of Chapter 2 was to investigate the KCC2 immunofluorescent signal from postnatal day (P) 0 to P60 in four major nuclei of the rats superior olivary complex (SOC), namely the medial nucleus of the trapezoid body (MNTB), the medial superior olive (MSO), the lateral superior olive (LSO), and the superior paraolivary nucleus (SPN). The lack of a correlation between the continuous presence of KCC2 mRNA/protein in the postnatal rat brain stem on one side, and the shift in GABA/glycinergic polarity (i.e. KCC2 functionality) on the other side, prompted me to search for a specific cellular expression pattern of the KCC2 protein that might correlate with the switch in GABA/glycine signalling. To do so, the KCC2 immunoreactivity was analysed using high-resolution confocal microscopy in three cellular regions of interest: the soma surface, the soma interior, and the neuropil. In the soma surface, I observed an increase of the KCC2 immunofluorescent signal intensity, yet with a moderate magnitude (1.1 to 1.6-fold). Therefore, I conclude that the change in the soma surface signal is only of minor importance and does not explain the change in KCC2 functionality. The KCC2 signal intensity in the soma interior decreased in all nuclei (1.4 to 2-fold) with the exception of the MNTB where no statistically significant change was found. The decrease in the soma interior was probably related to the increase in the soma surface immunoreactivity and the proposed (weak) intracellular trafficking process of the KCC2 protein. The main developmental reorganization (in qualitative as well as in quantitative aspects) of the KCC2 immunofluorescence in the SOC nuclei was observed in the neuropil. The signal changed its pattern from a diffusely stained neuropil early in development (P0-P4) to a crisp and membrane-confined signal later on (P8-P60), with single dendrites becoming apparent. The exception was found in the MNTB, where the neuropil became almost unlabeled. Quantification revealed a statistically significant decrease (2.2 to 3.8-fold) in the neuropil immunoreactivity in all four nuclei, although the remaining KCC2-stained dendrites became thicker and the signal became stronger. I suppose that, at least in part, the neuropil reorganization can be explained by an age-related reduction of dendritic branches via a pruning mechanism and with the absence of an abnormal Cl- load via extrasynaptic GABAA receptors. This is consistent with the proposed additional role of KCC2, namely to maintain the cellular ionic homeostasis and to prevent dendritic swelling (Gulyás et al., 2001). In conclusion, neither the increase in the KCC2 soma surface signal intensity, nor the reorganization in the neuropil can be strictly related to the developmental switch in the GABA/glycine polarity and the onset of KCC2 function, although some correlation (the appearance of a specific membrane-confined dendritic pattern) between structure and function was found. Further implication of different molecular methods, regarding the proposed posttranslational modification of KCC2, will shed light upon the question of what leads to the functional activation of the cotransporter. In Chapter 3, the advantage of loss-of-function KCC2 mice made it possible, via manipulating the duration of the depolarizing phase of GABA/glycine transmission, to analyse the effect of disturbed Cl- regulation and, thus, the effect of disrupted GABA/glycine neurotransmission (lack of inhibition). I asked the following question: how important is the Cl- homeostasis to maintain general aspects (brain weight) and specific aspects (nucleus volume, neuron number, and soma cross-sectional area) of brain development? Brain stem slices from KCC2 knock-out animals (-/-), with a trace amount of transporter (~5%), as well as from wild type animals (+/+) at P3 and P12 were stained for Nissl substance and the analyses were performed with the help of basic morphometrical and stereological methods. In KCC2 (-/-) animals, body growth impairment was observed, in part related to the seizure activity preventing normal feeding (Woo et al., 2002). However, their brains, in terms of brain weight, were less affected. Therefore, I conclude that Cl- homeostasis is not essential per se to maintain the brain weight. Four auditory nuclei (MNTB, MSO, LSO, and ventral cochlear nucleus (VCN)), were compared with respect to the KCC2 null mutation. The SOC nuclei were not influenced by the lack of KCC2 at P3 considering the morphometric parameters. A difference in the number of neurons occurred in the VCN at P3. I suggest to perform additional immunohistochemical studies of glial presence related to its involvement in the structural and functional support of the neurons and their survival. At P12, the volume of the auditory nuclei in KCC2 (-/-) animals was smaller than in (+/+) animals. However, this is likely to be an epiphenomenon since the brain weight increase was also impaired with the same magnitude. Therefore, I suppose that the Cl- homeostasis is not crucial for the nucleus volume increase in the VCN, the MNTB and the MSO during development. An exception was found for the LSO. Regarding the other morphometric parameters at P12, the four nuclei behaved in a different way: (1) in the VCN, after P3, no parameter underwent a disproportional change due to impaired Cl- homeostasis; (2) the MNTB and the LSO showed less pronounced neuropil in mutants in comparison to age-matched controls and two reasons were proposed: first, the depolarizing GABA/glycine transmission in mutants may contribute to excessive Ca2+ load, excitotoxicity and dendrite damage; second, a decrease of some trophic factors may prevent dendrite development in addition to impaired normal body growth; (3) the MSO neurons in P12 (-/-) animals had smaller soma cross-sectional area than in P12 (+/+) animals. I conclude that the normal Cl- homeostasis is required in the MSO at older ages (P12) to achieve and maintain a proper soma size; (4) the lack of KCC2 did not prevent the process of neuronal differentiation in the VCN and the MNTB during development in both mutant and control animals. In conclusion, the various auditory nuclei have to be discussed independently regarding the influence of Cl- homeostasis on some morphometric parameters. Presumably, this is related to the different time of the shift in the GABA/glycine polarity i.e., the onset of KCC2 function (Srinivasan et al., 2004a). Taken together, my thesis accumulated data about the immunohistological expression pattern of KCC2 in various auditory brain stem nuclei and the influence of impaired Cl- homeostasis on some morphometric features in these nuclei. This information will be helpful for further investigations involved to discover the mechanisms and the events that govern the inhibition and the inhibitory pathway in the central auditory system.
In the delay management problem we decide how to react in case of delays in public transportation. More specific, the question is if connecting vhicles should wait for delayed feeder vehicles or if it is better to depart in time.
Any tree in an undirected graph defines a fundamental cut basis. The minimum fundamental cut basis problem is to find a tree minimizing the weight of the corresponding basis. This problem is NP, in the thesis heuristics, relaxations, and numerical results are presented.
Piezoelectric filters are used in telecommunication to filter electrical signals. This report deals with the problem of calculating passing and damped frequency intervals for a filter with given geometrical configurations and materials. Only periodic filters, which are widely used in practice, were considered. These filters consist of periodically arranged cells. For a small amount of cells a numerical procedure to visualise the wave propagation in the filter was developed. For a big number of cells another model of the filter was obtained. In this model it is assumed that the filter occupies an infinite domain. This leads to a differential equation, with periodic coefficients, that describes propagation of the wave with a given frequency in the filter. To analyse this equation the Spectral Theory for Periodic Operators had to be employed. Different ways -- analytical and numerical -- to apply the theory were proposed and analysed.
In this paper we introduce a multiscale technique for the analysis of deformation phenomena of the Earth. Classically, the basis functions under use are globally defined and show polynomial character. In consequence, only a global analysis of deformations is possible such that, for example, the water load of an artificial reservoir is hardly to model in that way. Up till now, the alternative to realize a local analysis can only be established by assuming the investigated region to be flat. In what follows we propose a local analysis based on tools (Navier scaling functions and wavelets) taking the (spherical) surface of the Earth into account. Our approach, in particular, enables us to perform a zooming-in procedure. In fact, the concept of Navier wavelets is formulated in such a way that subregions with larger or smaller data density can accordingly be modelled with a higher or lower resolution of the model, respectively.
Superselection rules induced by the interaction with a mass zero Boson field are investigated for a class of exactly soluble Hamiltonian models. The calculations apply as well to discrete as to continuous superselection rules. The initial state (reference state) of the Boson field is either a normal state or a KMS state. The superselection sectors emerge if and only if the Boson field is infrared divergent, i. e. the bare photon number diverges and the ground state of the Boson field disappears in the continuum. The time scale of the decoherence depends on the strength of the infrared contributions of the interaction and on properties of the initial state of the Boson system. These results are first derived for a Hamiltonian with conservation laws. But in the most general case the Hamiltonian includes an additional scattering potential, and the only conserved quantity is the energy of the total system. The superselection sectors remain stable against the perturbation by the scattering processes.
Finite difference discretizations of 1D poroelasticity equations with discontinuous coefficients are analyzed. A recently suggested FD discretization of poroelasticity equations with constant coefficients on staggered grid, , is used as a basis. A careful treatment of the interfaces leads to harmonic averaging of the discontinuous coefficients. Here, convergence for the pressure and for the displacement is proven in certain norms for the scheme with harmonic averaging (HA). Order of convergence 1.5 is proven for arbitrary located interface, and second order convergence is proven for the case when the interface coincides with a grid node. Furthermore, following the ideas from , modified HA discretization are suggested for particular cases. The velocity and the stress are approximated with second order on the interface in this case. It is shown that for wide class of problems, the modified discretization provides better accuracy. Second order convergence for modified scheme is proven for the case when the interface coincides with a displacement grid node. Numerical experiments are presented in order to illustrate our considerations.
In traditional portfolio optimization under the threat of a crash the investment horizon or time to maturity is neglected. Developing the so-called crash hedging strategies (which are portfolio strategies which make an investor indifferent to the occurrence of an uncertain (down) jumps of the price of the risky asset) the time to maturity turns out to be essential. The crash hedging strategies are derived as solutions of non-linear differential equations which itself are consequences of an equilibrium strategy. Hereby the situation of changing market coefficients after a possible crash is considered for the case of logarithmic utility as well as for the case of general utility functions. A benefit-cost analysis of the crash hedging strategy is done as well as a comparison of the crash hedging strategy with the optimal portfolio strategies given in traditional crash models. Moreover, it will be shown that the crash hedging strategies optimize the worst-case bound for the expected utility from final wealth subject to some restrictions. Another application is to model crash hedging strategies in situations where both the number and the height of the crash are uncertain but bounded. Taking the additional information of the probability of a possible crash happening into account leads to the development of the q-quantile crash hedging strategy.
Inappropriate speed is the most common reason for road traffic accidents world wide. Thus, a necessity for speed management exists. The so-called SUNflower states Sweden, the United Kingdom and the Netherlands - each spending strong effort in traffic safety policies - have great success in reducing mean road speeds and speed variances through speed management. However, the effect is still insufficient for gaining real traffic safety. Thus, there is a discussion to make use of technical in-vehicle devices. One of these technologies called Intelligent Speed Adaptation (ISA) reduces vehicle speeds. This is done either by warning the driver that he is speeding, or activating the accelerator pedal with a counterforce, or reducing the gasoline supply to the motor. The three ways of reducing the speed are called version 1-3. The EC-project for research on speed adaptation policies on European roads (PROSPER) deals with strategic proposals for the implementation of the different ISA-versions. This thesis includes selected results of PROSPER. In this thesis two empiric surveys were done in order to give an overview about the basic conditions (e.g. social, economic, technical aspects) for an ISA implementation in Germany. On one hand, a stakeholder analysis and questionnaire using the Delphi-method has been accomplished in two rounds. On the other hand, a questionnaire with speed offenders has been accomplished, too, in two rounds. In addition, the author created an expert pool consisting of 23 experts representing the most important fields of science and practice in which ISA is involved. The author made phone or personal interviews with most of the experts. 12 experts also produced a detailed publication on their professional point of view towards ISA. The two surveys and the professional comments on ISA led to four possible implementation scenarios for ISA in Germany. However, due to a strong political opposition against ISA it is also thinkable that ISA is not implemented or the implementation process starts after 2015 (i.e. outside the aimed period of time). The scenarios are as follows: A) Implementation of version 1 by market forces with governmental subventions. B) Implementation of version 2 by market forces supported by traffic safety institutions and image-making processes. C) Implementation of a modified version 3 by law for speed offenders instead of cancellation of the driving licence. D) Implementation of various versions in Germany because of a broad implementation of ISA in the SUNflower states. X) Non-implementation of ISA leads to the necessity of alternative speed management measures. The author prefers scenario B because - ceteris paribus - it seems to be the most likely way to implement the technology. As soon as ISA reaches technical maturity, the implementation process has to be accomplished in three steps. 1) Marketing and image making 2) Margin introduction 3) Market penetration This implementation process for ISA by market forces could effect a percentage of at least 15% of all vehicles equipped with ISA before the year 2015.