DIMACS
DIMACS REU 2020

General Information

Student: Joseph Durie
School: Rutgers University-New Brunswick
E-mail: jrd266 at scarletmail dot rutgers dot edu
Project: Worst-Case Ball Recycling Problem

Project Description

The ball-recycling problem, a variant of the common balls-and-bins problem, has m balls thrown into n bins, typically according to some probability distribution p. Repeatedly, one bin is selected, and its balls are removed and rethrown according to p. We want to maximize the expected number of balls rethrown at every step. I will be investigating worst-case performance for online ball-recycling algorithms, that is, ball-recycling when the balls are rethrown not according to p, but according to some adversary. The goal is to find an online algorithm that gets as close as possible to the offline optimum algorithm over all possible adversaries.

Weekly Log

Week 1 (5/26-5/31): Dr. Farach-Colton sent me his paper "Optimal Ball Recycling" (see References) as an introduction to the balls-and-bins recycling problem. I read through it to get a feel for the problem, as well as to gain intuition about the recycling strategies Fullest Bin, Random Ball, and Golden Gate, which will likely be useful in my project. I met with Dr. Farach-Colton to discuss broad goals for the project, dividing it up into three distinct phases - finding an optimal offline algorithm, giving adversarial bounds for the existing strategies mentioned above, and finally using both of the above to design an online algorithm that gets as close to the offline optimum as possible. I combined all of this information into my introductory presentation (see Presentations).
Week 2 (6/1-6/7): Gave introductory presentation, began working on finding polynomial-time offline optimum algorithm, initially only considering the 2-bin case for simplicity. Came up with several natural algorithms, including always recycling the bin that sends the most balls to the other bin (recycling rate minus the balls that go back to itself), and the bin that makes the distribution of balls in the two bins as uneven as possible, however I found instances where these strategies only gave results that were 3/4 and 5/6 of the optimal answer, respectively. I tried a few other greedy-type algorithms like this, but got similar results. I then tried to approach the problem from the other direction, by trying to improve the brute-force dynamic programming to polynomial time. The version I discussed in the intro presentation has complexity O(Nn (N choose m)), but using a stars-and-bars bitmask, this can be improved to O(Nn (n + m - 1 choose m)). Although this is still exponential, if either m or n are small and constant, it is polynomial time. Specifically, for an arbitrarily long stream (size N), for fixed n and m, this is linear time. However, I have not yet found a polynomial-time algorithm for when N, m, and n are all variable, so I will keep looking for one. I also began work on the second stage of the project, namely analyzing worst-case complexity of the existing recycling algorithms. It was relatively easy to show that Fullest Bin is not within a constant factor of optimal, using a variation on the skyscraper distribution mentioned in "Optimal Ball Recycling". I was also able to show the same for Golden Gate, although the specific counterexample is significantly more involved than the counterexample for Fullest Bin.
Week 3 (6/8-6/14): Worked more on finding worst-case counterexamples for existing recycling strategies. Found one for Golden Gate on Balls showing that it isn't within a constant of optimal. This means that none of these three deterministic algorithms (Fullest Bin, Golden Gate, and Golden Gate on Balls) are within a constant of optimal in the worst case. I also began working on proving something similar for Random Ball, and was able to show that it is at most 1/2 of optimal in the worst case, but getting past that proved difficult. I now suspect that Random Ball might actually be within a constant of optimal, because, of the methods mentioned in "Optimal Ball Recycling", it was the only one proven to always have expected value within a constant of optimal. Proving that this is constant-optimal will be significantly different than the things I've done so far, and I will see if there is anything in the proof in "Optimal Ball Recycling" that still applies in the worst case. I spent a large portion of this week yet again working unsuccessfully at reducing the offline optimum algorithm to polynomial time, trying a lot of different ways to reduce the complexity of the algorithm. For example, I came up with a O((N + n) (N choose n)) algorithm that uses a bitmask to denote the last element recycled from each bin. However, once again, for variable n this is exponential time. In another algorithm, I tried to represent each state by position in the stream and count for a given bin, which would run in polynomial time, but the problem becomes that there is not enough information to compute the answer from other states. Each other state would need to have given counts in two bins, not just one, and if you make the state include the count for this second bin, then you need three in the other states, and so on. I will keep working on trying to find a polynomial-time algorithm, but I think this dynamic programming approach is coming at it from the wrong direction.
Week 4: (6/15-6/21): Worked more on finding optimal offline algorithm. Tried a new strategy where I compute the optimal answers for every start / end point when only the first k bins can be recycled from, which is somewhat similar (in the general sense) to the Aggressive Empty strategy mentioned in Optimal Ball Recycling. However, even with this addition, I was unable to improve the dynamic programming to get it down to polynomial time. Given how much time I have spent trying to do this, I have now also begun working on potentially proving that the problem is NP-Complete (in the general case where n and m are both variable). Regarding Random Ball, I tried a lot more counterexamples to try to show that it is not constant-optimal in the worst case, but have so far been unsuccessful. These results, as well as the fact that Random Ball is within a constant of optimal in expectation, have led me to believe even more strongly that Random Ball is actually constant-optimal in the worst case. In order to gain evidence for this claim, I reread the section of Optimal Ball Recycling on proving that it within constant of optimal (in expectation), but am still working on how to apply the methods there in the worst case. If it turns out that this is true in the worst case as well, and specifically the 1/2 of optimal bound holds for Random Ball, this would show that Random Ball is an optimal online algorithm, because the adversary I used to show that Random Ball is at most 1/2 of optimal applies to any recycling strategy, so long as the adversary has access to any random bits the strategy will use to make decisions.
Week 5: (6/22-6/28): Worked more on finding optimal offline algorithm. Strongly beginning to suspect that it is not solvable in polynomial time (with respect to n, m, and N simultaneously), although I have not yet been able to make a reduction from an NP-complete problem, though that is something I will keep trying going forward. I have also begun to explore non-deterministic alternatives. Specifically, I investigated a randomized algorithm that, instead of storing all (n + m - 1) choose m states for a given position in the stream, only stores polynomially many, keeping a certain number with each count for a given bin. It seems that even this will likely not be enough for a full solution, but I think there is a good chance that it will be within a constant factor of optimal. With regards to Random Ball, I have tried to come up with a lot more counterexamples, and at this point I believe it is constant-optimal, so going forward I will be working on proving that.
Week 6: (6/29-7/5): For the optimal offline algorithm, worked on finding polynomial-time algorithms that gave answers within a constant of optimal. Looked back at some of the strategies I investigated in the first couple weeks, such as always recycling the bin that sends the least balls to itself, or the bin that sends the most balls to other bins. Also came up with a new strategy, looking at all possible combinations of the first c bins to recycle (for constant c). However, in each of these cases, I was able to find an adversary for which the algorithm was a non-constant factor worse than optimal. For the last one, this counterexample was a form of a skyscraper distribution, but the specific parameters of the distribution had to be very specific. Still working on analyzing the randomized algorithm from last week. Its analysis is proving to be more complicated than I expected.
Week 7: (7/6-7/12): For Random Ball, Dr. Farach-Colton recommended that I look into Yao's minimax principle to get bounds on the performance of Random Ball based on the performance of deterministic algorithms. This will help with getting an upper bound on performance, and I am still working on methods to prove the lower bound. I wrote some code to test the performance of Random Ball on several adversaries, against what I believe to be the optimum algorithms on those adversaries. In many of these cases, Random Ball got very close to optimal (within about 15%). In some cases, it got down to a bit over half of optimal, but never below that. I believe the adversaries I tested should be among the worst for Random Ball, so this is a good sign for it being constant-optimal. I also began writing the paper.
Week 8: (7/13-7/19): Proved several smaller results to add to the paper. For example, in the stars-and-bars dynamic programming, proved that in the worst case, all states (asymptotically) are reachable, so you can't cut down the time complexity significantly by just removing the unreachable states. I also added in a counterexample for Random Ball where the adversary does not have access to the random bits used to choose the random balls. I tried a few cases, but the best I could get here was a competitive ratio of 8/9, which matches pretty closely with the randomized trials I did last week. Kept writing the paper, and kept trying to prove that Random Ball in general was constant-optimal.
Week 9: (7/20-7/24): Made presentation and finished the paper. Found a hole in the proof that all states (asymptotically) are reachable, so I took that out. Gave presentation on Wednesday (link below). Worked more on proving that Random Ball is constant-optimal, but still haven't gotten anywhere.

Presentations

References

Additional Information