O Problema da Atribuição Dupla de Custo Mínimo

• Vinícius F. dos Santos UFMG
• Sebastián Urrutia UFMG

DOI: https://doi.org/10.5753/etc.2016.9847

Resumo

Neste trabalho introduzimos o Problema da Atribução Dupla de Custo Mínimo, no qual a entrada é um par X, Y de vetores n-dimensionais de custos e é necessário encontrar um par (i, j) para o qual uma função f(i, j) dada é verdadeira, minimizando xi + yj. Apresentamos algoritmos polinomiais para a solução do problema e discutimos os melhores cenários para os algoritmos apresentados.

 

Referências

Cosnard, M., Duprat, J., and Ferreira, A. G. (1990). The complexity of searching in X+Y and other multisets. Information Processing Letters, 34(2):103–109.

Frederickson, G. and Johnson, D. (1982). The complexity of selection and ranking in X +Y and matrices with sorted columns. J. of Comput. and Syst. Sci., 24(2):197–208.

Fredman, M. L. (1976). How good is the information theory bound in sorting? Theoretical Computer Science, 1(4):355–361.

Lambert, J.-L. (1992). Sorting the sums (xi + yj) in O(n2) comparisons. Theoretical Computer Science, 103(1):137–141.

Meisel, F. and Bierwirth, C. (2009). Heuristics for the integration of crane productivity in the berth allocation problem. Transportation Research Part E: Logistics and Transportation Review, 45(1):196 – 209.

Mirzaian, A. and Arjomandi, E. (1985). Selection in X + Y and matrices with sorted rows and columns. Information processing letters, 20(1):13–17.