No description available.

No description available.

No description available.

In this thesis, we study two optimization problems which have a lot of important applications in diverse domains: Line Cover Problem (LCP) in Computational Geometry and Maximum Genus Embedding (MGE) in Topological Graph Theory. We study LCP whose decision version is known NP-Complete from the perspective of Parameterized Complexity, as well as classical techniques in Algorithm Design. In particular, we provide an exact algorithm in time O(n^3 2n) based on Dynamic Programming and initiate a dual problem of LCP in terms of Linear Programming Duality. We study the dual problem by applying approximation and kernelization, obtaining an approximation algorithm with ratio k - 1 and a kernel of size O(k^4). Then we survey related geometric properties on LCP. Finally we propose a Parameterized Algorithm to solve LCP with running time O*(k^k/1:35^k). We explore connections between the maximum genus of a graph and its cycle space consisting of fundamental cycles only. We revisit a known incorrect approach of finding a maximum genus embedding via computing a maximum pairing of intersected fundamental cycles with respect to an arbitrary spanning tree. We investigate the reason it failed and conclude it confused the concept of deficiency. Also, we characterize the upper-embeddablity of a graph in terms of maximum pairings of intersected fundamental cycles, i.e. a graph is upper-embeddable if and only if the number of maximum pairings of intersected fundamental cycles for any spanning tree is the same. Finally, we present a lower and an upper bound of the maximum number of vertex-disjoint cycles in a general graph, beta(G) - 2gammaM(G) and beta(G) - gammaM(G), only depending on maximum genus and cycle rank.

No description available.

Die Arbeit behandelt einen Reduktionsbeweis der zeigt, dass die Identifikation der Zeichenkette die von einem konsistenten rekurrenten neuronalen Netz das höchste Gewicht unter allen Zeichenketten zugewiesen bekommt ein Problem ist, dass NP-vollständig und APX-hart ist. / The thesis mainly consists of a proof by reduction that shows that identifying the string that is assigned the highest weight amongst all strings by a complete recurrent neural network is a problem that turns out to be NP-complete and APX-hard.

Optimization problems are divided into numerical optimization problems and combinatorial optimization problems. Genetic algorithms (GAs) are applied to solve optimization problems widely. GAs with multi-parent crossover are often used to solve numerical optimization problems. However, no effective multi-parent crossover is used for combinatorial optimization problems. Partially mapped crossover (PMX) is the most popular crossover for combinatorial optimization problems. In this thesis, we propose multi-parent partially mapped crossover (MPPMX). A large amount of experimental results show that the improvement ratio of MPPMX reaches 38.63 % over PMX. The p-values of t-test on the difference between MPPMX and PMX range from 10-6 to 10-14, which indicates the significant improvement of MPPMX over PMX.

5th IFAC Symposium on Mechatronic Systems, Marriott Boston Cambridge, Cambridge, MA, USA, Sept 13-15, 2010

The optimization problems involving stochastic systems are often encountered in financial systems, networks design and routing, supply-chain management, actuarial science, telecommunications systems, statistical pattern recognition analysis associated with electronic commerce and medical diagnosis. / This thesis aims to develop computational methods for solving three optimization problems, where their dynamical systems are described by three different classes of stochastic systems with jumps. / In Chapter 1, a brief review on optimization problems involving stochastic systems with jumps is given. It is then followed by the introduction of three optimization problems, where their dynamical systems are described by three different classes of stochastic systems with jumps. These three stochastic optimization problems will be studied in detail in Chapters 2, 3 and 4, respectively. The literature reviews on optimization problems involving these three stochastic systems with jumps are presented in the last three sections of each of Chapters 2, 3 and 4, respectively. / In Chapter 2, an optimization problem involving nonparametric regression with jump points is considered. A two-stage method is proposed for nonparametric regression with jump points. In the first stage, we identify the rough locations of all the possible jump points of the unknown regression function. In the second stage, we map the yet to be decided jump points into pre-assigned fixed points. In this way, the time domain is divided into several sections. Then the spline function is used to approximate each section of the unknown regression function. These approximation problems are formulated and subsequently solved as optimization problems. The inverse time scaling transformation is then carried out, giving rise to an approximation to the nonparametric regression with jump points. For illustration, several examples are solved by using this method. The result obtained are highly satisfactory. / In Chapter 3, the optimization problem involving nonparametric regression with jump curves is studied. A two-stage method is presented to construct an approximating surface with jump location curve from a set of observed data which are corrupted with noise. In the first stage, we detect an estimate of the jump location curve in a surface. In the second stage, we shift the jump location curve into a row pixels or column pixels. The shifted region is then divided into two disjoint subregions by the jump location row pixels. These subregions are expanded to two overlapping expanded subregions, each of which includes the jump location row pixels. We calculate artificial values at these newly added pixels by using the observed data and then approximate the surface on each expanded subregions in which the artificial values at the pixels in the jump location row pixels for each expanded subregion. The curve with minimal distance between the two surfaces is chosen as the curve dividing the region. Subsequently, two nonoverlapping tensor product cubic spline surfaces are obtained. Then, by carrying out the inverse space scaling transformation, the two fitted smooth surfaces in the original space are obtained. For illustration, a numerical example is solved using the method proposed. / In Chapter 4, a class of stochastic optimal parameter selection problems described by linear Ito stochastic differential equations with state jumps subject to probabilistic constraints on the state is considered, where the times at which the jumps occurred as well as their heights are decision variables. We show that this constrained stochastic impulsive optimal parameter selection problem is equivalent to a deterministic impulsive optimal parameter selection problem subject to continuous state inequality constraints, where the times at which the jumps occurred as well as their heights remain as decision variables. Then we show that this constrained deterministic impulsive optimal parameter selection problem can be transformed into an equivalent constrained deterministic impulsive optimal parameter selection problem with fixed jump times. We approximate the continuous state inequality constraints by a sequence of canonical inequality constraints. This leads to a sequence of approximate deterministic impulsive optimal parameter selection problems subject to canonical inequality constraints. For each of these approximate problems, we derive the gradient formulas of the cost function and the constraint functions. On this basis, an efficient computational method is developed. For illustration, a numerical example is solved. / Finally, Chapter 5 contains some concluding remarks and suggestions for future studies.

No description available.