[pt] Esta tese faz um estudo do problema do Conjunto Dominante, um problema NP-difícil de grande relevância em aplicações relacionadas ao projeto de rede sem fio, mineração de dados, teoria de códigos, dentre outras. O conjunto dominante mínimo em um grafo é um conjunto mínimo de vértices de modo que cada vértice do grafo pertence a este conjunto ou é adjacente a um vértice que pertence a ele. Três variantes do problema foram estudadas; primeiro, uma variante na qual considera pesos nos vértices, buscando um conjunto dominante com menor peso total; segundo, uma variante onde o subgrafo induzido pelo conjunto dominante está conectado; e, finalmente, a variante que engloba essas duas características. Para resolver esses três problemas, propõe-se um algoritmo híbrido baseado na meta-heurística busca tabu com componentes adicionais de programação matemática, resultando em um método por vezes chamado de mateurística, (matheuristic, em inglês). Diversas técnicas adicionais e vizinhanças largas foram propostas afim de alcançar regiões promissoras no espaço de busca. Análises experimentais demonstram a contribuição individual de todos esses componentes. Finalmente, o algoritmo é testado no problema do código de cobertura mínima, que pode ser visto como um caso especial do problema do conjunto dominante. Os códigos são estudados na métrica Hamming e na métrica Rosenbloom-Tsfasman. Neste último, diversos códigos menores foram encontrados. / [en] This thesis addresses the Dominating Set Problem, an NP- hard problem with great relevance in applications related to wireless network design, data mining, coding theory, among others. The minimum dominating set in a graph is a minimal set of vertices so that each vertex of the graph belongs to it or is adjacent to a vertex of this set. We study three variants of the problem: first, in the presence of weights on vertices, searching for a dominating set with smallest total weight; second, a variant where the subgraph induced by the dominating set needs to be connected, and,finally, the variant that encompasses these two characteristics. To solve these three problems, we propose a hybrid algorithm based on tabu search with additional mathematical-programming components, leading to a method sometimes called matheuristic. Several additional techniques and large neighborhoods are also employed to reach promising regions in the search space. Our experimental analyses show the good contribution of all these individual components. Finally, the algorithm is tested on the covering code problem, which can be viewed as a special case of the minimum dominating set problem. The codes are studied for the Hamming metric and the Rosenbloom-Tsfasman metric. For this last case, several shorter codes were found.

[pt] Esta dissertação descreve um sistema desenvolvido que permite a criação e execução de consultas a partir de palavras-chave sobre um banco de dados relacional. O sistema recebe palavras-chave quaisquer e tenta criar consultas que podem ser executadas em um Sistema de Gerenciamento de Banco de dados (SGBD). Para realizar esta geração automática de consultas o sistema utiliza os dados do catálogo da base de origem. O sistema permite assim efetuar consultas em um SGBD sem o conhecimento de uma linguagem de consultas, como SQL, e sem conhecimento do modelo do banco de dados. / [en] This dissertation describes a developed system that allows the creation and execution of searches from keywords in a relational database. The system receives any keywords and tries to create queries that can be executed in database. To perform this automatic generation of queries the system uses the information of the catalogue of the source database. The system allows to make queries in a database without the knowledge of a language queries, like SQL, and the model from the database.

