The Variable-Processor Cup Game

on YouTube ↗19m

" summary

Shows that allowing P to vary changes guarantees drastically: the greedy emptier remains optimal versus deterministic adversaries but its backlog jumps from O(log N) to Ω(N). Provides a recursive filling strategy that forces backlog ~N within time about 2^N, and a refined construction that still forces backlog N^{1-ε} in quasi-polynomial time against randomized greedy-like emptiers. Highlights dependence on adaptive versus oblivious fillers and leaves open whether the N^{1-ε} gap is avoidable.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:14THE SINGLE-PROCESSOR CUP GAME
3. 1:39THE P-PROCESSOR CUP GAME
4. 2:33THE GREEDY ALGORITHM
5. 3:14LOTS OF OTHER DIRECTIONS OF RESEARCH
6. 4:09ON TIME-SHARED SYSTEMS, RESOURCES VARY
7. 4:59THIS PAPER: THE VARIABLE-PROCESSOR CUP G.
8. 6:27How DOES GREEDY PERFORM?
9. 7:52WHAT ABOUT FOR SHORTER GAMES?
10. 8:50WHAT IF THE EMPTIER IS RANDOMIZED? Important Note: The filler is an oblivious adversary
11. 10:50PUTTING THE RESULTS TOGETHER
12. 12:03THE GOAL
13. 12:15INDUCTIVE HYPOTHESIS: n-1 CUPS
14. 14:06FREEZE CUP 1 DURING THE RECURSION
15. 15:25SET p = 1 AND PLACE 1/2 IN EACH CUP
16. 16:09DOWNSIDES OF THIS CONSTRUCTION