Research On Some Problems Of Bin Coloring

Bin Packing is one of the classical combinatorial optimization problems. It has beenextensively studied in the past and shown its importance in practical applications dur-ing the daily life. In practice, there are many complicated variants with more or changedconstraints that makes them harder than the classical Bin Packing problem.In this paper, we present an interesting variant of the packing problem and its sub-problem-Minimize the number of bins with arbitrary coloring constraint (2 coloringconstraint respectively). Our bin coloring problems are motivated from several appli-cations in networking and transportation in supply chain. For Example, we need toencapsulate many data into a packet in network when we want to transmit them to oth-ers. In such applications, each type of items represents all the packets from a single user(or a single task) and each bin represents a burst or a channel. By minimizing the num-ber of bins used in our certain Bin Coloring Problem, we can maximize the efficiency ofthe total network.In this paper, we consider the dual problem of minimizing the different number ofcolors and its subproblem. Our object is minimizing the number of bins used under thecolor constraints. Discussing the problem that the color constraint is only 2, we showthat this case is NP-Complete and give a linear algorithm with approximation 4/3 ratio.At last, we discuss the general case that the color constraint is arbitrary. A heuristicalgorithm is presented.