- Worst Case Ball Recycling Problem
- Project Year:
2020
- REU Student (s):
Joseph Durie | Rutgers University-New Brunswick NJ
- Student 1 Institution:
Rutgers University-New Brunswick
- Project Mentor:
Martin Farach-Colton
- Project Mentor Area:
Computer Science
- Project Abstract:
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 investigated 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 was to find an online algorithm that gets as close as possible to the offline optimum algorithm over all possible adversaries.
