???item.export.label??? ???item.export.type.endnote??? ???item.export.type.bibtex???

Please use this identifier to cite or link to this item: https://tede.ufam.edu.br/handle/tede/8946
Full metadata record
DC FieldValueLanguage
dc.creatorSalvatierra, Marcos Marreiro-
dc.creator.Latteshttp://lattes.cnpq.br/7398454498084942eng
dc.contributor.advisor1Colonna, Juan Gabriel-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/9535853909210803eng
dc.contributor.referee1Feitosa, Eduardo Luzeiro-
dc.contributor.referee1Latteshttp://lattes.cnpq.br/5939944067207881eng
dc.contributor.referee2Nakamura, Fabíola Guerra-
dc.contributor.referee2Latteshttp://lattes.cnpq.br/9615041048900531eng
dc.contributor.referee3Vilca, Omar Latorre-
dc.contributor.referee3Latteshttp://lattes.cnpq.br/3293662600883484eng
dc.contributor.referee4Onety, Renata da Encarnação-
dc.contributor.referee4Latteshttp://lattes.cnpq.br/2342137418158973eng
dc.date.issued2022-05-26-
dc.identifier.citationSALVATIERRA, Marcos Marreiro. Aumento de desempenho na determinação de precificações ótimas livres de inveja. 2022. 63 f. Tese (Doutorado em Informática) - Universidade Federal do Amazonas, Manaus (AM), 2022.eng
dc.identifier.urihttps://tede.ufam.edu.br/handle/tede/8946-
dc.description.resumoMaximizar 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).eng
dc.description.abstractMaximizing sellers’ revenue while preserving consumers’ satisfaction presents some computational challenges. The envy-free pricing problem is itself a modeling alternative that is APX-hard in general, but some cases and/or variations have already been proven to be solvable exactly in polynomial time, and for others, there exists approximation algorithms with constant ratio in polynomial time. This work ad- dresses the cases of envy-free perfect matching, in which the number of consumers coincides with the number of items on sale and each consumer can buy only a single item, and unit demand with substitutability metric, in which several units of the same item are sold in different locations and consumers in these locations can buy only one unit of the item, and the costs of moving from one location to another to make the purchase form a metric space. For the first case, an exact algorithm was designed based on a dynamic programming strategy taking into account the consumers’ utilities to calculate the optimal pricing. For the second case, an algorithmic strategy was proposed that performs the search for the op- timal solutions through a reduction to the first case and the simplification of the calculations of the shortest paths for the determination of prices. Comparing the proposed methods with those in the literature, in the first case there was a performance increase of, on average, 49 % in the search for optimal prices, and in the second case there was a reduction in computational time complexity in the search for optimal solutions from O(n^4) to O(n^3).eng
dc.formatapplication/pdf*
dc.thumbnail.urlhttps://tede.ufam.edu.br/retrieve/57087/Tese_MarcosSalvatierra_PPGI.pdf.jpg*
dc.languageporeng
dc.publisherUniversidade Federal do Amazonaseng
dc.publisher.departmentInstituto de Computaçãoeng
dc.publisher.countryBrasileng
dc.publisher.initialsUFAMeng
dc.publisher.programPrograma de Pós-graduação em Informáticaeng
dc.rightsAcesso Aberto-
dc.subjectOtimização combinatóriapor
dc.subjectComputação - Matemáticapor
dc.subjectAlgorítmospor
dc.subjectProgramação dinâmicapor
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA: CIENCIA DA COMPUTACAOeng
dc.titleAumento de desempenho na determinação de precificações ótimas livres de invejaeng
dc.typeTeseeng
dc.contributor.advisor1orcidhttps://orcid.org/ 0000-0002-1740-2618eng
dc.creator.orcidhttps://orcid.org/ 0000-0002-6680-4023eng
dc.contributor.referee1orcidhttps://orcid.org/ 0000-0001-6401-3992eng
dc.contributor.referee2orcidhttps://orcid.org/ 0000-0001-8251-3202eng
dc.contributor.referee3orcidhttps://orcid.org/ 0000-0001-5609-6310eng
dc.contributor.referee4orcidhttps://orcid.org/ 0000-0002-2621-5961eng
dc.subject.userOtimização combinatóriapor
dc.subject.userComplexidade de algoritmospor
dc.subject.userAusência de invejapor
dc.subject.userProgramação dinâmicapor
Appears in Collections:Doutorado em Informática

Files in This Item:
File Description SizeFormat 
Tese_MarcosSalvatierra_PPGI.pdf1.64 MBAdobe PDFThumbnail

Download/Open Preview


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.