@PHDTHESIS{ 2022:1370527898, title = {Aumento de desempenho na determina??o de precifica??es ?timas livres de inveja}, year = {2022}, url = "https://tede.ufam.edu.br/handle/tede/8946", abstract = "Maximizar a receita de vendedores preservando a satisfa??o dos consumidores apresenta alguns desafios computacionais. O problema da precifica??o livre de inveja surgiu como uma alternativa de modelagem que ? APX-dif?cil em geral, mas alguns casos e/ou varia??es j? foram provados ser resolv?veis de maneira exata em tempo polinomial. Este trabalho aborda os casos de emparelhamento perfeito livre de inveja, no qual o n?mero de consumidores coincide com o n?mero de itens ? venda e cada consumidor pode comprar apenas um ?nico item, e o de demanda unit?ria com substituibilidade m?trica, no qual v?rias unidades de um mesmo item s?o vendidas em localidades diferentes e os consumidores destas localidades podem comprar apenas uma unidade do item, sendo que os custos de deslocamento de uma localidade ? outra para a realiza??o da compra formam um espa?o m?trico. Para o primeiro caso, foi projetado um algoritmo exato baseado em uma estrat?gia de programa??o din?mica levando em considera??o as utilidades dos consumido- res para calcular as precifica??es ?timas. Para o segundo caso, foi proposta uma estrat?gia algor?tmica que realiza a busca das solu??es ?timas atrav?s de uma redu??o para o primeiro caso e da simplifica??o dos c?lculos dos caminhos m?nimos para a determina??o dos pre?os. Comparando-se os m?todos propostos com os existentes na literatura, no primeiro caso houve um aumento de desempenho de, em m?dia, 49% na busca de pre?os ?timos, e no segundo caso houve uma redu??o da complexidade computacional de tempo na busca das solu??es ?timas de O(n^4) para O(n^3).", publisher = {Universidade Federal do Amazonas}, scholl = {Programa de P?s-gradua??o em Inform?tica}, note = {Instituto de Computa??o} }