Nessa tese consideramos problemas de alocação e precificação de itens, onde temos um conjunto de itens e um conjunto de compradores interessados em tais itens. Nosso objetivo é escolher uma alocação de itens a compradores juntamente com uma precificação para tais itens para maximizar o lucro obtido, considerando o valor máximo que um comprador está disposto a pagar por um determinado item. Em particular, focamos em três problemas: o Problema da Compra Máxima, o Problema da Precificação Livre de Inveja e o Leilão de Anúncios de Segundo Preço. O Problema da Compra Máxima e o Problema da Precificação Livre de Inveja modelam o problema que empresas que vendem produtos ou serviços enfrentam na realidade, onde é necessário escolher corretamente os preços dos produtos ou serviços disponíveis para os clientes para obter um lucro interessante. Já o Leilão de Anúncios de Segundo Preço modela o problema enfrentado por empresas donas de ferramentas de busca que desejam vender espaço para anunciantes nos resultados das buscas dos usuários. Ambas as questões, tanto a precificação de produtos e serviços quanto a alocação de anunciantes em resultados de buscas, são de grande relevância econômica e, portanto, são interessantes de serem atacadas dos pontos de vista teórico e prático. Nosso foco nesse trabalho é considerar algoritmos de aproximação e algoritmos de programação inteira mista para os problemas mencionados, apresentando novos resultados superiores àqueles conhecidos previamente na literatura, bem como determinar a complexidade computacional destes problemas ou de alguns de seus casos particulares de interesse. / In this thesis we consider allocation and pricing problems, where we have a set of items and a set of consumers interested in such items. Our objective is to choose an allocation of items to consumers, considering the maximum value a consumer is willing to pay in a specific item. In particular, we focus in three problems: the Max-Buying Problem, the Envy-Free Pricing Problem and the Second-Price Ad Auction. The Max-Buying Problem and the Envy-Free Pricing Problem model a problem faced in reality by companies that sell products or services, where it is necessary to correctly choose the price of the products or services available to clients in order to obtain an interesting profit. The Second-Price Ad Auction models the problem faced by companies that own search engines and desire to sell space for advertisers in the search results of the users. Both questions, the pricing of items and services and the allocation of advertisers in search results are of great economical relevance and, for this, are interesting to be attacked from a theoretical and a practical perspective. Our focus in this work is to consider approximation algorithms and mixed integer programming algorithms for the aforementioned problems, presenting new results superior than the previously known in the literature, as well as to determine the computational complexity of such problems or some of their interesting particular cases.

Nessa tese consideramos problemas de alocação e precificação de itens, onde temos um conjunto de itens e um conjunto de compradores interessados em tais itens. Nosso objetivo é escolher uma alocação de itens a compradores juntamente com uma precificação para tais itens para maximizar o lucro obtido, considerando o valor máximo que um comprador está disposto a pagar por um determinado item. Em particular, focamos em três problemas: o Problema da Compra Máxima, o Problema da Precificação Livre de Inveja e o Leilão de Anúncios de Segundo Preço. O Problema da Compra Máxima e o Problema da Precificação Livre de Inveja modelam o problema que empresas que vendem produtos ou serviços enfrentam na realidade, onde é necessário escolher corretamente os preços dos produtos ou serviços disponíveis para os clientes para obter um lucro interessante. Já o Leilão de Anúncios de Segundo Preço modela o problema enfrentado por empresas donas de ferramentas de busca que desejam vender espaço para anunciantes nos resultados das buscas dos usuários. Ambas as questões, tanto a precificação de produtos e serviços quanto a alocação de anunciantes em resultados de buscas, são de grande relevância econômica e, portanto, são interessantes de serem atacadas dos pontos de vista teórico e prático. Nosso foco nesse trabalho é considerar algoritmos de aproximação e algoritmos de programação inteira mista para os problemas mencionados, apresentando novos resultados superiores àqueles conhecidos previamente na literatura, bem como determinar a complexidade computacional destes problemas ou de alguns de seus casos particulares de interesse. / In this thesis we consider allocation and pricing problems, where we have a set of items and a set of consumers interested in such items. Our objective is to choose an allocation of items to consumers, considering the maximum value a consumer is willing to pay in a specific item. In particular, we focus in three problems: the Max-Buying Problem, the Envy-Free Pricing Problem and the Second-Price Ad Auction. The Max-Buying Problem and the Envy-Free Pricing Problem model a problem faced in reality by companies that sell products or services, where it is necessary to correctly choose the price of the products or services available to clients in order to obtain an interesting profit. The Second-Price Ad Auction models the problem faced by companies that own search engines and desire to sell space for advertisers in the search results of the users. Both questions, the pricing of items and services and the allocation of advertisers in search results are of great economical relevance and, for this, are interesting to be attacked from a theoretical and a practical perspective. Our focus in this work is to consider approximation algorithms and mixed integer programming algorithms for the aforementioned problems, presenting new results superior than the previously known in the literature, as well as to determine the computational complexity of such problems or some of their interesting particular cases.