The following online bin packing problem is considered: Items with integer sizes are given and variable sized bins arrive online. A bin must be used if there is still an item remaining which fits in it when the bin arrives. The goal is to minimize th
e total size of all the bins used. Previously, a lower bound of 5/4 on the competitive ratio of this problem was achieved using jobs of size S and 2S-1. For these item sizes and maximum bin size 4S-3, we obtain asymptotically matching upper and lower bounds, which vary depending on the ratio of the number of small jobs to the number of large jobs.
In a multiparty message-passing model of communication, there are $k$ players. Each player has a private input, and they communicate by sending messages to one another over private channels. While this model has been used extensively in distributed c
omputing and in multiparty computation, lower bounds on communication complexity in this model and related models have been somewhat scarce. In recent work cite{phillips12,woodruff12,woodruff13}, strong lower bounds of the form $Omega(n cdot k)$ were obtained for several functions in the message-passing model; however, a lower bound on the classical Set Disjointness problem remained elusive. In this paper, we prove tight lower bounds of the form $Omega(n cdot k)$ for the Set Disjointness problem in the message passing model. Our bounds are obtained by developing information complexity tools in the message-passing model, and then proving an information complexity lower bound for Set Disjointness. As a corollary, we show a tight lower bound for the task allocation problem cite{DruckerKuhnOshman} via a reduction from Set Disjointness.