[pt] A percepção de risco na compra online é tida como um fator importante que restringe a velocidade de expansão do comércio eletrônico. A reserva de um hotel, em si já percebida como arriscada pela dominância intangível do serviço, tem sido apontada como gerando ainda mais insegurança quando realizada pelo site próprio do hotel. Características de personalidade, como a busca de sensações, podem levar alguns consumidores a evitar um canal de marketing que traga percepção de maior risco. Este estudo procurou compreender o papel da busca de sensações na escolha, pelos consumidores, do canal para fazer a reserva de um hotel. Para isso, conduziu-se um survey em uma amostra de 3.600 pessoas que fizeram reserva em hotéis do Rio de Janeiro, entre setembro de 2009 e fevereiro de 2010. Metade da amostra fez a reserva através do site próprio do hotel, enquanto que a outra metade utilizou outros canais para efetivar a reserva (telefone, agências e operadores de turismo, ou serviços GDS, como Expedia). Os resultados identificam as dimensões do risco percebido relevantes nesta situação de compra, bem como as diferenças de escolha entre consumidores em função do nível (alto ou baixo) de seu nível de busca de sensações. / [en] The risk perception in buying online is seen as an important factor that restricts the speed of electronic commerce expansion. The hotel booking, as itself, is perceived as risky by the intangible dominance of service, it has been identified as generating further uncertainty when performed by the hotel s own website. Personality traits such as sensation seeking, may lead some consumers to avoid a marketing channel that brings increased perceived risk. This study sought to understand the role of sensation seeking in the choice, by the channel consumers, to book a hotel. For this, we conducted a survey in a sample of 3,600 people who have booked hotels in Rio de Janeiro, between September 2009 and February 2010. Half of the sample made a booking through the hotel s own site, while the other half used other channels to book it (telephone, agencies and tour operators, GDS or services such as Expedia). The results identify which perceived risk dimensions are relevant in this buying situation, as well as differences in the choice among consumers according to the level (high or low) level of sensation seeking.

[pt] As técnicas de tecnologia de grupos vêm sendo largamente usadas em muitos sistemas de manufatura. Vários algoritmos têm sido propostos para o projeto otimizado de eficientes células de manufatura. O problema de formação de células deve levar em conta vários objetivos: o número de operações gargalo, o número de máquinas e/ou peças gargalo, o fluxo intercelular, os custos de subcontratação, os custos de duplicação de máquinas e a carga da máquina e/ou célula mais sobrecarregada, entre outros. Nesta tese propõe-se uma metodologia multi- critério para resolver o problema de formação de células com múltiplos objetivos. Este enforque é baseado no uso da meta-heurística busca tabu para resolver uma seqüência de problemas com objetivos simples e restrições múltiplas, onde cada objetivo é minimizado individualmente, segundo sua ordem de importância. Resultados computacionais envolvendo uma aplicação para um problema bi-critério são apresentados para casos com até 100 máquinas e 1000 peças. / [en] Group tecnology techniques are now widely used in many manufacturing systems. Severla algorithms have been proposed for the optimal design of efficient manufacturing cells. The cell formation problem must take into account several objectives: the number of bottleneck operations, the number of bottleneck machines and/or parts, the intercell flow, the intracell workload balancing, the subcontracting cost, the machine duplication costs, and the workload of the busiest machine and/or cell, among athers. In this work, we propose a multi-criteria methodology for solving the cell formation problem with multiple objectives. This approach is based on the use of the tabu search meta-heuristic for solving a sequence of single-objective, multi-contrained problems, in wich each objective is taken and optimized in turn, following their order of relative importance. Computational results concerning an application to a bi-criteria problem are reported for instances with up 100 machines and 1000 parts.

[pt] O teste lógico de circuitos integrados VLSI é parte indispensável de sua fabricação e projeto. O enfoque pseudo-exaustivo para o teste lógico de circuitos integrados consiste em particionar o circuito original a ser testado em subcircuitos com um reduzido número de entradas, que são então testados em paralelo de forma exaustiva. Neste trabalho apresenta-se um algoritmo aproximado para o problema de particionamento de circuitos integrados combinacionais, baseado na metaheurística de busca tabu. O algoritmo proposto apresenta diversas características originais, tais como: o conceito de vizinhança reduzida, obtida por movimentos envolvendo apenas um subconjunto de nós de fronteira; movimentos complexos que induzem diversos movimentos resultantes, embora as variações na função de custo sejam facilmente calculáveis; uma função objetivo bi-critério combinando o número de circuitos e o número de cortes, que simultaneamente adiciona uma estratégia de diversificação à busca; e o uso de uma heurística de empacotamento como passo de pós-otimização. O desempenho do algoritmo proposto foi avaliado através de sua aplicação a um conjunto de circuitos computacionais ISCAS padronizados. Os resultados computacionais foram comparados com aqueles fornecidos pelos algoritmos conhecidos na literatura, obtendo-se melhorias significativas. As taxas de médias de redução foram da ordem de 30% para o número de subcircuitos na partição e de 40% para o número de cortes. / [en] The logical test of integrated VLSI circuits is one of the main phases of their design and fabrication. The pseudo-exhaustive approach for the logical test of integrated circuits consists in partitioning the original circuit to be tested into non-overlapping subcircuits with a small, bounded number of subcircuits, which are then exhaustively tested in parallel. In this work we present an approximate algorithm for the problem of partitioning integrated combinational circuits, based on the tabu search metaheuristic. The proposed algorithm presents several original features, such as: the use of a reduced neighborhood, obtained from moves involving only a subset of boundary nodes; complex moves which entail several resulting moves, although the variations in the cost function are very easily computable; a bi-criteria cost function combining the number of subcircuits and the number of cuts, which simultaneously adds a diversification strategy to the search; and the use of a bin-packing heuristic as a post-optimization step. The behavior of the proposed algorithm was evaluated through its application to a set of benchmark ISCAS combinational circuits. The computational results have been compared with those obtained by the other algorithms in the literature, with significant improvements. The average reduction rates have been of the order of 30% in the number of subcircuits in the partition, and of the order of 40% in the number of cuts.

[pt] A principal contribuição desta tese consiste no desenvolvimento de uma heurística híbrida, robusta e eficiente, para o problema de empacotamento unidimensional. A heurística proposta utiliza os seguintes componentes: limites inferiores e superiores do número de caixas; reduções; abordagem dual para a obtenção de soluções iniciais; heurísticas para redistribuição dos pesos; e busca tabu. O outro objetivo desta tese é a aplicação desta heurística para a solução do problema de escalonamento em processadores paralelos idênticos. São apresentados resultados computacionais obtidos sobre centenas de problemas testes da literatura. / [en] We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several components: lower and upper bounds; reductions, construction of initial solutions by reference to the dual problem;heuristics for load redistribution based on dominance, differencing, and unbalancing; and tabu search. We also investigate the application of this hybrid heuristic to the problem of task scheduling on identical parallel processors. Computational results on hundreds of benchmark test problem are presented.

[pt] Neste trabalho, apresentamos algoritmos aproximativos para dois problemas de otimização em árvores. Na primeira parte, consideramos o Problema de Atribuição de k-Hotlinks. Seja G= (V,E) um grafo direcionado acíclico representando um web site, onde nós correspondem a páginas e arcos correspondem a hyperlinks. Nesse contexto, hotlink são definidos como atalhos (novos arcos) adicionados às páginas de G de modo a reduzir o tempo gasto pelos usuários para alcançarem as informações desejadas. Neste trabalho consideramos o problema onde G é uma árvore enraizada e o objetivo é minimizar o tempo médio gasto pelos usuários atribuindo no máximo k hotlinks a cada nó. Para a versão mais estudada desse problema onde no máximo um hotlink pode ser atribuído a cada nó, provamos a existência de um FPTAS. Isso representa uma significante melhora em relação ao algoritmo com aproximação constante obtido recentemente em [Jacobs, WADS 2007]. Além disso, desenvolvemos o primeiro algoritmo com aproximação constante para a versão mais geral onde k hotlinks podem ser atribuídos a cada nó. Na segunda parte deste trabalho, consideramos o problema de computar estratégias eficientes para realizar buscas em árvores. Como uma generalização da tradicional busca binária em listas ordenadas, suponha que se deseja encontrar um nó específico (porém desconhecido) de uma árvore realizando consultas em seus arcos, onde cada consulta indica a extremidade do arco mais próxima ao nó desejado. Dada a probabilidade de cada nó ser aquele procurado, o objetivo é computar uma estratégia de busca que minimize o número esperado de consultas. Aplicações práticas desse problema incluem sincronização de file systems e testes de software. Apresentamos um algoritmo linear que obtém a primeira aproximação constante para esse problema. Isso representa uma melhora significativa em relação à O(log n)-aproximação anterior. / [en] Here we present a study on two optimization problems in trees: the k- Hotlink Assignment Problem and the problem of Binary Searching in Trees. As a result, we obtain improved approximation algorithms for both problem. The k-Hotlink Assignment Problem can be defined as follows. Let G = (V,E) be a directed acyclic graph representing a web site, where nodes correspond to pages and arcs to hyperlinks. In this context, hotlinks are defined as shortcuts (new arcs) added to web pages of G in order to reduce the time spent by users to reach their desired information. Here we consider the problem where G is a rooted directed tree and the goal is minimizing the expected time spent by users by assigning at most k hotlinks to each node. For the most studied version of this problem where at most one hotlink can be assigned from each node, we prove the existence of an FPTAS, improving upon the constant factor algorithm recently obtained in [Jacobs, WADS 2007]. In addition, we develop the first constant factor approximation algorithm for the most general version where k hotlinks can be assigned from each node. In the second part of this work, we consider the problem of computing efficient strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of a tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a linear time algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(log n)-approximation.

