Fundação de Amparo a Pesquisa no Estado do Rio Grande do Sul / In this work we present the lifting method [AS2], which is used to classify certain class of Hopf algebras. Since this method is based on the coradical filtration, it can be used just for those Hopf algebras satisfying the Chevalley property (CP). Results related to the explicit calculation of such filtration are also explored. Finally, we study the standard filtration, which is defined in [AC], and which allows us to extend the lifting method to the non-(CP) case. / Neste trabalho apresentamos o método de lifting [AS2], o qual é utilizado para a classificação de certa classe de álgebras de Hopf. Desde que este método baseia-se na filtração coradical, ele não pode ser utilizado para aquelas que satisfazem a propriedade Chevalley (PC). Resultados relacionados com o cálculo explícito de tal filtração também são explorados. Na parte final, estudamos a filtração standard, que está definida em [AC], e que nos permite estender o método de lifting ao caso não (PC).

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Um conjunto independente de um grafo à um subconjunto de vÃrtices que nÃo contÃm nenhum par de vÃrtices vizinhos. O problema do maior conjunto independente consiste em encontrar um conjunto independente de cardinalidade mÃxima. O problema do maior subgrafo induzido k-partido consiste em encontrar k conjuntos independentes cuja uniÃo tenha cardinalidade mÃxima. AlÃm de possuÃrem aplicaÃÃo em diversas Ãreas, como visÃo computacional, biologia molecular e projeto de circuitos integrados, estes problemas tambÃm modelam outros problemas de otimizaÃÃo combinatÃria, como empacotamento de conjuntos e coloraÃÃo de vÃrtices. Neste trabalho, estudamos os politopos associados aos dois problemas. Primeiro, descrevemos um novo procedimento de geraÃÃo de facetas para o politopo de conjuntos independentes, que unifica e generaliza diversos procedimentos anteriores. AlÃm de gerar vÃrias classes de desigualdades indutoras de facetas jà conhecidas, este procedimento tambÃm gera novas desigualdades que ainda nÃo foram descritas na literatura. Em seguida, estudamos o politopo do subgrafo induzido k-partido associado à formulaÃÃo por representantes de cor. Identificamos suas facetas mais simples, mostramos que facetas podem ser geradas a partir de subgrafos induzidos, e descrevemos duas classes de subgrafos que geram facetas deste politopo. Para obter os principais resultados desta dissertaÃÃo, fazemos um estudo da relaÃÃo de afim-isomorfismo entre poliedros, e desenvolvemos um novo procedimento de conversÃo de faces em facetas que generaliza as diversas versÃes do procedimento de levantamento de variÃveis. / A stable set of a graph is a set of pairwise non-adjacent vertices. The maximum stable set problem is to find a stable set of maximum cardinality in a given graph. The maximum induced k-partite subgraph problem is to find k stable sets such that their union has maximum cardinality. Besides having applications in various fields, including computer vision, molecular biology and VLSI circuit design, these problems also model other important combinatorial problems, such as set packing and vertex coloring. In the present work, we study the facial structure of the polytopes associated with both problems. First, we describe a new facet generating procedure for the stable set polytope, which unifies and subsumes several previous procedures. Besides generating many well-known facet inducing inequalities, this procedure can also generate new facet-inducing inequalities which have not been previously described. Then, we study the maximum induced k-partite polytope formulated by asymmetric representatives. We describe its simplest facets, show that some of its facets arise from vertex induced subgraphs, and identify two classes of subgraphs which generate facets of the polytope. To reach these main results, we study the affine equivalence between polyhedra, and also develop a new facet generating procedure for general polyhedra which subsumes the many versions of the lifting of variables.

