Approaches to Bin Packing with Clique-Graph Conflicts

Bill McCloskey and Ajeet Shankar

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-05-1378

2005

This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/Archive/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