Compartilhamento de Custos de Empacotamento

  • Flávio K. Miyazawa UNICAMP
  • Rafael C. S. Schouery UNICAMP

Resumo


No Problema do Empacotamento, queremos empacotar um conjunto de itens em recipientes de forma a respeitar a capacidade dos recipientes e a minimizar o número de recipientes usados. Neste artigo, abordamos o problema de compartilhar o custo do empacotamento entre os agentes participantes.


 

Referências

Faigle, U. and Kern, W. (1993). On some approximately balanced combinatorial cooperative games. Zeitschrift f¨ur Operations Research, 38(2):141–152.

Gilmore, P. C. and Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6):849–859.

Karmarkar, N. and Karp, R. M. (1982). An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science, pages 312–320.

Lee, C. C. and Lee, D. T. (1985). A simple on-line bin-packing algorithm. Journal of the ACM, 32(3):562–572.

Moulin, H. (1999). Incremental cost sharing: Characterization by coalition strategy-proofness. Social Choice and Welfare, 16(2):279–320.

Qiu, X. and Kern, W. (2016). Approximate core allocations and integrality gap for the bin packing game. Theoretical Computer Science, 627:26 – 35.

Scheithauer, G. and Terno, J. (1997). Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem. Operations Research Letters, 20(2):93–100.
Publicado
04/07/2016
MIYAZAWA, Flávio K.; SCHOUERY, Rafael C. S.. Compartilhamento de Custos de Empacotamento. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2016 . p. 848-851. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2016.9841.