Avaliar a biocompatibilidade do fio lifting biológico - fio serrilhado de poliuretana de óleo de mamona - e sua eficácia no rejuvenescimento facial. Na primeira etapa deste trabalho implantamos os fios no dorso de camundongos, que foram sacrificados com 03, 07, 15 e 30 dias com posterior análise histológica por microscopia óptica. Na segunda fase implantamos os fios na face de pacientes com flacidez dérmica e analisamos, fotograficamente e através de uma modelagem numérico-computacional o resultado (rejuvenescimento), com intervalos entre 07 e 60 dias. As análises histológicas demonstraram uma rápida integração do fio ao tecido celular subcutâneo com formação abundante de colágeno e as fotografias dos pacientes revelaram uma maior firmeza da derme e um rejuvenescimento facial, comprovados pela análise computacional. Suas características químicas e físicas e os resultados iniciais nos permitem acreditar que o fio lifting biológico - fio serrilhado de poliuretana do óleo de mamona - apresenta elevada biocompatibilidade com uma rápida integração ao tecido subcutâneo sendo uma excelente opção no rejuvenescimento facial. / Evaluate the biological lifting thread - castor oil polyurethane serrulate thread - bio-compatibility and it´s eficacy on facial rejuvenation. At first we implanted the threads in subcutaneous tissues on mice backs that were sacrificed after 03, 07, 15 and 30 days, followed by histological analysis of material by using optical microscopy. Later, implants were carried out in patients with facial dermal flaccidity, and comparisons were made through photographs between 7 and 60 days, than we made a numerical-computational modelling comparision of this photographs. Histological analysis showed a quick thread integration with the celular subcutaneous tissue by a large amount of colagen syntesis and the patients photographs showed facial rejuvenation with improvement of the skin flaccidity comproved by numerical modelling. It`s chemical and physical characteristics and the initial results allow us belive that the biological lifting thread - castor oil polyurethane serrulate thread - has good bio-compatibility and fast integration with the celular subcutaneous tissue being an excellent option for the facial rejuvenation.

Dizertační práce se zabývá algoritmy SegDWT pro segmentový výpočet Diskrétní Waveletové Transformace – DWT jedno i vícedimenzionálních dat. Segmentovým výpočtem se rozumí způsob výpočtu waveletové analýzy a syntézy po nezávislých segmentech (blocích) s určitým překryvem tak, že nevznikají blokové artefakty. Analyzující část algoritmu pracuje na principu odstranění přesahu a produkuje vždy část waveletových koeficientů z waveletové transformace celého signálu, které mohou být následně libovolně zpracovány a podrobeny zpětné transformaci. Rekonstruované segmenty jsou pak skládány podle principu přičtení přesahu. Algoritmus SegDWT, ze kterého tato práce vychází, není v současné podobně přímo použitelný pro vícerozměrné signály. Tato práce obsahuje několik jeho modifikací a následné zobecnění pro vícerozměrné signály pomocí principu separability. Kromě toho je v práci představen algoritmus SegLWT, který myšlenku SegDWT přenáší na výpočet waveletové transformace pomocí nekauzálních struktur filtrů typu lifting.

Práce se zaměřuje na efektivní výpočet dvourozměrné diskrétní vlnkové transformace. Současné metody jsou v práci rozšířeny v několika směrech a to tak, aby spočetly tuto transformaci v jediném průchodu, a to případně víceúrovňově, použitím kompaktního jádra. Tohle jádro dále může být vhodně přeorganizováno za účelem minimalizace užití některých prostředků. Představený přístup krásně zapadá do běžně používaných rozšíření SIMD, využívá hierarchii cache pamětí moderních procesorů a je vhodný k paralelnímu výpočtu. Prezentovaný přístup je nakonec začleněn do kompresního řetězce formátu JPEG 2000, ve kterém se ukázal být zásadně rychlejší než široce používané implementace.

Thesis: M.S., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 1978 / Includes bibliographical references. / by Song Y. Chung. / M.S. / M.S. Massachusetts Institute of Technology, Department of Aeronautics and Astronautics

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programs (IP) are a commonly researched class of problems used by governments and businesses to improve decision making through optimal resource allocation and scheduling. However, integer programs require an exponential amount of effort to solve and in some instances a feasible solution is unknown even with the most powerful computers. There are several methods commonly used to reduce the solution time for IPs. One such approach is to generate new valid inequalities through lifting. Lifting strengthens a valid inequality by changing the coefficients of the variables in the inequality. Lifting can result in facet defining inequalities, which are the theoretically strongest inequalities. This thesis introduces the Cutting-plane Algorithm in Three Sets (CATS) that can help reduce the solution time of integer programs. CATS uses synchronized simultaneous lifting to generate a new class of previously undiscovered valid inequalities. These inequalities are based upon three sets of indices from a binary knapsack integer program, which is a commonly studied integer program. CATS requires quartic effort times the number of inequalities generated. Some theoretical results describe easily verifiable conditions under which CATS inequalities are facet defining. A small computational study shows CATS obtains about an 8.9% percent runtime improvement over a commercial IP software. CATS preprocessing time is fast and requires an average time of approximately .032 seconds to perform. With the exciting new class of inequalities produced relatively quickly compared to the solution time, CATS is advantageous and should be implemented to reduce solution time of many integer programs.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programs (IPs) are a commonly researched class of decision problems. These problems are used in various applications to help companies, governments, or individuals make better decisions by determining optimal resource allocations. While IPs are practical tools, they require an exponential amount of effort to solve, unless P = NP. This fact has led to much research focused on reducing the time required to solve IPs. Cutting planes are a commonly used tool for reducing IP solving time. Lifting, a process of changing the coefficients in an inequality, is often employed to strengthen cutting planes. When lifting, the goal is often to create a facet defining inequality, which is theoretically the strongest cutting plane. This thesis introduces two new lifting procedures for the Node Packing problem. The Node Packing problem seeks to select the maximum number of nodes in a graph such that no two nodes are adjacent. The first lifting method, the Simultaneous Lifting Expansion, takes two inequalities and combines them to make a stronger cut. It works for any two general classes of inequalities, as long as the requisite graph structures are met. The second method, the Cliques On Odd-holes Lifting (COOL) procedure, lifts from an odd-hole inequality to a facet defining inequality. COOL makes use of the Odd Gap Lifting procedure, an efficient method for finding lifting coefficients on odd holes. A computational study shows COOL to be effective in creating cuts in graphs with low edge densities.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programming (IP) is a powerful technique used by many companies and organizations to determine optimal strategies for making decisions and managing resources to achieve their goals. One class of IP problems is the multiple knapsack (MK) problem. However, MK and other IP problems, are extremely complicated since they are ${\cal NP}$-hard problems. Furthermore, there exist numerous instances that can not be solved. One technique commonly used to reduce the solution time for IP problems is lifting. This method, introduced by Gomory, takes an existing valid inequality and strengthens it. Lifting has the potential to form facet defining inequalities, which are the strongest inequalities to solve an IP problem. As a result, lifting is frequently used in integer programming applications. This research takes a broad approach to simultaneous lifting and provides its theoretical background for. The underlying hypergraphic structure for simultaneous lifting in an MK problem is identified and called a constellation. A constellation contains two hypercliques and multiple hyperstars from various conflict hypergraphs. Theoretical results demonstrate that a constellation induces valid inequalities that could be obtained by simultaneous lifting. Moreover, these constellation inequalities can be facet defining. The primary advancements, constellations and the associated valid inequalities, of this thesis are theoretical in nature. By providing the theory behind simultaneous lifting, researchers should be able to apply this knowledge to develop new algorithms that enable simultaneous lifting to be performed faster and over more complex integer programs.

published_or_final_version / abstract / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy