O Problema Quadr�tico de Aloca��o, PQA, foi estudado utilizando uma
abordagem alg�brica atrav�s de uma relaxa��o linear, o Problema de
Aloca��o Linear, PAL. A utiliza��o dessa abordagem se deve ao fato
de existir na literatura o Teorema das Invers�es demonstrado por
Rangel em Ran00 que associa o custo de uma solu��o do PQA ao n�mero
de invers�es de sua correspondente linear no PAL. Embora seja polinomial
o reconhecimento de uma solu��o linear vi�vel para o PQA, caracterizar
no conjunto de todas as solu��es do PAL quais s�o as que satisfazem
o PQA � uma tarefa extremamente dif�cil. Neste trabalho constru�mos
uma matriz que armazena informa��es de solu��es lineares capazes
de gerar solu��es quadr�ticas. Combinando esse mapeamento com o Teorema
das Invers�es apresentamos um m�todo construtivo que gera solu��es
iniciais de boa qualidade. A grande vantagem dessa matriz � que seu
custo computacional e gasto de mem�ria s�o baixos. Propomos tamb�m
uma vers�o paralela deste algoritmo.
%0 Journal Article
%1 Resendo2006
%A Resendo, Leandro Colombi
%A Rangel, Maria Cristina
%D 2006
%J Pesquisa Operacional
%K imported
%N 1
%P 129-144
%T Um algoritmo construtivo baseado em uma abordagem alg�brica do problema
quadr�tico de aloca��o
%V 26
%X O Problema Quadr�tico de Aloca��o, PQA, foi estudado utilizando uma
abordagem alg�brica atrav�s de uma relaxa��o linear, o Problema de
Aloca��o Linear, PAL. A utiliza��o dessa abordagem se deve ao fato
de existir na literatura o Teorema das Invers�es demonstrado por
Rangel em Ran00 que associa o custo de uma solu��o do PQA ao n�mero
de invers�es de sua correspondente linear no PAL. Embora seja polinomial
o reconhecimento de uma solu��o linear vi�vel para o PQA, caracterizar
no conjunto de todas as solu��es do PAL quais s�o as que satisfazem
o PQA � uma tarefa extremamente dif�cil. Neste trabalho constru�mos
uma matriz que armazena informa��es de solu��es lineares capazes
de gerar solu��es quadr�ticas. Combinando esse mapeamento com o Teorema
das Invers�es apresentamos um m�todo construtivo que gera solu��es
iniciais de boa qualidade. A grande vantagem dessa matriz � que seu
custo computacional e gasto de mem�ria s�o baixos. Propomos tamb�m
uma vers�o paralela deste algoritmo.
@article{Resendo2006,
abstract = {O Problema Quadr�tico de Aloca��o, PQA, foi estudado utilizando uma
abordagem alg�brica atrav�s de uma relaxa��o linear, o Problema de
Aloca��o Linear, PAL. A utiliza��o dessa abordagem se deve ao fato
de existir na literatura o Teorema das Invers�es demonstrado por
Rangel em [Ran00] que associa o custo de uma solu��o do PQA ao n�mero
de invers�es de sua correspondente linear no PAL. Embora seja polinomial
o reconhecimento de uma solu��o linear vi�vel para o PQA, caracterizar
no conjunto de todas as solu��es do PAL quais s�o as que satisfazem
o PQA � uma tarefa extremamente dif�cil. Neste trabalho constru�mos
uma matriz que armazena informa��es de solu��es lineares capazes
de gerar solu��es quadr�ticas. Combinando esse mapeamento com o Teorema
das Invers�es apresentamos um m�todo construtivo que gera solu��es
iniciais de boa qualidade. A grande vantagem dessa matriz � que seu
custo computacional e gasto de mem�ria s�o baixos. Propomos tamb�m
uma vers�o paralela deste algoritmo.},
added-at = {2011-08-05T23:57:14.000+0200},
author = {Resendo, Leandro Colombi and Rangel, Maria Cristina},
biburl = {https://www.bibsonomy.org/bibtex/23505eece8af5a197aca13c533f062603/lgmarujo},
interhash = {080ab3aaccdf2af22662089e45249226},
intrahash = {3505eece8af5a197aca13c533f062603},
journal = {Pesquisa Operacional},
keywords = {imported},
number = 1,
owner = {Lino},
pages = {129-144},
timestamp = {2011-08-05T23:57:15.000+0200},
title = {Um algoritmo construtivo baseado em uma abordagem alg�brica do problema
quadr�tico de aloca��o},
volume = 26,
year = 2006
}