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

<p>The post asks for an algorithm that each ball can use independently.  To achieve this, just have each ball independently simulate <span class="math-container">$A$</span>, and decide to join a given bin only if <span class="math-container">$A$</span> says it should.</p>

<p><strong>Lemma 1.</strong> <em>This greedy algorithm is 0.5-competitive.</em></p>

<p><em>Proof.</em> Let <span class="math-container">$A^* = \bigcup_{i} A_i$</span> denote the set of balls assigned by <span class="math-container">$A$</span>.  Let <span class="math-container">$O_i$</span> denote the set of balls assigned by OPT to bin <span class="math-container">$i$</span>.  Let <span class="math-container">$O^* = \bigcup_i O_i$</span> be the set of all balls assigned by OPT.</p>

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

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

<p>And just for the record, per OP's comment:</p>

<p><strong>Lemma 2.</strong> <em>No deterministic online algorithm has competitive ratio more than 0.5</em>.</p>

<p><em>Proof.</em> 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.<span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2019-11-06T17:39:30.167Z
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.
Chandra Chekuri
CC BY-SA 4.0
2019-11-06T20:05:09.950Z
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. http://chekuri.cs.illinois.edu/talks/crm_submodular.pdf
Chandra Chekuri
CC BY-SA 4.0
2019-11-06T15:13:14.073Z
2019-11-06T15:13:14.073Z
Neal Young
<p>We have <span class="math-container">$k$</span> bins of capacity <span class="math-container">$c_i$</span> each. These bins appear in an online fashion, say on day <span class="math-container">$i$</span>, bin <span class="math-container">$i$</span> appears. There are <span class="math-container">$l$</span> balls. Ball <span class="math-container">$j$</span> has weight <span class="math-container">$w_{ij}$</span> with bin <span class="math-container">$i$</span>. </p>

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

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

<p>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.</p>

CC BY-SA 4.0
2019-11-05T23:54:44.743Z
*"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.
Neal Young
CC BY-SA 4.0
2019-11-06T00:25:29.723Z
If we assume that the balls cannot communicate with each other, does that make the problem clearer?
zdm
CC BY-SA 4.0
2019-11-06T00:45:25.897Z
@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.
zdm
CC BY-SA 4.0
2019-11-06T00:56:38.473Z
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.)
usul
CC BY-SA 4.0
2019-11-06T02:47:16.270Z
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.
zdm
<online-algorithms>
How to design an online algorithm for secretary problem with multiple players?
zdm
# How to design an online algorithm for secretary problem with multiple players?

(Asked by: username_0 on 2019-10-31)

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.

**Tags:** online-algorithms
> **Comments:**
> **username_1**: *"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.  
> **username_0**: If we assume that the balls cannot communicate with each other, does that make the problem clearer?  
> **username_0**: @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.  
> **username_2**: 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.)  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2019-11-06. Score: 2 | Accepted answer

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$

> **Comments:**
> **username_3**: 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.  
> **username_3**: 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. http://chekuri.cs.illinois.edu/talks/crm_submodular.pdf  

---

