The goal of this thesis is to study the complexity of NP-Hard problems, using the Max-Cut and the Max-k-Cut problems, and the study of fitness landscapes. The Max-Cut and Max-k-Cut problems are well studied NP-hard problems specially since the approximation algorithm of Goemans and Williamson (1995) which introduced the use of SDP to solve relaxed problems. In order to prove the existence of a performance guarantee, the rounding step from the SDP solution to a Max-Cut solution is simple and randomized. For the Max-k-Cut problem, there exist several approximation algorithms but many of them have been proved to be equivalent. Similarly as in Max-Cut, these approximation algorithms use a simple randomized rounding to be able to get a performance guarantee. Ignoring for now the performance guarantee, one could ask if there is a rounding process that takes into account the structure of the relaxed solution since it is the result of an optimization problem. In this thesis we answered this question positively by using clustering as a rounding method. In order to compare the performance of both algorithms, a series of experiments were performed using the so-called G-set benchmark for the Max-Cut problem and using the Random Graph Benchmark of Goemans1995 for the Max-k-Cut problem. With this new rounding, larger cut values are found both for the Max-Cut and the Max-k-Cut problems, and always above the value of the performance guarantee of the approximation algorithm. This suggests that taking into account the structure of the problem to design algorithms can lead to better results, possibly at the cost of a worse performance guarantee. An example for the vertex k-center problem can be seen in Garcia-Diaz et al. (2017), where a 3-approximation algorithm performs better than a 2-approximation algorithm despite having a worse performance guarantee. Landscapes over discrete configurations spaces are an important model in evolutionary and structural biology, as well as many other areas of science, from the physics of disordered systems to operations research. A landscape is a function defined on a very large discrete set V that carries an additional metric or at least topological structure into the real numbers R. We will consider landscapes defined on the vertex set of undirected graphs. Thus let G=G(V,E) be an undirected graph and f an arbitrary real-valued function taking values from V . We will refer to the triple (V,E,f) as a landscape over G. We say two configurations x,y in V are neutral if f(x)=f(y). We colloquially refer to a landscape as 'neutral'' if a substantial fraction of adjacent pairs of configurations are neutral. A flat landscape is one where f is constant. The opposite of flatness is ruggedness and it is defined as the number of local optima or by means of pair correlation functions. These two key features of a landscape, ruggedness and neutrality, appear to be two sides of the same coin. Ruggedness can be measured either by correlation properties, which are sensitive to monotonic transformation of the landscape, and by combinatorial properties such as the lengths of downhill paths and the number of local optima, which are invariant under monotonic transformations. The connection between the two views has remained largely unexplored and poorly understood. For this thesis, a survey on fitness landscapes is presented, together with the first steps in the direction to find this connection together with a relation between the covariance matrix of a random landscape model and its ruggedness.

Falls and related injuries have affected residents in long-term care facilities for many years. It has been well-established that patient fall prevention includes staff education and hourly rounding in addition to adequate risk assessment. These steps, taken together, have the potential to decrease a 52.7% fall rate on the long-term care pilot unit. The purpose of this quality improvement project was to: (a) educate staff on the process of properly performing hourly rounding and (b) and achieve a decreased incidence of falls from the current fall rate. Thus, the practice-focused question for the project addressed whether rounding hourly on patients in a long-term care facility would decrease the numbers of falls and related injuries. The conceptual framework used for this evidence-based project was the Institute for Healthcare Improvement's rapid cycle improvement. A sample size of 40 residents' fall rates were compared for a 6-week period before the intervention of hourly rounding to the fall rates after 6 weeks of full implementation of the rounding process. A Wilcoxon Signed Ranks test (z = -4.169, p < .001) showed that there was a statistically significant improvement in staff knowledge when mean pretest scores (75.9%) were compared to posttest scores (94.5%). Nursing staff were also evaluated on competencies, and 100% of the staff successfully completed the competency checklist on the first attempt. Post project fall rates revealed a decreased fall rate by 22% over a 6-week period post implementation. Nursing leadership should ensure that staff are continually educated on policies being implemented to ensure an effective outcome. Having hourly rounding as a permanent policy can decrease the patient's fall rate and improve patient safety, a positive social change.

