Bill McCloskey and Ajeet Shankar

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-05-1378

, 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},
    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