Compartilhamento de Custos de Empacotamento
Abstract
In the bin packing problem, one desires to pack a set of items in bins while respecting the bins’ capacities with the objective of minimizing the number of bins used. In this paper, we consider the problem of sharing the cost of packing between the participant agents.
References
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.
Published
2016-07-04
How to Cite
MIYAZAWA, Flávio K.; SCHOUERY, Rafael C. S..
Compartilhamento de Custos de Empacotamento. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
