Online Vector Packing

on YouTube ↗52m

" summary

General online vector packing is essentially hopeless in the worst case: competitive ratio grows Θ(d) for arbitrary vectors, and an information-theoretic lower bound nearly D^{1−ε} appears for the b=1 case. Assuming every coordinate ≤1/B yields sublinear bounds (upper ~D^{1/(something like B·log D)}, lower ~D^{1/B}). A e-competitive fractional sliding-window algorithm uses density 1/x; randomized rounding plus spillover yields an unsplittable randomized ~e-competitive algorithm for tiny vectors (sizes ≲ ε^2 log D), and a lower bound approaching e via duality shows e is essentially tight as d→∞.

AI-written summary · about

" chapters (26)

1. 0:00Intro
2. 1:45amazon Cloud Computing
3. 5:53Two Dimensional Interpretation
4. 6:18Vector Bin Packing Problem
5. 6:46Online Algorithms
6. 7:11Example: First Fit
7. 9:42VBP(B=1) Lower Bound
8. 12:24Online Vector Packing • In practice, task demands are small compared to capacity
9. 14:13VBP Lower Bound
10. 16:41Closing The Gap
11. 17:49Two Dimensional Vector Packing
12. 18:25Algorithm for arbitrary dimension
13. 18:42Our Techniques
14. 19:05The Splittable model
15. 19:42Phase 1: Splittable Model - OPT
16. 21:13Multidimensional Setting
17. 21:27Sliding Window Algorithm
18. 29:10Randomized Unsplittable Algorithm
19. 31:27Proof Idea
20. 32:18(1 + ε)e-competitive deterministic Alg
21. 36:04Lower Bound (d=2)
22. 37:52Phase 2 ALG opens additional cA bins by end of Phase 2
23. 39:46Lower Bound for arbitrary d
24. 45:56Online Lower Bounds via Duality
25. 47:27Conclusions
26. 48:04Open Problems