1
$\begingroup$

We have $k$ bins of capacity $c_i$ each. These bins appear in an online fashion, say on day $i$, bin $i$ appears. There are $l$ balls. Ball $j$ has weight $w_{ij}$ with bin $i$.

Each ball knows that there will be $k$ bins. On day $i$, bin $i$ appears and ball $j$ gets to know the bin and its capacity $c_i$. Also, ball $j$ gets to know $w_{i1},w_{i2},\ldots,w_{il}$; the weights of all balls with bin $i$ (including her weight of course). Ball $j$ must decide either to put herself into bin $i$ or not, once and forever (i.e., once decided, the game is over for ball $j$).

Each ball wants to be satisfied, that is, puts herself into a bin that has enough capacity. Ball $j$ does not know if some other balls have chosen bin $i$ or not. Also, Ball $j$ knows only the current information, does not know the weights of the balls with bins that will appear in the future.

Is there a way to find an online algorithm that maximizes the number of satisfied balls? I think this is somehow related to secretary problem but I am not sure how to prove this claim.

$\endgroup$
  • $\begingroup$ "Each ball wants to be satisfied, that is, puts herself into a bin that has enough capacity. The unknown here is that ball 𝑗 does not know if some other balls have chosen bin 𝑖 or not." It is unclear what this means. If all balls agree on some protocol in advance, you could use any online algorithm you want -- each ball would just simulate the algorithm to know what it (and the other balls) should do. $\endgroup$ – Neal Young Nov 5 '19 at 23:54
  • $\begingroup$ If we assume that the balls cannot communicate with each other, does that make the problem clearer? $\endgroup$ – zdm Nov 6 '19 at 0:25
  • $\begingroup$ @NealYoung I think it is better to see a special case of the problem. Say, when bin $i$ appears, it can contain at most one ball (we can choose the weights to satisfy this condition). This special case, I think, is the classical online matching problem. $\endgroup$ – zdm Nov 6 '19 at 0:45
  • $\begingroup$ Suppose for now that there is a single algorithm deciding which balls go in each bin. Maybe using online-matching-like techniques you can prove that a greedy algorithm -- pack the most balls that will fit at each time step -- achieves a decent competitive ratio like 0.5. (Ignoring that it's NP-hard to compute.) $\endgroup$ – usul Nov 6 '19 at 0:56
  • $\begingroup$ Say $k=2$ and $l=2$. Say bin 1 has capacity $c_1=2$ and bin 2 has capacity $c_2=1$. Say when bin 1 appears, we have $(w_{11},w_{12})=(1,2)$ and an online algorithm puts ball 1 into bin 1. Now, when bin 2 appears, say we have $(w_{21},w_{22})=(1,2)$. The online algorithm cannot put any ball in bin 2 (it has already put ball 1 into bin 1 and ball 2 cannot be put into bin 2). However, ball 1 can be put into bin 2 and ball 2 can be put into bin 1. I meant to say that future weights and future capacities are not known. $\endgroup$ – zdm Nov 6 '19 at 2:47
2
$\begingroup$

Per @usul's suggestion, consider the following online greedy algorithm $A$. When bin $i$ is revealed, $A$ considers all subsets $S$ of not-yet assigned balls such that all balls in $S$ can fit together in bin $i$. It chooses any largest such set, say $A_i$, then assigns all balls in $A_i$ to bin $i$.

The post asks for an algorithm that each ball can use independently. To achieve this, just have each ball independently simulate $A$, and decide to join a given bin only if $A$ says it should.

Lemma 1. This greedy algorithm is 0.5-competitive.

Proof. Let $A^* = \bigcup_{i} A_i$ denote the set of balls assigned by $A$. Let $O_i$ denote the set of balls assigned by OPT to bin $i$. Let $O^* = \bigcup_i O_i$ be the set of all balls assigned by OPT.

The set $O_i \setminus A^*$ is one possible set that $A$ could have assigned to bin $i$. Set $A_i$ is at least as large as this set, so $|O_i \setminus A^*| \le |A_i|$. Summing over $i$ gives $|O^*\setminus A^*| \le |A^*|$. That is, the number of balls assigned by OPT but not $A$ is at most the number assigned by $A$. This implies the desired bound. Specifically, as $O^* \subseteq A^* \cup (O^*\setminus A^*)$, it follows that $$|O^*| \le |A^*| + |O^*\setminus A^*| \le |A^*| + |A^*| = 2|A^*|.~~~~~~~~\Box$$

If you want a polynomial-time algorithm, you can modify $A$ to choose each set $A_i$ so that it is within a factor of $1-\epsilon$ of the largest possible. (E.g., to achieve $\epsilon=1/2$ just order the not-yet-assigned balls by increasing $w_{ij}$, and take as many as will fit in bin $i$. Or use a PTAS at each step to achieve any fixed $\epsilon>0$.) Then $|O_i \setminus A^*| \le |A_i|/(1-\epsilon)$ and the algorithm will be $(1-\epsilon)/(2-\epsilon)$-competitive. (E.g. $1/3$-competitive for $\epsilon=1/2$.)

And just for the record, per OP's comment:

Lemma 2. No deterministic online algorithm has competitive ratio more than 0.5.

Proof. Consider the instance with two balls and two capacity-1 bins, where each ball has weight 1 for bin 1, but only the ball put by the online algorithm in bin 1 can fit in bin 2.$~~~\Box$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The reason for 1/2 in this case is known to follow from local-greedy for submodular function maximization subject to a partition matroid constraint. It may shed light on more general problems. I will post a pointer when I get a chance. $\endgroup$ – Chandra Chekuri Nov 6 '19 at 17:39
  • 1
    $\begingroup$ Related to my other comment, here are talk slides from 2006 where I explain the connection between multiple knapsack, generalized assignment and local-greedy for submodular function maximization. Some may find this connection helpful. chekuri.cs.illinois.edu/talks/crm_submodular.pdf $\endgroup$ – Chandra Chekuri Nov 6 '19 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.