Bill McCloskey and Ajeet Shankar
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-05-1378
April 2005
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1378.pdf
The problem of bin packing with arbitrary conflicts was introduced in 1995. In this paper, we consider a restricted problem, bin packing with clique-graph conflicts. We prove bounds for several approximation algorithms, and show that certain on- and off-line algorithms are equivalent. Finally, we present an optimal polynomial-time algorithm for the case of constant item sizes, and analyze its performance in the more general case of bounded item sizes.
BibTeX citation:
@techreport{McCloskey:CSD-05-1378, Author = {McCloskey, Bill and Shankar, Ajeet}, Title = {Approaches to Bin Packing with Clique-Graph Conflicts}, Institution = {EECS Department, University of California, Berkeley}, Year = {2005}, Month = {Apr}, URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5649.html}, Number = {UCB/CSD-05-1378}, Abstract = {The problem of bin packing with arbitrary conflicts was introduced in 1995. In this paper, we consider a restricted problem, bin packing with clique-graph conflicts. We prove bounds for several approximation algorithms, and show that certain on- and off-line algorithms are equivalent. Finally, we present an optimal polynomial-time algorithm for the case of constant item sizes, and analyze its performance in the more general case of bounded item sizes.} }
EndNote citation:
%0 Report %A McCloskey, Bill %A Shankar, Ajeet %T Approaches to Bin Packing with Clique-Graph Conflicts %I EECS Department, University of California, Berkeley %D 2005 %@ UCB/CSD-05-1378 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5649.html %F McCloskey:CSD-05-1378