An evidence-based leadership (EBL) framework is an intervention designed to facilitate organizational changes such as the reduction of nursing turnover and the improvement of nursing job enjoyment. This project provides an overview of the effect of nursing turnover on an organization, presents the components of the EBL framework, and provides an evaluation of the influence of EBL on nursing turnover and job enjoyment. The EBL framework provided a method for reducing variance in leadership skill and behavior by outlining specific methods necessary to reduce inconsistency. The project objective was to determine if the implementation of an EBL framework for 820 nursing staff in 10 clinical units at a tertiary medical center improved turnover and job satisfaction, as evidenced by turnover data from the unit-specific dashboards and the National Database of Nursing Quality Indicators (NDNQI) job enjoyment scores. All data were collected retrospectively, pre-implementation to post-implementation of the EBL framework, to determine whether significant improvement occurred in turnover percentages and job enjoyment scores. Results of a t test indicated no statistically significant improvement in turnover percentages or job enjoyment scores 7 months after the implementation of the EBL framework. The nonsignificant results could be attributed to several factors including senior leadership turnover, lack of specific accountability measures for failure to implement the EBL framework (insert comma here) and the restricted time frame of the evaluation period. Despite these nonsignificant results, the evaluation provides a baseline for future longitudinal studies to determine if an EBL framework can influence nursing turnover and job enjoyment after having been in place longer than the 7 months post implementation used for this evaluation.

During mitosis, adherent animal cells undergo a drastic shape change, from essentially flat to round, in a process known as mitotic cell rounding (MCR). The aim of this thesis was to critically examine the physical and biological basis of MCR. The experimental part of this thesis employed a combined optical microscope-atomic force microscope (AFM) setup in conjunction with flat tipless cantilevers to analyze cell mechanics, shape and volume. To this end, two AFM assays were developed: the constant force assay (CFA), which applies constant force to cells and measures the resultant height, and the constant height assay (CHA), which confines cell height and measures the resultant force. These assays were deployed to analyze the shape and mechanical properties of single cells trans-mitosis. The CFA results showed that cells progressing through mitosis could increase their height against forces as high as 50 nN, and that higher forces can delay mitosis in HeLa cells. The CHA results showed that mitotic cells confined to ~50% of their normal height can generate forces around 50-100 nN without disturbing mitotic progression. Such forces represent intracellular pressures of at least 200 Pascals and cell surface tensions of around 10 nN/µm. Using the CHA to compare mitotic cell rounding with induced cell rounding, it was observed that the intracellular pressure of mitotic cells is at least 3-fold higher than rounded interphase cells. To investigate the molecular basis of the mechanical changes inherent in mitotic cell rounding, inhibitors and toxins were used to pharmacologically dissect the role of candidate cellular processes. These results implicated the actomyosin cortex and osmolyte transporters, the most prominent of which is the Na+/H+ exchanger, in the maintenance of mechanical properties and intracellular hydrostatic pressure. Observations on blebbing cells under the cantilever supported the idea that the actomyosin cortex is required to sustain hydrostatic pressure and direct this pressure into cell shape changes. To gain further insight into the relationship between actomyosin activity and intracellular pressure, dynamic perturbation experiments were conducted. To this end, the CHA was used to evaluate the pressure and volume of mitotic cells before, during and after dynamic perturbations that included tonic shocks, influx of specific inhibitors, and exposure to pore-forming toxins. When osmotic pressure gradients were depleted, pressure and volume decreased. When the actomyosin cytoskeleton was abolished, cell volume increased while rounding pressure decreased. Conversely, stimulation of actomyosin cortex contraction triggered an increase in rounding pressure and a decrease in volume. Taken together, the dynamic perturbation results demonstrated that the actomyosin cortex contracts against an opposing intracellular pressure and that this relationship sets the surface tension, pressure and volume of the cell. The discussion section of this thesis provides a comprehensive overview of the physical basis of MCR by amalgamating the experimental results of this thesis with the literature. Additionally, the biochemal signaling pathways and proteins that drive MCR are collated and discussed. An exhaustive and unprecedented synthesis of the literature on cell rounding (approx. 750 papers as pubmed search hits on “cell rounding”, April 2012) reveals that the spread-to-round transition can be thought of in terms of a surface tension versus adhesion paradigm, and that cell rounding can be physically classified into four main modes, of which one is an MCR-like category characterized by increased actomyosin cortex tension and diminution of focal adhesions. The biochemical pathways and signaling patterns that correspond with these four rounding modes are catalogued and expounded upon in the context of the relevant physiology. This analysis reveals cell rounding as a pertinent topic that can be leveraged to yield insight into core principles of cell biophysics and tissue organization. It furthermore highlights MCR as a model problem to understand the adhesion versus cell surface tension paradigm in cells and its fundamentality to cell shape, mechanics and physiology.