[pt] Em cenários de tomada de decisão, quando um agente, humano ou máquina, necessita de mais conhecimento para decidir devido a uma lacuna de conhecimento, surge uma necessidade de informação. Os usuários podem conscientemente tomar a iniciativa de adquirir conhecimento para preencher essa lacuna através de tarefas de buscas por informação. As consultas do usuário podem ser incompletas, imprecisas e ambíguas. Isso ocorre porque parte da informação necessária está implícita ou porque o usuário não compreende totalmente o domínio ou a tarefa que motiva a busca. Esta condição está prevista nas abordagens de busca exploratória. Embora os Grafos de Conhecimento (KG) sejam reconhecidos como fontes de informação com grande potencial para integração de dados e busca exploratória, eles são incompletos por natureza. Além disso, KGs Crowdsourced, ou KGs construídos pela integração de diversas fontes de informação de qualidade variável, precisam de uma Camada de Confiança para serem eficazes no suporte a processos de tomada de decisão. A avaliação da veracidade do conhecimento depende dos contextos das alegações e das tarefas a serem realizadas ou pretendidas (propósito). Esta pesquisa tem como objetivo preparar e consultar KGs para apoiar a exploração ciente de contexto em cenários de tomada de decisão. As contribuições incluem uma arquitetura para sistemas de apoio à decisão, composta por uma Camada de Decisão, uma Camada de Confiança e uma Camada de Conhecimento que opera sob a hipótese de Mundo Aberto Dual. A Camada de Conhecimento é composta por um Grafo de Conhecimento enriquecido de Contexto (CoaKG) e uma Máquina de Consulta baseada em CoaKG. CoaKG estende um KG padrão com mapeamentos de contexto para identificar o contexto explicitamente representado e regras para inferir o contexto implícito. A máquina de Consulta baseada em CoaKG foi projetada como uma abordagem de resposta a consultas que recupera todas as respostas contextualizadas (possíveis). A Wikidata é objeto de uma Prova de Conceito para avaliar a eficácia da Camada de Conhecimento. / [en] In decision-making scenarios, an information need arises when an agent, human, or machine needs more knowledge to decide due to a knowledge gap. Users can consciously take the initiative to acquire knowledge to fill this gap through information search tasks. User queries can be incomplete, inaccurate, and ambiguous. It occurs because part of the information needed is implicit or because the user does not fully understand the domain or the task that motivates the search. This condition is foreseen within the exploratory search approaches. Although Knowledge Graphs (KG) are recognized as information sources with great potential for data integration and exploratory search, they are incomplete by nature. Besides, Crowdsourced KGs, or KGs constructed by integrating several different information sources of varying quality, need a Trust Layer to be effective. The evaluation of knowledge truthfulness depends upon the contexts of claims and tasks being carried out or intended (purpose). This research aims to prepare and query KGs to support context-aware exploration in decision-making scenarios. The contributions include a framework for Context Augmented Knowledge Graphs-based Decision Support Systems composed of a Decision Layer, a Trust Layer, and a Knowledge Layer that operates under a Dual Open World Assumption. The Knowledge Layer comprises a Context Augmented KG (CoaKG) and a CoaKG Query Engine. CoaKG contains contextual mappings to identify explicit context and rules to infer implicit context. CoaKG Query Engine is designed as a query-answering approach that retrieves all contextualized (possible answers) from the CoaKG. Wikidata is the object of a Proof of Concept to evaluate the effectiveness of the Knowledge Layer.

