蔡玄暉. / Submitted: Dec. 2009. / Thesis (doctoral)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (p. 371-382). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in Chinese and English. / Cai Xuanhui.

Un des problemes majeurs dans le domaine des telecommunications est de construire des réseaux robustes qui puissent faire face a l'incertitude de la demande. Ayant l'architecture d'un réseau et un budget donne pour le problème d'allocation de la capacité, le but est d'identifier une capacité faisable, qui minimise le pire cas de demande insatisfaite. Premièrement, nous formulons l'incertitude de la demande comme un polytope engendre par un nombre fini de scénarios de la demande. Nous montrons que le problème peut se ramener a la minimisation d'une fonction convexe sur un polyèdre. Nous calculons alors une solution optimale par trois méthodes de plans sécants : Kelley, Elzinga & Moore et faisceaux. Ensuite, nous formulons l'incertitude comme un polyèdre décrit par un nombre fini d'inégalités linéaires, ce qui résulte en un problème considérablement plus difficile. Par conséquent, nous cherchons uniquement des bornes supérieures et inférieures. Quelques idées novatrices sont présentées et l'algorithme de type \Branch & Bound" de Falk & Soland est utilise afin de calculer le maximum d'une fonction convexe additive ; de plus, nous défifinissons une variante de cet algorithme, adaptée a notre situation particulière. Après avoir défini la capacité d'un réseau, l'étape suivante est de calculer le routage optimal dans ce réseau. Nous minimisons la congestion en utilisant comme objectif la fonction moyenne de retard de Kleinrock. Le problème résultant est convexe mais non-linaire et la fonction duale est la somme d'un terme polyédral et d'un terme différentiable. Afin de résoudre ce problème, nous implémentons un algorithme hybride base sur la relaxation Lagrangienne.

Bacterial cell division requires formation of the cytokinetic cell division septum at the mid-cell position, a process that is determined by three Min proteins; MinC, MinD and MinE. Regulation of cell division by Min proteins occurs via a multi-step process involving interactions between various Min proteins, as well as the membrane. In this cycle, ATP-bound MinD binds to the membrane surface where it can recruit MinC to inhibit formation of the cell division septum. MinE binding to this complex displaces MinC and stimulates ATP hydrolysis, leading to the dissociation of MinD from the membrane. These interactions give rise to a dynamic pattern of Min protein localization that appears to involve a polymeric state that is designed to create a zone that is permissive to cell division at the mid-point of the cell. The interaction between MinD and the membrane is a critical aspect of this cycle, yet the role of the lipid bilayer in MinD activation, localization and polymerization is not well understood. To probe the role of membrane charge and fluidity on MinD activation and polymerization, we developed a kinetic assay of MinE-stimulated MinD ATPase activity. We found that membrane charge is essential for MinD activation and that differences in membrane fluidity give rise to changes in its activity. Moreover, a burst phase was also observed during the first few minutes of reaction, but only on the most fluid anionic lipid tested. To help determine if the observed membrane-dependent changes in MinD activity are linked to any changes in MinD polymer structure, we have begun to develop a method to identify surface exposed regions of MinD through a combination of covalent labeling and mass spectrometry. Optimization of various steps for the assay has been done, and the assay can be applied to the future characterization of MinD polymer structure. Results from this assay, in combination with those from the kinetic measurements described here, will help to improve understanding about how membrane properties modulate MinD ATPase activity, and how this can influence the Min protein oscillation that is required to ensure normal bacterial cell division.

We study computational theory and methods for finding multiple unstable solutions (corresponding to saddle points) to three types of nonlinear variational elliptic systems: cooperative, noncooperative, and Hamiltonian. We first propose a new Lorthogonal selection in a product Hilbert space so that a solution manifold can be defined. Then, we establish, respectively, a local characterization for saddle points of finite Morse index and of infinite Morse index. Based on these characterizations, two methods, called the local min-orthogonal method and the local min-max-orthogonal method, are developed and applied to solve those three types of elliptic systems for multiple solutions. Under suitable assumptions, a subsequence convergence result is established for each method. Numerical experiments for different types of model problems are carried out, showing that both methods are very reliable and efficient in computing coexisting saddle points or saddle points of infinite Morse index. We also analyze the instability of saddle points in both single and product Hilbert spaces. In particular, we establish several estimates of the Morse index of both coexisting and non-coexisting saddle points via the local min-orthogonal method developed and propose a local instability index to measure the local instability of both degenerate and nondegenerate saddle points. Finally, we suggest two extensions of an L-orthogonal selection for future research so that multiple solutions to more general elliptic systems such as nonvariational elliptic systems may also be found in a stable way.

Thesis (Ph. D.)--Stanford University, 1953.

published_or_final_version / Linguistics / Doctoral / Doctor of Philosophy

Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.

Bacterial cell division requires formation of the cytokinetic cell division septum at the mid-cell position, a process that is determined by three Min proteins; MinC, MinD and MinE. Regulation of cell division by Min proteins occurs via a multi-step process involving interactions between various Min proteins, as well as the membrane. In this cycle, ATP-bound MinD binds to the membrane surface where it can recruit MinC to inhibit formation of the cell division septum. MinE binding to this complex displaces MinC and stimulates ATP hydrolysis, leading to the dissociation of MinD from the membrane. These interactions give rise to a dynamic pattern of Min protein localization that appears to involve a polymeric state that is designed to create a zone that is permissive to cell division at the mid-point of the cell. The interaction between MinD and the membrane is a critical aspect of this cycle, yet the role of the lipid bilayer in MinD activation, localization and polymerization is not well understood. To probe the role of membrane charge and fluidity on MinD activation and polymerization, we developed a kinetic assay of MinE-stimulated MinD ATPase activity. We found that membrane charge is essential for MinD activation and that differences in membrane fluidity give rise to changes in its activity. Moreover, a burst phase was also observed during the first few minutes of reaction, but only on the most fluid anionic lipid tested. To help determine if the observed membrane-dependent changes in MinD activity are linked to any changes in MinD polymer structure, we have begun to develop a method to identify surface exposed regions of MinD through a combination of covalent labeling and mass spectrometry. Optimization of various steps for the assay has been done, and the assay can be applied to the future characterization of MinD polymer structure. Results from this assay, in combination with those from the kinetic measurements described here, will help to improve understanding about how membrane properties modulate MinD ATPase activity, and how this can influence the Min protein oscillation that is required to ensure normal bacterial cell division.

Thesis (M.A.)--University of Hawaii at Manoa, 2005. / Includes bibliographical references (leaves 45-50). / ix, 71 leaves, bound 29 cm

This study investigates the polysemy of the preposition מִן (min) in Biblical Hebrew. The complexity relating to the senses of this preposition has long been recognised, but existing sources differ about the primary sense of מִן (min), as well as the delimitation of the derived senses. In order to provide a more systematic account of the senses of מִן (min) the principled polysemy approach, which was developed by Tyler and Evans (2003), was employed. This methodology is grounded in the theoretical framework of cognitive semantics. The criteria provided for determining the primary sense point to a sense in which מִן (min) indicates both locational source and separation. These two elements are both present in the primary sense. By applying criteria for determining distinct senses, ten additional usages of מִן (min) were identified, namely, material source, partitive, cause, agent, origin, position, exception, comparison, negative consequence, and time. It was shown that all these senses are related to the primary sense in a substantiated way. A semantic network for the preposition מִן (min) was proposed in which it was shown that half of the senses are more related to the source element in the primary sense and the other half to the separation element of the primary sense. / MA (Semitic Languages), North-West University, Potchefstroom Campus, 2014