During mitosis, adherent animal cells undergo a drastic shape change, from essentially flat to round, in a process known as mitotic cell rounding (MCR). The aim of this thesis was to critically examine the physical and biological basis of MCR. The experimental part of this thesis employed a combined optical microscope-atomic force microscope (AFM) setup in conjunction with flat tipless cantilevers to analyze cell mechanics, shape and volume. To this end, two AFM assays were developed: the constant force assay (CFA), which applies constant force to cells and measures the resultant height, and the constant height assay (CHA), which confines cell height and measures the resultant force. These assays were deployed to analyze the shape and mechanical properties of single cells trans-mitosis. The CFA results showed that cells progressing through mitosis could increase their height against forces as high as 50 nN, and that higher forces can delay mitosis in HeLa cells. The CHA results showed that mitotic cells confined to ~50% of their normal height can generate forces around 50-100 nN without disturbing mitotic progression. Such forces represent intracellular pressures of at least 200 Pascals and cell surface tensions of around 10 nN/µm. Using the CHA to compare mitotic cell rounding with induced cell rounding, it was observed that the intracellular pressure of mitotic cells is at least 3-fold higher than rounded interphase cells. To investigate the molecular basis of the mechanical changes inherent in mitotic cell rounding, inhibitors and toxins were used to pharmacologically dissect the role of candidate cellular processes. These results implicated the actomyosin cortex and osmolyte transporters, the most prominent of which is the Na+/H+ exchanger, in the maintenance of mechanical properties and intracellular hydrostatic pressure. Observations on blebbing cells under the cantilever supported the idea that the actomyosin cortex is required to sustain hydrostatic pressure and direct this pressure into cell shape changes. To gain further insight into the relationship between actomyosin activity and intracellular pressure, dynamic perturbation experiments were conducted. To this end, the CHA was used to evaluate the pressure and volume of mitotic cells before, during and after dynamic perturbations that included tonic shocks, influx of specific inhibitors, and exposure to pore-forming toxins. When osmotic pressure gradients were depleted, pressure and volume decreased. When the actomyosin cytoskeleton was abolished, cell volume increased while rounding pressure decreased. Conversely, stimulation of actomyosin cortex contraction triggered an increase in rounding pressure and a decrease in volume. Taken together, the dynamic perturbation results demonstrated that the actomyosin cortex contracts against an opposing intracellular pressure and that this relationship sets the surface tension, pressure and volume of the cell. The discussion section of this thesis provides a comprehensive overview of the physical basis of MCR by amalgamating the experimental results of this thesis with the literature. Additionally, the biochemal signaling pathways and proteins that drive MCR are collated and discussed. An exhaustive and unprecedented synthesis of the literature on cell rounding (approx. 750 papers as pubmed search hits on “cell rounding”, April 2012) reveals that the spread-to-round transition can be thought of in terms of a surface tension versus adhesion paradigm, and that cell rounding can be physically classified into four main modes, of which one is an MCR-like category characterized by increased actomyosin cortex tension and diminution of focal adhesions. The biochemical pathways and signaling patterns that correspond with these four rounding modes are catalogued and expounded upon in the context of the relevant physiology. This analysis reveals cell rounding as a pertinent topic that can be leveraged to yield insight into core principles of cell biophysics and tissue organization. It furthermore highlights MCR as a model problem to understand the adhesion versus cell surface tension paradigm in cells and its fundamentality to cell shape, mechanics and physiology.

