Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Minimizing the object dimensions in circle and sphere packing problems

Given a fixed set of identical or different-sized circular items, the problem we deal with consists on finding the smallest object within which the items can be packed. Circular, triangular, squared, rectangular and also strip objects are considered. Moreover, 2D and 3D problems are treated. Twice-differentiable models for all these problems are presented. A strategy to reduce the complexity of evaluating the models is employed and, as a consequence, instances with a large number of items can be considered. Numerical experiments show the flexibility and reliability of the new unified approach. (C) 2007 Elsevier Ltd. All rights reserved.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

XHA: eXtensible Hyper-Automation

O objetivo geral desta dissertação é estudar as possibilidades de flexibilização da função de saída do Sistema Hyper-Automaton além das rígidas possibilidades utilizadas atualmente com a utilização direta do HTML, objetivando eliminar as limitações como execução de aplicações proprietárias, caracteres incompatíveis entre browsers, excesso de tráfego na rede, padronizar aplicações, incrementar recursos didáticos, melhorar o suporte a aplicações multimídia atuais e futuras, facilitar a manutenção, implementação e reuso, alterar o layout de saída no browser de maneira dinâmica, explorar outros recursos de links, estabelecer padrões de organização do material instrucional criado pelo professor e muitas outras. Tal sistema anteriormente desenvolvido e funcionando adequadamente, é baseado no formalismo de Autômatos Finitos com Saída como modelo estrutural para organização de hiperdocumentos instrucionais, em especial em cursos na Web, tornando o material hipermídia independente do controle da aplicação. O Sistema Hyper-Automaton, tornou-se portanto, um sistema semi-automatizado para suporte a cursos na Web. Com o desdobramento da pesquisa, esta procurou ir mais além e descreveu possibilidades de não só estudar os aspectos possíveis de formatação de saída do sistema, mas reestruturá-lo totalmente sobre uma linguagem de markup padrão, buscando atualizá-lo tecnologicamente definindo outras possibilidades para que significativos trabalhos futuros possam de maneira mais clara serem alcançados. Dessa maneira, esta dissertação centra-se no estudo da aplicação de formas de flexibilização do Sistema Hyper-Automaton, tanto na parte da estruturação de documentos que são conteúdos instrucionais armazenados, bem como, na forma desse material tornar-se-á disponível através de navegadores WWW compatíveis com as tecnologias propostas, possibilitando o incremento substancial de funcionalidades necessárias para cursos onde a Web é o principal meio. Esta pesquisa dá prosseguimento a dois trabalhos anteriormente concluídos no PPGC e do Curso de Bacharelado em Ciência da Computação da UFRGS no ano de 2000, na seqüência, Hyper-Automaton: Hipertextos e Cursos na Web Utilizando Autômatos Finitos com Saída, dissertação de mestrado de Júlio Henrique de A. P. Machado e Hyper-Automaton: Implementação e Uso, trabalho de diplomação de Leonardo Penczek.

New technologies, old habits: automation without innovation

This research investigated the underuse of technological tools by innovative organizations which are acknowledged for their use of and familiarity with new technologies. The research conducted an analysis of 58 institutional repositories (IRs) out of 43 educational and research institutions which are internationally renowned for excellence. The core aspect of the analysis was the use of IRs for publishing and dealing with evidence in order to legitimize and add value to scientific research. The following items were analyzed: (a) the logical structuring of scientific communication published in the IRs; (b) the metadata which describe scientific communication based on the terms of the DCMI protocol used; (c) the availability of software functions which facilitate the queries and publication of evidences. Results show that the introduction of IRs did not add value to the quality of research in\ terms of associating and publishing evidence that could back them up. A strong tendency to replicate the traditional library model of physical collections was observed. It was concluded that merely possessing good technological tools is not sufficient for fostering innovation and strategic gains in organizations, even if their implementation takes place in highly promising and favorable environments.

Multicast packing problem: abordagem multiobjetivo

This work presents a algorithmic study of Multicast Packing Problem considering a multiobjective approach. The first step realized was an extensive review about the problem. This review serverd as a reference point for the definition of the multiobjective mathematical model. Then, the instances used in the experimentation process were defined, this instances were created based on the main caracteristics from literature. Since both mathematical model and the instances were definined, then several algoritms were created. The algorithms were based on the classical approaches to multiobjective optimization: NSGA2 (3 versions), SPEA2 (3 versions). In addition, the GRASP procedures were adapted to work with multiples objectives, two vesions were created. These algorithms were composed by three recombination operators(C1, C2 e C3), two operator for build solution, a mutation operator and a local search procedure. Finally, a long experimentation process was performed. This process has three stages: the first consisted of adjusting the parameters; the second was perfomed to indentify the best version for each algorithm. After, the best versions for each algorithm were compared in order to identify the best algorithm among all. The algorithms were evaluated based on quality indicators and Hypervolume Multiplicative Epsilon

Automation and cybernetics: Control of a flexible one-link manipulator

States that control is of the essence in cybernetics. Summarizes the dynamic equations for a flexible one-link manipulator moving in the horizontal plane. Employs the finite element method, based on elementary beam theory, during the process of formulation. Develops and instruments a one-link flexible manipulator in order to control its vibration modes. Uses a simple second-order vibration model which permits vibrations on the rod to be estimated using the hub angle. The validation of the dynamic model and the structural analysis of the flexible manipulator is reached using proper infrared cameras and active light sources for determining actual positions of objects in space. Shows that the performance of the control is satisfactory, even under perturbation action.