Compartilhamento de Custos de Empacotamento
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.
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
Como Citar
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.