Nesta tese propõe-se um método heurístico para o problema de Projeto de Rede da Cadeia de Suprimentos (Supply Chain Network Design) considerando vários aspectos de relevância prática, tais como: fornecedores e matérias-primas, localização e operação de instalações, atribuição de Centros de Distribuição (CD), e grande número de clientes e produtos. Uma eficiente abordagem heurística de duas fases é proposta para a obtenção de soluções viáveis para os problemas, que inicialmente é modelado como um Programa Linear Inteiro Misto (PLIM) de grande escala. Na fase de construção, uma estratégia de Linear Programming Rounding é aplicada para se obter os valores iniciais para as variáveis de localização inteira do modelo. Simultaneamente, um método Multi-start foi desenvolvido para gerar soluções iniciais diversificadas para cada nova iteração da heurística de Rounding. Na segunda fase, dois procedimentos de Busca Local foram desenvolvidos no sentido de melhorar a solução fornecida pelo método de Rounding. Implementamos duas diferentes abordagens de Busca Local: remoção-inserção e troca. Uma técnica de Busca Tabu para orientar o procedimento de Busca Local para explorar os diferentes espaços de soluções foi desenvolvida. As formulações e algoritmos foram implementados na linguagem C++ utilizando ferramentas de otimização da COIN-OR. O método de solução foi experimentado em instâncias geradas aleatoriamente, com tamanhos diferentes em termos do número de parâmetros, tais como o número de produtos, zonas de clientes, CDs e fábricas considerando um sistema logístico de quatro níveis. As implementações computacionais mostram que o método de solução proposto obteve resultados satisfatórios quando comparados com a literatura. Para validar este método heurístico também foi usado em um caso realista, com base em dados de uma empresa de borracha que está reestruturando sua cadeia de suprimentos devido ao projeto de uma nova uma nova fábrica e produção de novos produtos. A abordagem heurística proposta revelou-se adequada para aplicação prática em um caso real de uma indústria multicommodity em um contexto determinístico. / In this thesis we propose a heuristic method for the Supply Chain Network Design (SCND) problem considering several aspects of practical relevance: suppliers and raw materials, location and operation facilities, distribution center (DC) assignments, and large numbers of customers and products. An efficient two-phase heuristic approach is proposed for obtaining feasible solutions to the problems, which is initially modeled as a large-scale Mixed Integer Linear Program (MILP). In the construction phase, a linear programming rounding strategy is applied to obtain initial values for the integer location variables in the model. Simultaneously, a Multi-start method was developed to generate diversified initial solutions from each new iteration in the rounding heuristic. In the second phase, two Local Search procedures were developed towards to improve the solution provided by the rounding method. We implemented two different Local Search approaches: removal-insertion and exchange. A Tabu Search technique was developed to guide the Local Search procedure to explore the different spaces of solutions. The formulations and algorithms were implemented in C++ code language using the optimization engine COIN-OR. The solution method was experimented in randomly generated instances, with different sizes in terms of the number of parameters, such as number of products, customer zones, DCs, and factories considering a four-echelon logistic system. The computational implementations show that the solution method proposed obtained satisfactory results when compared to the literature review. To validate this heuristic method was also used in a realistic case, based on data from a rubber company that is restructuring its supply chain due to the overture of a new factory, producing new products. The proposed heuristic approach proved appropriate to practical application in a realistic case of a multi commodity industry in a deterministic context.

