In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

Le but de cette thèse est de trouver des bornes supérieures pour les valeurs propres des opérateurs naturels agissant sur les fonctions d’une variété compacte (M; g). Nous étudions l’opérateur de Laplace–Beltrami et des opérateurs du type laplacien. Dans le cas du laplacien, deux aspects sont étudiés. Le premier aspect est d’étudier des relations entre la géométrie intrinsèque et les valeurs propres du laplacien. Nous obtenons des bornes supérieures ne dépendant que de la dimension et d’un invariant conforme qui s’appelle le volume conforme minimal. Asymptotiquement, ces bornes sont consistantes avec la loi de Weyl. Elles améliorent également les résultats de Korevaar et de Yang et Yau. La méthode employée est intéressante en soi. Le deuxième aspect est d’étudier la relation entre la géométrie extrinsèque et les valeurs propres du laplacien agissant sur des sous-variétés compactes de RN et de CPN. Nous étudions un invariant extrinsèque qui s’appele l’indice d’intersection. Pour des sous-variétés compactes de RN, nous généralisons les résultats de Colbois, Dryden et El Soufi et obtenons des bornes supérieures qui sont stables par des petites perturbations. Pour des sous-variétés de CPN, nous obtenons une borne supérieure ne dépendant que du degré des sous-variétés. Pour des opérateur du type laplacien, une modification de notre méthode donne des bornes supérieures pour les valeurs propres des opérateurs de Schrödinger en termes du volume conforme minimal et de l’intégrale du potentiel. Nous obtenons également les bornes supérieures pour les valeurs propres du laplacien de Bakry–Émery dépendant d’invariants conformes. / The purpose of this thesis is to find upper bounds for the eigenvalues of natural operators acting on functions on a compact Riemannian manifold (M; g) such as the Laplace–Beltrami operator and Laplace-type operators. In the case of the Laplace-Beltrami operator, two aspects are investigated: The first aspect is to study relationships between the intrinsic geometry and eigenvalues of the Laplacian operator. In this regard, we obtain upper bounds depending only on the dimension and a conformal invariant called min-conformal volume. Asymptotically, these bounds are consistent with the Weyl law. They improve previous results by Korevaar and Yang and Yau. The method which is introduced to obtain the results, is powerful and interesting in itself. The second aspect is to study the interplay of the extrinsic geometry and eigenvalues of the Laplace–Beltrami operator acting on compact submanifolds of RN and of CPN. We investigate an extrinsic invariant called the intersection index studied by Colbois, Dryden and El Soufi. For compact submanifolds of RN, we extend their results and obtain upper bounds which are stable under small perturbation. For compact submanifolds of CPN, we obtain an upper bound depending only on the degree of submanifolds. For Laplace type operators, a modification of our method lead to have upper bounds for the eigenvalues of Schrödinger operators in terms of the min-conformal volume and integral quantity of the potential. As another application of our method, we obtain upper bounds for the eigenvalues of the Bakry–Émery Laplace operator depending on conformal invariants.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-06-07T19:46:54Z No. of bitstreams: 1 sebastiaomaurofilho.pdf: 422464 bytes, checksum: 2d72827356c924e509ef415cf17ff6bc (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-06-26T17:47:29Z (GMT) No. of bitstreams: 1 sebastiaomaurofilho.pdf: 422464 bytes, checksum: 2d72827356c924e509ef415cf17ff6bc (MD5) / Made available in DSpace on 2017-06-26T17:47:29Z (GMT). No. of bitstreams: 1 sebastiaomaurofilho.pdf: 422464 bytes, checksum: 2d72827356c924e509ef415cf17ff6bc (MD5) Previous issue date: 2012-02-29 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Recentemente foi demonstrado [17] que correções quânticas para o potencial gravitacional de Newton explica as curvas de rotação em galáxias espirais sem introduzir o halo de matéria escura. O único parâmetro fenomenológico aѵ da teoria cresce com a massa da galáxia. A fim de melhor investigar a dependência de aѵ com a massa é preciso verificar o limite superior para aѵ em uma escala menor. Aqui nós realizamos o cálculo correspondente por meio da análise da dinâmica do vetor de Laplace-Runge-Lenz e da condição de equilíbrio de anãs-brancas. A limitação resultante sobre correções quânticas sugerem uma dependência de aѵ com a massa. / Recently it was shown that quantum corrections to the Newton potential can explain the rotation curves in spiral galaxies without introducing the Dark Matter halo. The unique phenomenological parameter aѵ of the theory grows with the mass of the galaxy. In order to better investigate the mass-dependence of aѵ one needs to check the upper bound for aѵ at a smaller scale. Here we perform the corresponding calculation by analyzing the dynamics of the Laplace-Runge-Lenz vector and the equilibrium condition of white-dwarf. The resulting limitation on quantum corrections is suggesting a mass-dependence of aѵ.

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

Nonlinear explicit finite element (FE) simulations are used to study the axial collapse behavior of multi-corner. single- and multi-cell crush tubes under quasi-static and dynamic loading conditions. It is shown that the higher hardening modulus and yield stress increases the crush force and its resulting energy absorption. Moreover, the multi-cell tubes are found to have complicated collapse modes because of the geometrical complexity of the corner region unlike single-cell tubes. it was also shown that the stress wave propagation has a significant effect on the formation of crush modes in the tubes without imperfections whereas this effect can be ignored in tubes with imperfection or trigger mechanism. An analytical formula for the prediction of mean crush force of multi-corner multi-cell tubes is derived based on the super folding element theory. The analytical predictions for the mean crush force are found to be in good agreement with the FE solutions. Results also show a strong correlation between the cross-sectional geometry and the crash behavior with the method of connecting the inner to the outer walls having large influence on the energy absorption.

Flood design necessitates discharge estimates for large recurrence intervals. However, in a flood frequency analysis, the uncertainty of discharge estimates increases with higher recurrence intervals, particularly due to the small number of available flood data. Furthermore, traditional distribution functions increase unlimitedly without consideration of an upper bound discharge. Hence, additional information needs to be considered which is representative for high recurrence intervals. Envelope curves which bound the maximum observed discharges of a region are an adequate regionalisation method to provide additional spatial information for the upper tail of a distribution function. Probabilistic regional envelope curves (PRECs) are an extension of the traditional empirical envelope curve approach, in which a recurrence interval is estimated for a regional envelope curve (REC). The REC is constructed for a homogeneous pooling group of sites. The estimation of this recurrence interval is based on the effective sample years of data considering the intersite dependence among all sites of the pooling group. The core idea of this thesis was an improvement of discharge estimates for high recurrence intervals by integrating empirical and probabilistic regional envelope curves into the flood frequency analysis. Therefore, the method of probabilistic regional envelope curves was investigated in detail. Several pooling groups were derived by modifying candidate sets of catchment descriptors and settings of two different pooling methods. These were used to construct PRECs. A sensitivity analysis shows the variability of discharges and the recurrence intervals for a given site due to the different assumptions. The unit flood of record which governs the intercept of PREC was determined as the most influential aspect. By separating the catchments into nested and unnested pairs, the calculation algorithm for the effective sample years of data was refined. In this way, the estimation of the recurrence intervals was improved, and therefore the use of different parameter sets for nested and unnested pairs of catchments is recommended. In the second part of this thesis, PRECs were introduced into a distribution function. Whereas in the traditional approach only discharge values are used, PRECs provide a discharge and its corresponding recurrence interval. Hence, a novel approach was developed, which allows a combination of the PREC results with the traditional systematic flood series while taking the PREC recurrence interval into consideration. An adequate mixed bounded distribution function was presented, which in addition to the PREC results also uses an upper bound discharge derived by an empirical envelope curve. By doing so, two types of additional information which are representative for the upper tail of a distribution function were included in the flood frequency analysis. The integration of both types of additional information leads to an improved discharge estimation for recurrence intervals between 100 and 1000 years. / Abschätzungen von Abflüssen mit hohen Wiederkehrintervallen werden vor allem für die Bemessung von Extremhochwässern benötigt. In der Hochwasserstatistik bestehen insbesondere für hohe Wiederkehrintervalle große Unsicherheiten, da nur eine geringe Anzahl an Messwerten für Hochwasserereignisse verfügbar ist. Zudem werden zumeist Verteilungsfunktionen verwendet, die keine obere Grenze beinhalten. Daher müssen zusätzliche Informationen zu den lokalen Pegelmessungen berücksichtigt werden, die den Extrembereich einer Verteilungsfunktion abdecken. Hüllkurven ermitteln eine obere Grenze von Hochwasserabflüssen basierend auf beobachteten maximalen Abflusswerten. Daher sind sie eine geeignete Regionalisierungsmethode. Probabilistische regionale Hüllkurven sind eine Fortentwicklung des herkömmlichen Ansatzes der empirischen Hüllkurven. Hierbei wird einer Hüllkurve einer homogenen Region von Abflusspegeln ein Wiederkehrintervall zugeordnet. Die Berechnung dieses Wiederkehrintervalls basiert auf der effektiven Stichprobengröße und berücksichtigt die Korrelationsbeziehungen zwischen den Pegeln einer Region. Ziel dieser Arbeit ist eine Verbesserung der Abschätzung von Abflüssen mit großen Wiederkehrintervallen durch die Integration von empirischen und probabilistischen Hüllkurven in die Hochwasserstatistik. Hierzu wurden probabilistische Hüllkurven detailliert untersucht und für eine Vielzahl an homogenen Regionen konstruiert. Hierbei wurden verschiedene Kombinationen von Einzugsgebietsparametern und Variationen von zwei Gruppierungsmethoden verwendet. Eine Sensitivitätsanalyse zeigt die Variabilität von Abfluss und Wiederkehrintervall zwischen den Realisationen als Folge der unterschiedlichen Annahmen. Die einflussreichste Größe ist der maximale Abfluss, der die Höhe der Hüllkurve bestimmt. Eine Einteilung in genestete und ungenestete Einzugsgebiete führt zu einer genaueren Ermittlung der effektiven Stichprobe und damit zu einer verbesserten Abschätzung des Wiederkehrintervalls. Daher wird die Verwendung von zwei getrennten Parametersätzen für die Korrelationsfunktion zur Abschätzung des Wiederkehrintervalls empfohlen. In einem zweiten Schritt wurden die probabilistischen Hüllkurven in die Hochwasserstatistik integriert. Da in traditionellen Ansätzen nur Abflusswerte genutzt werden, wird eine neue Methode präsentiert, die zusätzlich zu den gemessenen Abflusswerten die Ergebnisse der probabilistischen Hüllkurve – Abfluss und zugehöriges Wiederkehrintervall - berücksichtigt. Die Wahl fiel auf eine gemischte begrenzte Verteilungsfunktion, die neben den probabilistischen Hüllkurven auch eine absolute obere Grenze, die mit einer empirischen Hüllkurve ermittelt wurde, beinhaltet. Damit werden zwei Arten von zusätzlichen Informationen verwendet, die den oberen Bereich einer Verteilungsfunktion beschreiben. Die Integration von beiden führt zu einer verbesserten Abschätzung von Abflüssen mit Wiederkehrintervallen zwischen 100 und 1000 Jahren.

In dieser Arbeit werden die zu einem m-sektoriellen Operator assoziierten Halbgruppen betrachtet, die die Lösungen des Anfangswertproblems der zugehörigen Evolutionsgleichung beschreiben. Es wird eine 1987 von Davies veröffentlichte Methode zur Abschätzung dieser Halbgruppen verallgemeinert. Einen Schwerpunkt bilden die zu Dirichlet-Formen assoziierten Markov-Halbgruppen. Für diese werden die Resultate spezialisiert und der Zusammenhang zur intrinsischen Metrik dargelegt. Die Arbeit schließt mit verschiedenen Beispielen, die zeigen, wie mit diesen Verallgemeinerungen von Davies Methode neue Anwendungsgebiete erschlossen werden können. / This thesis is about m-sectorial operators and their associated semigroups describing the solutions of the initial value problem of the corresponding evolution equation. We generalize a method published by Davies 1987 to estimate these semigroups. A focus is set on Markov semigroups associated with Dirchlet forms. The results are applied to them and the connection to the intrinsic metric is presented. The thesis ends with different examples showing how this generalization of Davies method can be applied into new fields of application.

Afin d'optimiser la mise aux milles au laminage à froid, la thèse consiste à développer un modèle prédictif de variation de largeur à la fois précis et rapide pour des utilisations en temps réel. Des efforts ont commencé en 1960s en développant des formules empiriques. Par la suite, la Méthode des Bornes Supérieures (MBS) est devenue la plus connue. [Oh 1975] utilisant le champ de vitesse 3D "simple" prédit bien la variation de largeur au laminage en conditions d'un tandem finisseur. [Komori 2002] a proposé une combinaison des champs fondamentaux et obtenu une structure informatique peu dépendante aux champs de vitesse. Néanmoins, seuls deux champs fondamentaux ont été introduits qui forment un sous-ensemble de la famille 3D "simple". [Serek 2008] a étudié des champs de vitesse quadratique qui inclue la famille "simple" et donne des meilleurs résultats avec un temps de calcul plus long. Le premier résultat de la thèse est un modèle 2D (MBS) avec des champs de vitesse oscillante. Ce modèle aboutit à une vitesse optimale qui oscille spatialement le long de l'emprise. Les résultats (puissance, vitesse...) sont plus proches des ceux de Lam3-Tec3 que la MBS 2D "simple". Pour une modélisation 3D, nous avons choisi la MBS avec la vitesse 3D "simple" et obtenu un très bon accord avec les expériences réalisées sur des produits étroits à Arcelor Mittal [64]. En outre, un nouveau modèle MBS est développé pour une bande bombée et des cylindres droits. Les résultats montrent que la variation de largeur diminue avec la bombée de la bande et correspondent bien à ceux de Lam3-Tec3. Cependant, la MBS admet un comportement rigide-plastique tandis qu'au laminage des bandes larges les déformations élastique et thermique ont des impacts importants sur la déformation plastique. Les modèles existant prenant en compte ces phénomènes [23,64] sont couteux en temps de calcul. Ainsi, l'idée est de décomposer la variation de la largeur de plastique en trois termes : les variations de largeur totales, élastique et thermique à travers la zone de plastique déterminés par trois nouveaux modèles simplifiés. Les deux premiers permettent d'estimer les variations de largeur élastique et plastique avant et après l'emprise. Ils donnent aussi les conditions aux limites au modèle d'emprise qui est en effet la MBS avec le champ de vitesse 3D "simple" permettant d'estimer la variation de la largeur totale. En outre, avec les puissances de déformation et de dissipation plastique de frottement données par le même modèle, la variation de largeur thermique est également obtenue. Le modèle de variation de largeur est donc appelée UBM-Slab combiné, très rapide (0,05 s) et prédit avec précision la largeur de variation par rapport à Lam3-Tec3 (<6%) / In order to save material yields in cold rolling process, the thesis aims at developing a predictive width variation model accurate and fast enough to be used online. Many efforts began in the 1960s in developing empirical formula. Afterward, the Upper Bound Method (UBM ) became more common. [Oh 1975]'s model with 3D "simple" velocity field estimates well the width variation for finishing mill rolling conditions. [Komori 2002] proposed a combination of fundamental ones to obtain a computer program depending minimally on the assumed velocity fields. However, only two fundamental fields were introduced and formed a subset of the "simple" family. [Serek 2008] studied a quadratic velocity family that includes the "simple" one and leads to better results with a higher computing time. Focusing on UBM , the first result of the thesis is a 2D model with an oscillating velocity field family. The model results to an optimum velocity that oscillates spatially throughout the roll-bite. The optimum power and the velocity field are closer to Lam3-Tec3 results than the "simple" one. For 3D modelling, we chose the 3D "simple" UBM and carried a comparison to the experiments performed at Arcelor Mittal using narrow strips [64]. A very good agreement is obtained. Further, a new UBM model is developed for a crowned strip with cylindrical work-rolls. It shows that the width variation decreases as a function of the strip crown and the results match well those of Lam3-Tec3 . However, the UBM considers only a rigid-plastic behaviour while in large strip rolling, the elastic and thermal deformations have important impacts on the plastic one. There exist some models considering these phenomena [23,64] but they are all time-consuming. Thus, the idea is to decompose the plastic width variation into three terms : total, elastic and thermal width variations through the plastic zone that are determined by three new models. The simplified roll-bite entry & exit models allow estimating the elastic and plastic width variations before and after the roll-bite. They give equally the longitudinal stresses defining the boundary conditions for the roll-bite model which is indeed the 3D "simple" UBM approximating the total width variation term. Moreover, with the plastic deformation and friction dissipation powers given by the same model, the thermal width variation term is also obtained. The width variation model, called UBM-Slab combined is very fast (0.05s) and predicts accurately the width variation in comparison with Lam3-Tec3 (<6%)

abstract: I propose a new communications scheme where signature signals are used to carry digital data by suitably modulating the signal parameters with information bits. One possible application for the proposed scheme is in underwater acoustic (UWA) communications; with this motivation, I demonstrate how it can be applied in UWA communications. In order to do that, I exploit existing parameterized models for mammalian sounds by using them as signature signals. Digital data is transmitted by mapping vectors of information bits to a carefully designed set of parameters with values obtained from the biomimetic signal models. To complete the overall system design, I develop appropriate receivers taking into account the specific UWA channel models. I present some numerical results from the analysis of data recorded during the Kauai Acomms MURI 2011 (KAM11) UWA communications experiment. It is shown that the proposed communication scheme results in approximate channel models with amplitude-limited inputs and signal-dependent additive noise. Motivated by this observation, I study capacity of amplitude-limited channels under different transmission scenarios. Specifically, I consider fading channels, signal-dependent additive Gaussian noise channels, multiple-input multiple-output (MIMO) systems and parallel Gaussian channels under peak power constraints. I also consider practical channel coding problems for channels with signal-dependent noise. I consider two specific models; signal-dependent additive Gaussian noise channels and Z-channels which serve as binary-input binary-output approximations to the Gaussian case. I propose a new upper bound on the probability of error, and utilize it for design of codes. I illustrate the tightness of the derived bounds and the performance of the designed codes via examples. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2015

Notre thèse propose d'étudier la précision des calculs par la méthode des éléments finis (MEF) au moyen "d'indicateurs de qualité". Les indicateurs de qualité représentent des formules simples qui permettent d'évaluer la qualité des calculs par éléments finis. La qualité de l'analyse numérique est évaluée par rapport à la discrétisation. Le modèle mathématique est considéré correct et les erreurs résultant du choix des propriétés des matériaux ne sont pas pris en compte. Nous avons défini les formulations mathématiques de ces indicateurs de qualité, ainsi que leurs limites inférieures et supérieures. Grâce au choix de formulations simples, il est facile de les introduire dans un logiciel de calcul par éléments finis. Ils ont été implémentés dans le code de calcul CESAR-LCPC, module Mécanique en Comportement Non Linéaire. Afin de démontrer qu'ils ont été correctement définis et de tester leur fiabilité, ces indicateurs de qualité sont testés sur un certain nombre de problèmes simples en 2D et en 3D. Après avoir prouvé leur capacité à caractériser la qualité de la discrétisation des modèles d'éléments finis, nous les avons testés sur le cas d'une excavation de palplanches butonnées (site expérimental de Hochstetten, près de Karlsruhe). La précision des résultats en termes de propriétés mécaniques choisies pour le sol et les structures n'a pas été étudiée. Nous avons également démontré que les résultats sont indépendants des propriétés mécaniques choisies pour le sol ou la structure / The thesis proposes to study the accuracy of the finite element method (FEM) analyses by means of « quality indicators ». The quality indicators represent simple mathematical formulas that are designed to evaluate the reliability of the numerical analyses. The accuracy of the discretization modeling of these analyses is determined ; the mathematical model is considered correct and the errors resulting from the choice of the mechanical properties of the soil are not taken into account. We proposed the mathematical formulations of the quality indicators and also established their lower and upper bounds. Due to their simple mathematical formulation, the quality indicators are easily implemented in any finite element computer code. We have introduced them in the CESAR-LCPC finite element computer code, namely in the nonlinear mechanical execution module. The proposed quality indicators are used on a number of simple 2D and 3D problems elastic and elastoplastic problems in order to assess the jump in stress values in the nodes of the generated mesh. After testing the accuracy of the discretization modeling of these numerical analyses, we evaluated the discretization modeling quality of a braced sheetpile excavation (Hochstetten experimental site, near Karlsruhe). The accuracy of the results based on the mechanical properties of the soil and the structure has not been studied. Also, we proved that the quality indicator results are independent of the chosen mechanical properties for the soil or structure