[pt] Este trabalho desenvolve um modelo de busca por emprego com trabalhadores e firmas heterogêneos, salário mínimo e benefícios trabalhistas. Em equilíbrio, as firmas informais são menores, menos produtivas e empregam menos trabalhadores qualificados devido a um efeito de seleção. Trabalhadores informais geralmente recebem salários maiores para compensar a falta de benefícios trabalhistas, mas uma simples comparação de salários médios entre setores mostra um prêmio salarial para a formalidade devido a um efeito de composição. Além disto, o salário mínimo pode quebrar a relação de diferenciais compensatórios, de forma que haja um prêmio de formalidade para trabalhadores pouco qualificados mesmo após controlar para produtividade individual. O modelo é calibrado usando dados do Brasil e utilizado para explicar a evolução do mercado de trabalho neste país de 2003 até 2012. Os resultados sugerem que o aumento da escolaridade média foi o fator mais importante por trás da reversão da tendência de informalidade no Brasil, que ainda é um fato não plenamente explicado na literatura acadêmica. Também mostra-se que, no modelo calibrado, impostos progressivos sobre folha salarial poderiam levar a uma redução tanto do desemprego quanto da informalidade sem comprometer as receitas do governo. / [en] This work develops a search and matching model of informality with heterogeneous workers and firms, minimum wages, and mandated benefits. In equilibrium, informal firms are smaller, less productive and employ fewer skilled workers as a result of self-selection. Informal workers are generally compensated for the lack of mandated benefits by receiving higher wages, but a simple comparison of average earnings between sectors shows a formality wage premium because of compositional effects. In addition, a binding minimum wage can break the equalizing differentials relation, so that there might be a formality wage premium among low wage workers even after controlling for individual productivity. The model is calibrated using Brazilian data and used to explain the evolution of labor market outcomes in that country from 2003 to 2012. The results suggest that rising schooling was the most important factor behind the reversal of the informality trend in Brazil, which remains a puzzle in the current literature. It is also shown that, for the calibrated model, a progressive payroll tax would lead to a decrease in both unemployment and informality without compromising tax revenues.

[pt] Pesquisar preços pode ser custoso para os consumidores. Este artigo investiga os efeitos de busca na formação de conluio por parte das firmas. Para identificar tais efeitos, constrói-se um jogo repetido no qual os consumidores pesquisam preços seqüencialmente e as firmas competem por preços no jogo estático. Claramente, identificam-se dois efeitos distintos, por um lado, mais busca, i.e. mais consumidores pesquisando preços ou um menor custo de busca, facilita a formação de conluio, pois as firmas sustentam punições críveis mais severas. Por outro lado, mais busca dificulta a formação de conluio à medida que os desvios do conluio se tornam mais lucrativos. / [en] This paper investigates, through a theoretical approach, search effects on collusion. In order to identify these effects, we consider an infinitely repeated game; in the stage game, consumers search for prices sequentially and firms set price simultaneously. We clearly identify two different search effects on collusion; on the one hand, it facilitates collusion as the punishment payoff is lower. On the other hand, it makes collusion more difficult, since deviations are more profitable.