Les systèmes critiques basés sur l’arithmétique flottante exigent un processus rigoureux de vérification et de validation pour augmenter notre confiance en leur sureté et leur fiabilité. Malheureusement, les techniques existentes fournissent souvent une surestimation d’erreurs d’arrondi. Nous citons Arian 5 et le missile Patriot comme fameux exemples de désastres causés par les erreurs de calculs. Ces dernières années, plusieurs techniques concernant la transformation d’expressions arithmétiques pour améliorer la précision numérique ont été proposées. Dans ce travail, nous allons une étape plus loin en transformant automatiquement non seulement des expressions arithmétiques mais des programmes complets contenant des affectations, des structures de contrôle et des fonctions. Nous définissons un ensemble de règles de transformation permettant la génération, sous certaines conditions et en un temps polynômial, des expressions pluslarges en appliquant des calculs formels limités, au sein de plusieurs itérations d’une boucle. Par la suite, ces larges expressions sont re-parenthésées pour trouver la meilleure expression améliorant ainsi la précision numérique des calculs de programmes. Notre approche se base sur les techniques d’analyse statique par interprétation abstraite pour sur-rapprocher les erreurs d’arrondi dans les programmes et au moment de la transformation des expressions. Cette approche est implémenté dans notre outil et des résultats expérimentaux sur des algorithmes numériques classiques et des programmes venant du monde d’embarqués sont présentés. / Critical software based on floating-point arithmetic requires rigorous verification and validation process to improve our confidence in their reliability and their safety. Unfortunately available techniques for this task often provide overestimates of the round-off errors. We can cite Arian 5, Patriot rocket as well-known examples of disasters. These last years, several techniques have been proposed concerning the transformation of arithmetic expressions in order to improve their numerical accuracy and, in this work, we go one step further by automatically transforming larger pieces of code containing assignments, control structures and functions. We define a set of transformation rules allowing the generation, under certain conditions and in polynomial time, of larger expressions by performing limited formal computations, possibly among several iterations of a loop. These larger expressions are better suited to improve, by re-parsing, the numerical accuracy of the program results. We use abstract interpretation based static analysis techniques to over-approximate the round-off errors in programs and during the transformation of expressions. A tool has been implemented and experimental results are presented concerning classical numerical algorithms and algorithms for embedded systems.

Graph partitioning is a fundamental optimization problem that has been intensively studied. Many graph partitioning formulations are important as building blocks for divide-and-conquer algorithms on graphs as well as to many applications such as VLSI layout, packet routing in distributed networks, clustering and image segmentation. Unfortunately such problems are notorious for the huge gap between known best known approximation algorithms and hardness of approximation results. In this thesis, we study approximation algorithms for graph partitioning problems using a strong hierarchy of relaxations based on semi-definite programming, called Lasserre Hierachy. Our main contribution in this thesis is a propagation based rounding framework for solutions arising from such relaxations. We present a novel connection between the quality of solutions it outputs and column based matrix reconstruction problem. As part of our work, we derive optimal bounds on the number of columns necessary together with efficient randomized and deterministic algorithms to find such columns. Using this framework, we derive approximation schemes for many graph partitioning problems with running times dependent on how fast the graph spectrum grows. Our final contribution is a fast SDP solver for this rounding framework: Even though SDP relaxation has nO(r) many variables, we achieve running times of the form 2O(r) poly(n) by only partially solving the relevant part of relaxation. In order to achieve this, we present a new ellipsoid algorithm that returns certificate of infeasibility.

La conception des bibliothèques d’évaluation de fonctions est un activité complexe qui requiert beaucoup de soin et d’application, particulièrement lorsque l’on vise des niveaux élevés de fiabilité et de performances. En pratique et de manière habituelle, on ne peut se livrer à ce travail sans disposer d’outils qui guident le concepteur dans le dédale d’un espace de solutions étendu et complexe mais qui lui garantissent également la correction et la quasi-optimalité de sa production. Dans l’état actuel de l’art, il nous faut encore plutôt raisonner en termes de « boite à outils » d’où le concepteur doit tirer et combiner des mécanismes de base, au mieux de ses objectifs, plutôt qu’imaginer que l’on dispose d’un dispositif à même de résoudre automatiquement tous les problèmes.Le présent travail s’attache à la conception et la réalisation de tels outils dans deux domaines:∙ la consolidation du test d’arrondi de Ziv utilisé, jusqu’à présent de manière plus ou moins empirique, dans l’implantation des approximations de fonction ;∙ le développement d’une implantation de l’algorithme SLZ dans le but de résoudre le « Dilemme du fabricant de table » dans le cas de fonctions ayant pour opérandes et pour résultat approché des nombres flottants en quadruple précision (format Binary64 selon la norme IEEE-754). / The design of function evaluation libraries is a complex task that requires a great care and dedication, especially when one wants to satisfy high standards of reliability and performance. In actual practice, it cannot be correctly performed, as a routine operation, without tools that not only help the designer to find his way in a complex and extended solution space but also to guarantee that his solutions are correct and (almost) optimal. As of the present state of the art, one has to think in terms of “toolbox” from which he can smartly mix-and-match the utensils that fit better his goals rather than expect to have at hand a solve-all automatic device.The work presented here is dedicated to the design and implementation of such tools in two realms:∙ the consolidation of Ziv’s rounding test that is used, in a more or less empirical way, for the implementation of functions approximation;∙ the development of an implementation of the SLZ-algorithm in order to solve the Table Maker Dilemma for the function with quad-precision floating point (IEEE-754 Binary128 format) arguments and images.

