Name
Abstract | ||
|---|---|---|
We introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly environment. The bin coloring problem is to pack unit size colored items into bins, such that the maximum number of different colors per bin is minimized. Each bin has size B@?N. The packing process is subject to the constraint that at any moment in time at most q@?N bins are partially filled. Moreover, bins may only be closed if they are filled completely. We settle the computational complexity of the problem and design an approximation algorithm for a natural version which gives a solution whose value is at most one greater than the optimal one. We also investigate the existence of competitive online algorithms, which must pack each item without knowledge of any future items. We prove an upper bound of 3q-1 and a lower bound of 2q for the competitive ratio of a natural greedy-type algorithm, and show that surprisingly a trivial algorithm which uses only one open bin has a strictly better competitive ratio of 2q-1. Moreover, we show that any deterministic algorithm has a competitive ratio @W(q) and that randomization does not improve this lower bound even when the adversary is oblivious. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.tcs.2008.05.022 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
competitive ratio,deterministic algorithm,trivial algorithm,approximation algorithm,new problem,competitive analysis,competitive online algorithm,np-hardness,N bin,open bin,NP -hardness,natural greedy-type algorithm,natural version,Competitive analysis | Journal | 407 |
Issue | ISSN | Citations |
1-3 | Theoretical Computer Science | 3 |
PageRank | References | Authors |
0.38 | 2 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sven O. Krumke | 1 | 308 | 36.62 |
| Willem E. de Paepe | 2 | 117 | 9.74 |
| Jörg Rambau | 3 | 181 | 24.38 |
| Leen Stougie | 4 | 892 | 107.93 |