Nesta tese propõe-se um método heurístico para o problema de Projeto de Rede da Cadeia de Suprimentos (Supply Chain Network Design) considerando vários aspectos de relevância prática, tais como: fornecedores e matérias-primas, localização e operação de instalações, atribuição de Centros de Distribuição (CD), e grande número de clientes e produtos. Uma eficiente abordagem heurística de duas fases é proposta para a obtenção de soluções viáveis para os problemas, que inicialmente é modelado como um Programa Linear Inteiro Misto (PLIM) de grande escala. Na fase de construção, uma estratégia de Linear Programming Rounding é aplicada para se obter os valores iniciais para as variáveis de localização inteira do modelo. Simultaneamente, um método Multi-start foi desenvolvido para gerar soluções iniciais diversificadas para cada nova iteração da heurística de Rounding. Na segunda fase, dois procedimentos de Busca Local foram desenvolvidos no sentido de melhorar a solução fornecida pelo método de Rounding. Implementamos duas diferentes abordagens de Busca Local: remoção-inserção e troca. Uma técnica de Busca Tabu para orientar o procedimento de Busca Local para explorar os diferentes espaços de soluções foi desenvolvida. As formulações e algoritmos foram implementados na linguagem C++ utilizando ferramentas de otimização da COIN-OR. O método de solução foi experimentado em instâncias geradas aleatoriamente, com tamanhos diferentes em termos do número de parâmetros, tais como o número de produtos, zonas de clientes, CDs e fábricas considerando um sistema logístico de quatro níveis. As implementações computacionais mostram que o método de solução proposto obteve resultados satisfatórios quando comparados com a literatura. Para validar este método heurístico também foi usado em um caso realista, com base em dados de uma empresa de borracha que está reestruturando sua cadeia de suprimentos devido ao projeto de uma nova uma nova fábrica e produção de novos produtos. A abordagem heurística proposta revelou-se adequada para aplicação prática em um caso real de uma indústria multicommodity em um contexto determinístico. / In this thesis we propose a heuristic method for the Supply Chain Network Design (SCND) problem considering several aspects of practical relevance: suppliers and raw materials, location and operation facilities, distribution center (DC) assignments, and large numbers of customers and products. An efficient two-phase heuristic approach is proposed for obtaining feasible solutions to the problems, which is initially modeled as a large-scale Mixed Integer Linear Program (MILP). In the construction phase, a linear programming rounding strategy is applied to obtain initial values for the integer location variables in the model. Simultaneously, a Multi-start method was developed to generate diversified initial solutions from each new iteration in the rounding heuristic. In the second phase, two Local Search procedures were developed towards to improve the solution provided by the rounding method. We implemented two different Local Search approaches: removal-insertion and exchange. A Tabu Search technique was developed to guide the Local Search procedure to explore the different spaces of solutions. The formulations and algorithms were implemented in C++ code language using the optimization engine COIN-OR. The solution method was experimented in randomly generated instances, with different sizes in terms of the number of parameters, such as number of products, customer zones, DCs, and factories considering a four-echelon logistic system. The computational implementations show that the solution method proposed obtained satisfactory results when compared to the literature review. To validate this heuristic method was also used in a realistic case, based on data from a rubber company that is restructuring its supply chain due to the overture of a new factory, producing new products. The proposed heuristic approach proved appropriate to practical application in a realistic case of a multi commodity industry in a deterministic context.